Say I need to choose a random winner amongst three people and all I have to provide random outcomes is a coin. I could assign the first person TT, the second person HH, and the third person TH, and then HT is a "re-do." But that could theoretically continue indefinitely if I get unlucky enough to keep flipping HTs. I thought about flipping the coin three times, but with eight permutations possible, I'd still have a remainder (say, HTH and HTT) that I'd have to assign to the "re-do" outcome, so I haven't improved anything. I suspect that since there are no powers of two that are divisible by three, no amount of flips will leave me without some remainder that could result in a re-do. (It does get less likely that there won't be a winner with the more flips I do—5 flips means only a 2/32 chance it'll be a re-do, but it's still possible to have to do countless flips.)

Is there a way to fairly choose a random winner amongst three people with a definite number of coin flips?

No, you can’t be certain to be able to select someone with a finite number of flips at exactly 1/3 chance of selection.
Imagine the whole (binary) tree of an infinite sequence of coin flips. Ie a tree with that always divides into two branches. We want to select exactly 1/3 of that tree by combining subtrees. No matter how you add the subtrees of that tree together, you are essentially always adding fractions of the tree with powers of two as denominator. Like you can add half the tree, or a quarter of the tree, or an eighth of the tree…

So you can only select events with probabilities that look like: a1 / 2 + a2 / 4 + a3 / 8… where a1, a2, a3, etc are all either 0 or 1.

This probability is equivalent to a decimal in base 2. Eg something that looks like
0.100011101010101100111111

But if you want exactly a 1/3 chance, you have to be able to express the decimal 1/3 =
0.010101010101010101010101…

In other words, there’s never going to be a way to add a finite number of subtrees together to get exactly 1/3 of the tree.

Thanks for the response.

i can't see a way but it's an interesting question.

obviously if you keep flipping in a round robin format, you will have a winner.. or 99.99%+ chance of a winner fairly quickly

So we have entities A, B & C.

1. Split A & B into camp 1 and camp 2
2. Flip coin to add C to either camp 1 or camp 2
3. Flip coin to determine which camp is eliminated.
4. Remaining camp has either one (winner) or two entities.
5. If camp has two entities, use coin to determine winner.

That's unfair to C because C is always in a camp of two people. C has a 1/4 chance of winning while A and B each have a 3/8 chance.

I knew it was too easy, back to the drawing board.

Outside of the box: By some fortunate circumstances, the circumference of a America quarter is almost exactly 3 inches. So mark the quarter's coin edge with three marks at one inch intervals on each side. Now you have a coin that can be tossed and help you randomize into three equal probability outcomes on a single toss.

Take your coins to a store. Trade them for a six-sided die. Assign each player two integers between 1 and 6. Roll the die to determine the winner.

Obviously tongue-in-cheek, but there is no way to generate any space of outcomes using a coin whose size is anything but a power of 2. All powers of 2 are not divisible by 3, so your problem has no solution.

Again: no guarantee of finiteness, but in practice it will end.

Each person flips the coin. If all get the same result, do it again. Otherwise, the odd result is the winner.

Yes, if three different "sequences" are allowed (one for each person), then there are innumerable ways to select a "winner" via randomness.

OP was asking about solutions that don’t require “do overs” though. In practice you will always get a winner in a finite number of iterations. For any given N, the value 2^N has a remainder of either 1 or 2, so there are either 1 or 2 sequences of N flops that will not be assigned to one of the three players. The probability of such a sequence actually occurring is 2^-N if the remainder is 1 and 2^(-N+1) for a remainder of 2. In either case that probability tends to zero as N goes to infinity, so in practice we can make it as small as we like by increasing N. That doesn’t give a solution to OPs problem though. Since 2^N is never divisible by 3, no solution exists.