I read about this question online today and found it interesting [source]:

You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with 40% probability. Write a new function that returns 0 and 1 with 50% probability each. Your function should use only foo(), no other library method.

You can easily find the solution in the link above, but I thought it in the wrong way: my first attempt was to return 0 if two tosses return (1,0) and (0,1), 1 otherwise. Apparently the math does not add up here: P(1,0) + P(0,1) = 0.52. Later I learned that John von Neumann has proposed an elegant algorithm to solve it (though not 100% efficient). Naturally, I asked myself: can I use the same unfair coin to generate 1, 2 and 3 with equal probability (i.e. each with chance 1/3)?

... I took the wrong path again. Trying to group all combinations by tossing the coin 3 times into 3 groups: (000, 111) -> discard & continue to toss; {1 one, 2 zeros} and {2 ones, 1 zero}. Unfortunately P(1 one, 2 zeros) != P(2 ones, 1 zero) plus I can't get 3 numbers out of this grouping mechanism. Someone on Twitter proposed the following:

Generate 3 bits. Return 0 if 100/011, 1 if 010/101, 2 if 001/110, start over if 000/111.

Inspired by the 3 case, I think the following should work if I were to use the same coin to generate 1-5 with equal probabilities:

Generate 5 bits. There will be 2^5 = 32 combinations in total. Occurrences of {1 one, 4 zeros} = {4 ones, 1 zero} = 5, whereas {2 ones, 3 zeros} = {3 ones, 2 zeros} = 10. Return each number by exhausting the following sequence: (1 combination from {1 one, 4 zeros} , 1 combination from {4 ones, 1 zero}, 2 combinations from {2 ones, 3 zeros}, 2 combinations from {3 ones, 2 zeros}). Repeat the process if either {00000, 11111} is obtained.

Note: the above process could be generalized to other prime, odd numbers. Non-prime odd numbers fail as there exists an odd number d, 2k < d such that d cannot divide C(d, 2k) without a remainder. E.g. d=9, k=3.

It's entertaining to think through this kind of probability questions sometimes. Happy weekend!