[chaoxu]

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?

[thaumasiotes]

> 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.

[asheldon]

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.