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