How about the following process? Each person gets randomly assigned to one of the two groups, when one group is full, move the rest to the other group. Does this make sure every equal partition have the same probability of showing up?
> Does this make sure every equal partition have the same probability of showing up?
I'm not sure, but I wouldn't bet against it. But what is the value of having an exactly equal partition?
On second thought, the algorithm you describe processes people in a particular order, and it is much more likely to put two people who both occur near the end of the list into the same bucket than to put them in different buckets. So if that processing order is constant, the algorithm cannot produce every equal partition with equal probability.
I agree. It would be simpler to shuffle the list of people, then split the list in half.
Here's a proof this algorithm doesn't work by counter-example (N=6)
Consider a list of 6 elements. Elements 5 and 6 must be in the same bucket 50% of the time and different buckets 50% of the time. For this to be true, after we place the first 4 elements into their buckets according to this algorithm, there must be space left in both buckets 50% of the time and in only one bucket 50% of the time.
Sequences of the first 4 coin flips where neither bucket is filled, followed by possible ending sequences, and the odds of the prefix.
AABB(AB, BA) = 1/16th
ABAB(AB, BA) = 1/16th
ABBA(AB, BA) = 1/16th
BBAA(AB, BA) = 1/16th
BABA(AB, BA) = 1/16th
BAAB(AB, BA) = 1/16th
Total: 3/8ths
Sequences of the first 3-4 coin flips where one bucket is filled, followed by possible ending sequences, and the odds of the prefix:
AAA(BBB) = 1/8th
BBB(AAA) = 1/8th
AABA(BB) = 1/16th
ABAA(AA) = 1/16th
ABBB(AA) = 1/16th
BBAB(AA) = 1/16th
BABB(AA) = 1/16th
BAAA(BB) = 1/16th
Total: 5/8ths
Since one bucket is filled 5/8ths of the time after 4 elements are processed according to this algorithm, the final two elements will be in the same bucket 5/8ths of the time, not the expected 4/8ths of the time.
