Choosing a Non-Confederate Volunteer

Question

A magician is performing in front of a large crowd (around a 100 people, say) and wants a volunteer for a trick. The magician knows that he has no confederates in the crowd, but the crowd doesn't. How can the magician choose a volunteer from the people raising their hands, convincing the crowd that the volunteer is not a confederate?

I'm looking for a method that:

• is quick (should not take more than a couple of minutes)
• does not require uncommon equipment (eg. Geiger counters for randomness, etc. And then again, how do you prove the counter isn't rigged?)
• isn't complicated for the volunteers (eg. you cannot ask volunteers to calculate the moduli of products of large primes, etc.)

If possible, the method should be fair in the sense that all the people who volunteer to volunteer have an equal chance of being selected. Also, if possible, it should be clear to the mathematical layperson in the crowd that the method fulfills its purpose.

Edit: I thought I had one method of doing this, but as @Robert Israel and @Hans Lundmark have pointed out, it is not actually infallible. Further, it is fairly complicated, not guaranteed to terminate, and not very practical for an actual magic show. I am keeping it as an answer for lack of better ones.

Answer 1

Have the volunteers select one of them. Tell them to point at one of the others at the count of three. If there's a tie, do a run-off, but no need to spend too much time on that if there's another tie, since the probability that your confederate is among the top two is already low enough.

There might be some room for manipulation by having the confederate sit near the centre and thus be more likely to be voted for, so ideally the volunteers should step out of the audience and form a circle for symmetry. Explaining the reason for this might contribute to convincing the audience.

This may not be enough since people might suspect that a sufficient proportion of the volunteers were confederates to skew the election significantly. If so, you could let the entire audience vote; the downside is that this might make it significantly harder to resolve ties without raising suspicion that it's not being done objectively; counting the volunteers' votes is easier.

Of course any method will only work if there are enough volunteers, so if there are only two or three, you might want to emphasise that you need more in order to make sure that no confederate can be chosen.

Answer 2

First, the magician assigns consecutive numbers to the people volunteering to volunteer, from 1 to $n$. Using von Neumann's method, the magician treats a possibly biased coin as an unbiased coin, and flips this 'coin' $\lceil \log_2 n \rceil$ times. Before flipping the 'coin', the magician will have already declared that, for example, a result of 'heads' represents a binary '1' and 'tails' represents '0'. Now the sequence of flips can be converted into a number: if a volunteer has been assigned that number, that volunteer is chosen, otherwise the sequence of flips is repeated.