July 20th, 2007
You can post solution related comments on this page.
Pages: 1 2
This entry was posted
on Friday, July 20th, 2007 at 5:17 am and is filed under Math, Riddles.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
August 3rd, 2007 at 1:59 am
solution:
for one coin we will have 50-50 odds.
this will allow us to create random numbers in the range 0..X-1 where X is a power of 2.
we should choose such an X that satisfies X div (N-1) is bigger than X mod (N-1).
with such an X we can randomize numbers in the range 0..N-1 such that only one of them has a smaller chance than the others, which have the same chance.
when we randomize a number R in range 0..X-1, if it is below X-(X mod (N-1)), we select 1+R mod (N-1) as the result, otherwise, the result would be N.
to fix this state where one number has a smaller chance, we will use the other coin.
the first toss would be of that other coin, so that tails would mean selecting the number N, and heads would invoke the process described above.
the chances for this coin would be X for heads to X div (N-1) – X mod (N-1) for tails
August 11th, 2007 at 11:54 pm
Yair,
Brilliant solution. Thanks!
For all the others, let me clarify it a little, since its a bit obscure.
The most important step is selecting a number of the set {1,…,N} such that the probability for the number 1 is p, and the probability of all the numbers, 2,…,N is q, and such that q>p. This selection should be done with a fair coin (i.e. heads probability = tails probability = 1/2).
This can be done as follows: Using the fair coin, generate a randon number X, in the range 1,…,2^k, such that 2^k > N^2. Then, if you got a number in the range 2^k-(2^k)mod(N-1),…,2^k you select 1. Otherwise you select X mod(N-1). Obviously (well, after understanding all that weird notations…
) the probability of 1 is indeed lower than the probabilities for numbers in the range 2,…,N which are all equal.
Now, after we have that, we use the other coin to fix the bias – i.e. the probability of the second coin to be heads should be r, such that r+(1-r)*p = 1/N (p is as before).
Thats it!
August 12th, 2007 at 12:26 am
I think I also have a simpler solution.
Lets first start with a simple example. Say N = 7. Since 2^3=1 (mod 7) we can toss a fair coin three times, such that the number 1 will have a greater probability than the other numbers, which will all have the same positive probability (its like the oposite of the solution above). We can now fix the bias with the second coin.
Now, obviously this only works for N, such that there exists a k, such that 2^k=1 (mod N), and not all N are such (e.g. 10). But a simple variation of the above method can work on all N. Say there is a k such that 2^k > N and 2^k = 2^l (mod N), for some l. Then obviously the same method can work as well. All it remains to do is prove that indeed for all N, such k exists.
Now, if N is odd, then such k obviously exists. Otherwise, N = R*2^s, s > 0, R is odd. Then there exists t, such that 2^t = 1 (mod R). Then 2^(s+t) = 2^s (mod N). Et voilà!
August 25th, 2007 at 3:16 pm
So I have a different solution than the previous 2.
Let the first coin have the probability of 1/2.
Let K be the largest number, that implies 2^K
August 25th, 2007 at 4:18 pm
So I have a different solution than the previous 2.
Let the first coin have the probability of 1/2.
Let K be the largest number, that implies 2^K < N!.
Let the second coin have the probability of Q=2^K/N!
Given a number x in [1..N], I’ll demonstrate a method of creating a probability of 1/x
1. Select M=N!/x
2. Flip the even coin K times.
3. If the binary coded number is smaller than M, Flip the non-even coin.
4. If it fell on ‘Heads’ (the Q probability), return “True”
5. If the binary coded number is M or larger, or the non-even coin fell on ‘Tails’, return “False”
The probability of “True”, is therefore M/(2^K)*Q=M/2^K*2^K/N=M/N=N!/x/N!=1/x
Therefore, we have a virtual coin, with a probability of 1/x for every x in [1..N]
No, the algorithm will be:
1. Select 1 in a probability of 1/N. if failed continue.
2. Select 2 in a probability of 1/(N-1). if failed continue.
and so on…
August 26th, 2007 at 2:10 am
Nadav,
Extremely cool solution!
In my opinion it is the easiest solution proposed thus far (although it is not very economic – it “wastes” a lot of coin tosses).
Actually an interesting sequel would be to calculate the bounds on the number of tosses required by the different solutions.
August 31st, 2007 at 12:18 am
This question originates (as far as I know) in the Gillis-Turan binational mathematical olympiad.
Nadav’s solution was the one I originally had, and I like it a lot. You can save a few coin tosses by taking lcm(2,3,…,N), but that’s not very important. There are several more solutions based on the tactic of splitting into two sets, each with members of equal probabilities , then using the second coin to correct them. I know of another solution which is quite different, but I won’t detail it right now as it helps to solve the (much harder, but not impossible) question: Do the same, but with one coin only!
August 31st, 2007 at 12:35 am
Dan,
Until now I only heard rumors about a solution using only a single coin.
I have not given it any thought yet, as these rumors said that the result bases itself on some unproven hypothesis.
I understand from your comment that the riddle with a single coin has a valid solution (please confirm this).
If so I will sure think about it! (as I am sure will do many other readers of this blog).
Anyway, thanks a lot for not revealing the solution yet!
August 31st, 2007 at 4:48 am
It is indeed completely solvable. In fact, I know of two very different solutions to the problem, both quite provable.
October 19th, 2008 at 6:08 pm
Dan,
It’s been a year – Please post your solutions.
Thanks!
October 19th, 2008 at 6:29 pm
I must say that I second m0she’s request, although I still haven’t thought about the single coin form of the riddle enough.
Dan – you are welcome to post your solutions.
October 19th, 2008 at 8:57 pm
hey, I think I have some partial solution.
maybe you can 
if I had more free time or if I was as smart as I used to be I’d try to finalize it
it goes like this:
we toss the coin K times.
the coin’s odds, P, are such that P^K+(1-P)^K=1/N.
I think we can find such P for every K>1, N>1. but I leave proving that as an exercise
if all tosses are the same, then we choose the number N.
if they’re not, then let’s look at the number of possible combinations that have the same heads/tails count, C.
there are K!/C!/(K-C)! such combinations.
if we chose K right, that divides by N-1 for every C except for 0 and K.
so we can group all of the tosses of same heads/tails count to N-1 equal groups. and each group will give a different number from 1 to N-1.
what K can do the job? I think maybe (N-1)^2 can. but I’ll leave that as an exercise too
maybe my blanks/exercises here can be filled and maybe not
October 30th, 2008 at 10:37 pm
The following solutions are sorted in reverse chronological order of when I’ve seen them.
#1:
This is very similar to Yair’s idea, but makes certain useful assumptions: We need to assume that N is at least 4, and that Q=N-1 is a prime number, and choose K=Q. This satisfies that (Q choose C) = Q!/C!(Q-C)!, and for Q>C>0, since Q is prime, Q divides Q! but does not divide C! or (Q-C)!, and hence divides (Q choose C), like we wanted. We can choose the probability P such that f(P)=P^K+(1-P)^K=1/N, because f(P) is a continuous function of P, which satisfies f(1)= 1 > 1/N, f(1/2)= 2*(1/2)^K = 1/2^(N-2), which is not greater than 1/N for all N at least 4. Hence by the mean value theorem, there is a P in (1/2,1) with f(P)=1/N, and we are finished.
Now we only need to understand why the assumption that N-1 is prime does not limit us: Indeed, for all N, by Dirichlet’s Theorem, we know that there are infinitely many primes Q in the arithmetic sequence {m*N-1| m is Natural}, and if we take one such prime that is at least 3, then by the above we have a solution for m*N=Q+1. But then if we treat each person as m different people, we have a solution for N people, and we are happy.
(By the way, such K does not necessarily exists for all N where N-1 is not prime, and in fact no such K exists when N-1 is non-prime, as the following claim is true: The greatest common divisor of all (K choose C), where C ranges from 1 to K-1, equals a prime Q iff K is a power of Q, and if K is not a prime power, it equals 1)
#2:
This has some similarities to #1, but is a little different. We will need to assume that N is large enough, but as shown before, small N can be reduced to the larger m*N case easily.
Let the probability of the coin be P. We will flip the coin K=N-1 times, and write the result of the filp as a string of length K composed of letters H and T. Such a string will be called “bad” if it can be cyclically shifted right less than K times and it will return to itself, i.e. if it is non-trivially periodic. A string will be called “good” iff it is not bad. Then obviously the good strings can be divided into N-1 sets of strings, all with equal total probability, by ensuring that if one good string can be obtained from another by cyclic rotations, then they are in different sets. Now, let f(P) denote the probability of the result string being a bad string. Then we only need to be certain that it’s possible to choose P such that f(P)=1/N.
It is clear that f(P) is a polynomial of order K-1 in P, and thus continuous. If P=1, then the result string is always all heads, which has period 1 and is thus a bad string, so f(1)=1 > 1/N, and we need only see that 1/N > f(1/2), for example. Now, if P=1/2, then f(P) is simply the number of bad strings of length K divided by 2^K. We can count the bad strings by separating them based on their minimal period – the number of bad strings with period d equals 2^d if d is a proper divisor of K or 0 otherwise, and hence the number of bad strings with minimal period d is certainly not greater than 2^d, and 0 when d does not divide K. Hence the total number of bad strings is at most the sum of 2^d over all proper divisor d of K. The greatest proper divisor of K is of course at most K/2, hence the number of bad strings is at most the sum of 2^d over all natural d up to K/2, which is lesser than 2^((K/2)+1), and hence f(1/2) is lesser than 2^(K/2+1)/2^K=1/2^(K/2-1)=1/2^((N-3)/2). Obviously, exponential in N decreases to 0 much faster than 1/N, and so for large enough N we indeed have f(1)>1/N>f(1/2), as required.
#3:
This solution is somewhat long and messy, so I will leave some parts as exercise.
Denote by p the probability of heads, q the probability of tails (p+q=1), and choose them such that p*q=1/N (possible iff N is at least 4). Flip the coin a large number K of times. We will assign the results of the raffle to the results of the coin flips in such a way that if all coin flips were changed, we will choose the same person, with the exception of results with equal numbers of heads and tails (if K is even). We will then have basic “building blocks” with sizes of the form p^l*q^m+p^m*q^l for m+l=K, l>m non-negative integers, or p^l*q^m when l=m=K/2. Using the basic relations p+q=1, pq=1/N, it is possible to partially compute the above expressions and see that they can all be represented as rational numbers with denominator N^[K/2] (where [x]=floor(x)). Furthermore we have all the following properties:
1) The integers (N^[K/2])*(p^l*q^m+p^m*q^l), or half of that for m=l, decrease as m increases, for m up to [K/2];
2) For all integers r from 0 to [K/2]-1, the integer corresponding to m=r is less than N times greater than the integer corresponding to m=r+1;
3) For all r from 0 to [K/2], there are (K choose r) appearances of the integer corresponding to m=r, and hence at least K appearances for all r from 1 to [K/2];
4) The sum of all these integers, counting multiple appearances, is of course N^[K/2] by the binomial theorem;
5) The smallest of these integers (corresponding to m=[K/2]) is exactly 1;
These properties guarantee that as long as K is at least N^2, it is possible to divide the integers above into N sets, such that each set will have sum exactly N^[K/2]-1, which once we return to the original probabilities by dividing by N^[K/2], yields exactly the wanted results.
The properties above imply this by implying something somewhat stronger: They imply that if we try dividing these integers into sets by taking at each step the largest integer not yet used, and trying to place it into a set such that it will not make its sum exceed N^[K/2]-1, we will succeed: Properties 2 and 3 and 4, together with K > N^2, imply that this process will not halt before we reach the smallest integers, and properties 4 and 5 imply that the smallest integers will always fit into the sets, because they are of size 1. This concludes this long proof.
Some analysis and comparison: Solutions #1 and #2 are quite similar, and in fact are completely the same in the case that N-1 is prime. The extension to other cases is quite different though: Solution #2 is efficient in coin tossing, always requiring only N-1 tosses, but the calculation of the polynomial f(P), and thus of P, might be long and annoying. On the other hand, solution #1 always uses a simple polynomial that needs to be solved to find P, but also depends on finding a prime in the arithmetic sequence, which might be difficult and gives no simple estimation of the number of coin tosses as a function of N. Solution 3 only requires solving a quadratic in order to obtain the probability p, and only O(N^2) tosses (possibly significantly less), but actually assigning the results seems more complicated than in #1 and #2.