Is the probability $\frac12$?

I have $n$ players in total. Note that $n$ is even. We want to pick $\frac n2$ players uniformly at random. We have access to only one unbiased coin. We want to make this bisection in minimum expected number of coin tosses. What should I do?

My approach: I will keep tossing-if it is H I will add the player to team A else to team B. If there are already $\frac n2$ players in any team, I stop tossing and put the rest in other team. Leaving aside the problem of proving why this will give minimum number of tosses, I am not sure why the players have equal probability of getting to team A or B. It is clear for the first $\frac n2$ players but after that it gets a little messy.

Please don't say that it is symmetric so probability is half trivially.

Solution 1:

Step 1: Set $k={n\choose n/2}$.

Step 2: Choose an integer between $1$ and $k$, uniformly at random with your coin. This is a well-known problem, e.g. here. If $k$ happens to be a power of $2$ it can be done in a finite number of flips; otherwise, either the number of flips is unbounded (but very unlikely to be large) or your distribution is not precisely uniform (but very close).

Step 3: Choose the subset of size $n/2$, based on the outcome of step 2, and a lexicographic ordering of the subsets. For example, if $n=4$ and the players are $A,B,C,D$, then the first subset is $AB$, the second is $AC$, etc.

Solution 2:

It can't be done with a finite number of tosses at all. If $n=4$, then there are $\binom42=6$ possible bisections, so you want the probability of each bisection to be $\frac16$, which is not a sum of powers of $\frac12$.

You could consider a protocol using an unbounded number of tosses, and then ask for a protocol that minimizes the expected number of tosses. Or a protocol that maximizes the probability of being done as soon as possible, or something like that.