What are the Odds?
July 20th, 2007
This is the first riddle I post in my site that I haven’t yet solved.
Because of this, I give it the “very hard” icon. It may turn out to be easy – do not be intimidated!
You are given a natural number N and two coins. You can set the probabilities of getting heads or tails on both coins as you wish. You are then asked to generate a random number uniformly distributed on the set { 1, 2, …, N }. The catch is that you must have a finite upper bound on the number of coin tosses you use.
Lets clarify the requirements of the riddle by a simple example. Say N=6. Setting the probabilities for the coins to 2/3 and 1/2 will do the trick, as we can generate a number uniformly distributed on the set { 1, 2, 3, 4, 5, 6 } with a maximum of 3 tosses of the two coins (can you see how?).
Good luck!
Pages: 1 2
July 26th, 2007 at 9:36 am
Warning: Spoiler Comment (solution)
we set one coin to 50-50
now let’s find a power of two X that satisfies X mod (N-1)
July 26th, 2007 at 9:37 am
arg, all my comment after the little-then-symbol disappeared!
damn..
August 2nd, 2007 at 6:23 pm
I might be wrong, but it seems too easy and can be resolved with a single standard coin (50% H/T), as follows:
Find the smallest number M which satisfies 2^M>N.
Set the first coin’s probablity to 0.5 for Head.
Toss it M times.
There are 2^M different permutations of the sequence (i1,i2,i3,…,iM) where i is H or T.
Each permutation can be mapped to a number in the range 0 to 2^M-1, with a uniform probability.
Ignore the numbers outside the 1-N range. The process generates the numbers from {1,..,N} uniformly.
Leave the second coin untouched..
August 2nd, 2007 at 7:24 pm
Hi Assi,
Notice the sentence: “The catch is that you must have a finite upper bound on the number of coin tosses you use” (maybe I should have made it bold
).
This means that you cannot ignore any result of the coin tosses!
There is no finite upper bound on the number of coin tosses needed by your solution, as for all N, there is a positive probability of you getting a result that you ignore more than N times.
PS – please post solution related comments on the second page of the riddles (as not to ruin the riddle for people that haven’t solved them yet).
August 26th, 2007 at 1:20 am
Cool solution Nadav!
You even solve a broader problem – you can choose a random number in any smaller range too.