First, I claim that for any prime q, it is possible to choose one of q + 1 outcomes with just one coin. I do this as follows:
Let p be a probability such that pq+(1−p)q=1q+1. (Such a p exists by the intermediate value theorem, since p = 0 gives a value that’s too large and p = 1⁄2 gives a value that’s too small.)
Flip a coin that has probability p of coming up heads exactly q times. If all flips are the same, that corresponds to outcome 1. (This has probability 1/(q + 1) by construction.)
For each k between 1 and q − 1, there are (qk) ways of getting exactly k heads out of q flips, all equally likely. Note that this quantity is divisible by q (since none of 1, …, k are divisible by q; this is where we use that q is prime). Thus, we can subdivide the particular sequences of getting k heads out of q flips into q equally-sized classes, for each k. Each class corresponds to an outcome (2 through q + 1). The probability of each of these outcomes is qq+1⋅1q=1q+1, which is what we wanted.
Now, note that 2021*12 − 1 = 24251 is prime. (I found this by guessing and checking.) So do the above for q = 24251. This lets you flip a coin 24251 times to get 24252 equally likely outcomes. Now, since 24252 = 2021*12, just assign 12 of the outcomes to each person. Then each person will have a 1/2021 chance of being selected.
Conjecture (maybe 50% chance of being true?):
If you’re only allowed to use one coin, it is impossible to do this with fewer than 24251 flips in the worst case.
Question:
What if you can only use coins with rational probabilities?
Note that your approach only works for target N>3 (that is q>2), as p2+(1−p)2=1/3 does not have a real solution. Open question: How about 1-coin solution emulating a 3-sided dice?
See my solution (one long comment for all 3 puzzles) for some thoughts on rational coins—there are some constructions, but more importantly I suspect that no finite set of rational coins without the 1/2-coin can generate any fair dice. (My lemma does not cover all rational coins yet, though; see by the end of the comment. I would be curious to see it turn out either way!)
Update: I believe the solution by @UnexpectedValues can be adapted to work for all natural numbers.
Proof: By Dirichlet prime number theorem, for every N, there is a prime q of the form q=(N−1)+kN as long as N-1 and N are co-prime, which is true whenever N>2. Then N|q+1and the solution by UnexpectedValues can be used with appropriate p. Such p exists whenever q>2which is always the case for N>3. For N=3, one can take e.g. q=5 (since 3|5+1). And N≤2 is trivial.
Puzzle 3 thoughts: I believe I can do it with
1
coins, as follows.
First, I claim that for any prime q, it is possible to choose one of q + 1 outcomes with just one coin. I do this as follows:
Let p be a probability such that pq+(1−p)q=1q+1. (Such a p exists by the intermediate value theorem, since p = 0 gives a value that’s too large and p = 1⁄2 gives a value that’s too small.)
Flip a coin that has probability p of coming up heads exactly q times. If all flips are the same, that corresponds to outcome 1. (This has probability 1/(q + 1) by construction.)
For each k between 1 and q − 1, there are (qk) ways of getting exactly k heads out of q flips, all equally likely. Note that this quantity is divisible by q (since none of 1, …, k are divisible by q; this is where we use that q is prime). Thus, we can subdivide the particular sequences of getting k heads out of q flips into q equally-sized classes, for each k. Each class corresponds to an outcome (2 through q + 1). The probability of each of these outcomes is qq+1⋅1q=1q+1, which is what we wanted.
Now, note that 2021*12 − 1 = 24251 is prime. (I found this by guessing and checking.) So do the above for q = 24251. This lets you flip a coin 24251 times to get 24252 equally likely outcomes. Now, since 24252 = 2021*12, just assign 12 of the outcomes to each person. Then each person will have a 1/2021 chance of being selected.
Conjecture (maybe 50% chance of being true?):
If you’re only allowed to use one coin, it is impossible to do this with fewer than 24251 flips in the worst case.
Question:
What if you can only use coins with rational probabilities?
This comment is the best I can do on puzzle 3. Read it only if you want to be spoiled.
A beautiful solution! Some remarks and pointers
Note that your approach only works for target N>3 (that is q>2), as p2+(1−p)2=1/3 does not have a real solution. Open question: How about 1-coin solution emulating a 3-sided dice?
See my solution (one long comment for all 3 puzzles) for some thoughts on rational coins—there are some constructions, but more importantly I suspect that no finite set of rational coins without the 1/2-coin can generate any fair dice. (My lemma does not cover all rational coins yet, though; see by the end of the comment. I would be curious to see it turn out either way!)
Update: I believe the solution by @UnexpectedValues can be adapted to work for all natural numbers.
Proof: By Dirichlet prime number theorem, for every N, there is a prime q of the form q=(N−1)+kN as long as N-1 and N are co-prime, which is true whenever N>2. Then N|q+1and the solution by UnexpectedValues can be used with appropriate p. Such p exists whenever q>2which is always the case for N>3. For N=3, one can take e.g. q=5 (since 3|5+1). And N≤2 is trivial.