I wrote a logic puzzle, which you may have seen on my blog. It has gotten a lot of praise, and I think it is a really interesting puzzle.
Imagine the following two player game. Alice secretly fills 3 rooms with apples. She has an infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples. She must put a different number of apples in each room. Bob will then open the doors to the rooms in any order he chooses. After opening each door and counting the apples, but before he opens the next door, Bob must accept or reject that room. Bob must accept exactly two rooms and reject exactly one room. Bob loves apples, but hates regret. Bob wins the game if the total number of apples in the two rooms he accepts is a large as possible. Equivalently, Bob wins if the single room he rejects has the fewest apples. Alice wins if Bob loses.
Which of the two players has the advantage in this game?
This puzzle is a lot more interesting than it looks at first, and the solution can be seen here.
I would also like to see some of your favorite logic puzzles. If you you have any puzzles that you really like, please comment and share.
To make sure I understand this correctly: Bob cares about winning, and getting no apples is as good as 3^^^3 apples, so long as he rejects the room with the fewest, right?
A long one-lane, no passing highway has N cars. Each driver prefers to drive at a different speed. They will each drive at that preferred speed if they can, and will tailgate if they can’t. The highway ends up with clumps of tailgaters lead by slow drivers. What is the expected number of clumps?
Coscott’s solution seems incorrect for N=3. label 3 cars 1 is fastest, 2 is 2nd fastest 3 is slowest. There are 6 possible orderings for the cars on the road. These are shown with the cars appropriately clumped and the number of clumps associated with each ordering:
1 2 3 .. 3 clumps
1 32 .. 2 clumps
21 3 .. 2 clumps
2 31 .. 2 clumps
312 .. 1 clump
321 .. 1 clump
Find the mean number of clumps and it is 11⁄6 mean number of clumps. Coscott’s solution gives 10⁄6.
Must have counted wrong. Counted again and you are right.
Great problems though. I cannot figure out how to conclude it is the solution you got. Do you do it by induction? I think I could probably get the answer by induction, but haven’t bothered trying.
Take the kth car. It is at the start of a cluster if it is the slowest of the first k cars. The kth car is therefore at the start of a cluster with probability 1/k. The expected number of clusters is the sum over all cars of the probability that that car is in the front of a cluster.
Imagine that you have a collection of very weird dice. For every prime between 1 and 1000, you have a fair die with that many sides. Your goal is to generate a uniform random integer from 1 to 1001 inclusive.
For example, using only the 2 sided die, you can roll it 10 times to get a number from 1 to 1024. If this result is less than or equal to 1001, take that as your result. Otherwise, start over.
This algorithm uses on average 10240/1001=10.228770… rolls. What is the fewest expected number of die rolls needed to complete this task?
When you know the right answer, you will probably be able to prove it.
If you care about more than the first roll, so you want to make lots and lots of uniform random numbers in 1, 1001, then the best die is (rot13′d) gur ynetrfg cevzr va enatr orpnhfr vg tvirf lbh gur zbfg ragebcl cre ebyy. Lbh arire qvfpneq erfhygf, fvapr gung jbhyq or guebjvat njnl ragebcl, naq vafgrnq hfr jung vf rffragvnyyl nevguzrgvp pbqvat.
Onfvpnyyl, pbafvqre lbhe ebyyf gb or qvtvgf nsgre gur qrpvzny cbvag va onfr C. Abgvpr gung, tvira gung lbh pbhyq ebyy nyy 0f be nyy (C-1)f sebz urer, gur ahzore vf pbafgenvarq gb n cnegvphyne enatr. Abj ybbx ng onfr 1001: qbrf lbhe enatr snyy ragveryl jvguva n qvtvg va gung onfr? Gura lbh unir n enaqbz bhgchg. Zbir gb gur arkg qvtvg cbfvgvba naq ercrng.
Na vagrerfgvat fvqr rssrpg bs guvf genafsbezngvba vf gung vs lbh tb sebz onfr N gb onfr O gura genafsbez onpx, lbh trg gur fnzr frdhrapr rkprcg gurer’f n fznyy rkcrpgrq qrynl ba gur erfhygf.
Ebyy n friragrra fvqrq qvr naq n svsgl guerr fvqrq qvr (fvqrf ner ynoryrq mreb gb A zvahf bar). Zhygvcyl gur svsgl-guerr fvqrq qvr erfhyg ol friragrra naq nqq gur inyhrf.
Gur erfhyg jvyy or va mreb gb bar gubhfnaq gjb. Va gur rirag bs rvgure bs gurfr rkgerzr erfhygf, ergel.
Rkcrpgrq ahzore bs qvpr ebyyf vf gjb gvzrf bar gubhfnaq guerr qvivqrq ol bar gubhfnaq bar, be gjb cbvag mreb mreb sbhe qvpr ebyyf.
I am glad someone is thinking about it enough to fully appreciate the solution. You are suggesting taking advantage of 709*977=692693. You can do better.
You can do better than missing one part in 692693? You can’t do it in one roll (not even a chance of one roll) since the dice aren’t large enough to ever uniquely identify one result… is there SOME way to get it exactly? No… then it would be a multiple of 1001.
I am presently stumped. I’ll think on it a bit more.
ETA: OK, instead of having ONE left over, you leave TWO over. Assuming the new pair is around the same size that nearly doubles your trouble rate, but in the event of trouble, it gives you one bit of information on the outcome. So, you can roll a single 503 sided die instead of retrying the outer procedure?
Depending on the pair of primes that produce the two-left-over, that might be better. 709 is pretty large, though.
It is interesting to contemplate that the almost fair solution favors bob:
Bob counts the numbers of apples in 1st room and accepts it unless it has zero apples in it, in which case he rejects it. If he hasn’t rejected room 1 he counts the apples in 2 and if it is more than in 1 he accepts it else he rejects it.
For all possible numbers of apples in rooms EXCEPT one room has zero apples, Bob has 50% chance of getting it right. But for all possible number of apples in rooms where one room has zero apples in it, Bob has 5⁄6 chance of winning and only 1⁄6 chance of losing.
I think in some important sense this is the telling limit of why Coscott is right and how Alice can force a tie, but not win, if she knows Bob’s strategy. If Alilce knew Bob was using this strategy, she would never put zero apples in any room, and she and Bob would tie, i.e. Alice was able to force him arbitrarily close to 50:50.
And the strategy to work relies upon the asymmetry in the problem, that you can go arbitrarily high in apples but you can’t go arbitrarily low. Initially I was thinking Coscott’s solution must be wrong, that it must be equivocating somehow on the fact that Alice can choose ANY number of apples. But I think it is right, but that every strategy Bob uses to win can be defeated by Alice if she knows what his strategy is. I think without proof, that is :)
I think in some important sense this is the telling limit of why Coscott is right
Right about what? The hint I give at the beginning of the solution? My solution?
Watch your quantifiers. The strategy you propose for Bob can be responded to by Alice never putting 0 apples in any room. This strategy shows that Bob can force a tie, but this is not an example of Bob doing better than a tie.
Right about it not being a fair game. My first thought was that it really is a fair game and that by comparing only the cases where fixed numbers a, b, and c are distributed you get the slight advantage for Bob that you claimed. That if you considered ALL possibilities you would have not advantage for Bob.
Then I thought you have a vanishingly small advantage for Bob if you consider Alice using ALL numbers, including very very VERY high numbers, where the probability of ever taking the first room becomes vanishingly small.
And then by thinking of my strategy, of only picking the first room when you were absolutely sure it was correct, i.e. it had in it as low a number of apples as a room can have, I convinced myself that there really is a net advantage to Bob, and that Alice can defeat that advantage if she knows Bob’s strategy, but Alice can’t find a way to win herself.
So yes, I’m aware that Alice can defeat my 0 apple strategy if she knows about it, just as you are aware that Alice can defeat your 2^-n strategy if she knows about that.
So yes, I’m aware that Alice can defeat my 0 apple strategy if she knows about it, just as you are aware that Alice can defeat your 2^-n strategy if she knows about that.
What? I do not believe Alice can defeat my strategy. She can get arbitrarily close to 50%, but she cannot reach it.
I wrote a logic puzzle, which you may have seen on my blog. It has gotten a lot of praise, and I think it is a really interesting puzzle.
Imagine the following two player game. Alice secretly fills 3 rooms with apples. She has an infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples. She must put a different number of apples in each room. Bob will then open the doors to the rooms in any order he chooses. After opening each door and counting the apples, but before he opens the next door, Bob must accept or reject that room. Bob must accept exactly two rooms and reject exactly one room. Bob loves apples, but hates regret. Bob wins the game if the total number of apples in the two rooms he accepts is a large as possible. Equivalently, Bob wins if the single room he rejects has the fewest apples. Alice wins if Bob loses.
Which of the two players has the advantage in this game?
This puzzle is a lot more interesting than it looks at first, and the solution can be seen here.
I would also like to see some of your favorite logic puzzles. If you you have any puzzles that you really like, please comment and share.
To make sure I understand this correctly: Bob cares about winning, and getting no apples is as good as 3^^^3 apples, so long as he rejects the room with the fewest, right?
That is correct.
A long one-lane, no passing highway has N cars. Each driver prefers to drive at a different speed. They will each drive at that preferred speed if they can, and will tailgate if they can’t. The highway ends up with clumps of tailgaters lead by slow drivers. What is the expected number of clumps?
My Answer
You got it.
I am not sure what the distribution is.
The distribution; see e.g. here.
Ah, yes, thank you.
Coscott’s solution seems incorrect for N=3. label 3 cars 1 is fastest, 2 is 2nd fastest 3 is slowest. There are 6 possible orderings for the cars on the road. These are shown with the cars appropriately clumped and the number of clumps associated with each ordering:
1 2 3 .. 3 clumps
1 32 .. 2 clumps
21 3 .. 2 clumps
2 31 .. 2 clumps
312 .. 1 clump
321 .. 1 clump
Find the mean number of clumps and it is 11⁄6 mean number of clumps. Coscott’s solution gives 10⁄6.
Fix?
My solution gives 11⁄6
Dang you are right.
Coscott’s solution also wrong for N=4, actual solution is a mean of 2, Coscott’s gives 25⁄12.
4 with prob 1⁄24, 3 with prob 6⁄24, 2 with prob 11⁄24, 1 with prob 6⁄24
Mean of 25⁄12
How did you get 2?
Must have counted wrong. Counted again and you are right.
Great problems though. I cannot figure out how to conclude it is the solution you got. Do you do it by induction? I think I could probably get the answer by induction, but haven’t bothered trying.
Take the kth car. It is at the start of a cluster if it is the slowest of the first k cars. The kth car is therefore at the start of a cluster with probability 1/k. The expected number of clusters is the sum over all cars of the probability that that car is in the front of a cluster.
Hurray for the linearity of expected value!
Imagine that you have a collection of very weird dice. For every prime between 1 and 1000, you have a fair die with that many sides. Your goal is to generate a uniform random integer from 1 to 1001 inclusive.
For example, using only the 2 sided die, you can roll it 10 times to get a number from 1 to 1024. If this result is less than or equal to 1001, take that as your result. Otherwise, start over.
This algorithm uses on average 10240/1001=10.228770… rolls. What is the fewest expected number of die rolls needed to complete this task?
When you know the right answer, you will probably be able to prove it.
Solution
If you care about more than the first roll, so you want to make lots and lots of uniform random numbers in 1, 1001, then the best die is (rot13′d) gur ynetrfg cevzr va enatr orpnhfr vg tvirf lbh gur zbfg ragebcl cre ebyy. Lbh arire qvfpneq erfhygf, fvapr gung jbhyq or guebjvat njnl ragebcl, naq vafgrnq hfr jung vf rffragvnyyl nevguzrgvp pbqvat.
Onfvpnyyl, pbafvqre lbhe ebyyf gb or qvtvgf nsgre gur qrpvzny cbvag va onfr C. Abgvpr gung, tvira gung lbh pbhyq ebyy nyy 0f be nyy (C-1)f sebz urer, gur ahzore vf pbafgenvarq gb n cnegvphyne enatr. Abj ybbx ng onfr 1001: qbrf lbhe enatr snyy ragveryl jvguva n qvtvg va gung onfr? Gura lbh unir n enaqbz bhgchg. Zbir gb gur arkg qvtvg cbfvgvba naq ercrng.
Na vagrerfgvat fvqr rssrpg bs guvf genafsbezngvba vf gung vs lbh tb sebz onfr N gb onfr O gura genafsbez onpx, lbh trg gur fnzr frdhrapr rkprcg gurer’f n fznyy rkcrpgrq qrynl ba gur erfhygf.
I give working code in “Transmuting Dice, Conserving Entropy”.
I will say as little as possible to avoid spoilers, because you seem to have thought enough about this to not want it spoiled.
The algorithm you are describing is not optimal.
Edit: Oh, I just realized you were talking about generating lots of samples. In that case, you are right, but you have not solved the puzzle yet.
Ebyy n friragrra fvqrq qvr naq n svsgl guerr fvqrq qvr (fvqrf ner ynoryrq mreb gb A zvahf bar). Zhygvcyl gur svsgl-guerr fvqrq qvr erfhyg ol friragrra naq nqq gur inyhrf.
Gur erfhyg jvyy or va mreb gb bar gubhfnaq gjb. Va gur rirag bs rvgure bs gurfr rkgerzr erfhygf, ergel.
Rkcrpgrq ahzore bs qvpr ebyyf vf gjb gvzrf bar gubhfnaq guerr qvivqrq ol bar gubhfnaq bar, be gjb cbvag mreb mreb sbhe qvpr ebyyf.
You can do better :)
Yeah, I realized that a few minutes after I posted, but didn’t get a chance to retract it… Gimme a couple minutes.
Vf vg gur fnzr vqrn ohg jvgu avar avargl frira gjvpr, naq hfvat zbq 1001? Gung frrzf njshyyl fznyy, ohg V qba’g frr n tbbq cebbs. Vqrnyyl, gur cebqhpg bs gjb cevzrf jbhyq or bar zber guna n zhygvcyr bs 1001, naq gung’f gur bayl jnl V pna frr gb unir n fubeg cebbs. Guvf qbrfa’g qb gung.
I am glad someone is thinking about it enough to fully appreciate the solution. You are suggesting taking advantage of 709*977=692693. You can do better.
You can do better than missing one part in 692693? You can’t do it in one roll (not even a chance of one roll) since the dice aren’t large enough to ever uniquely identify one result… is there SOME way to get it exactly? No… then it would be a multiple of 1001.
I am presently stumped. I’ll think on it a bit more.
ETA: OK, instead of having ONE left over, you leave TWO over. Assuming the new pair is around the same size that nearly doubles your trouble rate, but in the event of trouble, it gives you one bit of information on the outcome. So, you can roll a single 503 sided die instead of retrying the outer procedure?
Depending on the pair of primes that produce the two-left-over, that might be better. 709 is pretty large, though.
The best you can do leaving 2 over is 709*953=675677, coincidentally using the same first die. You can do better.
It is interesting to contemplate that the almost fair solution favors bob:
Bob counts the numbers of apples in 1st room and accepts it unless it has zero apples in it, in which case he rejects it.
If he hasn’t rejected room 1 he counts the apples in 2 and if it is more than in 1 he accepts it else he rejects it.
For all possible numbers of apples in rooms EXCEPT one room has zero apples, Bob has 50% chance of getting it right. But for all possible number of apples in rooms where one room has zero apples in it, Bob has 5⁄6 chance of winning and only 1⁄6 chance of losing.
I think in some important sense this is the telling limit of why Coscott is right and how Alice can force a tie, but not win, if she knows Bob’s strategy. If Alilce knew Bob was using this strategy, she would never put zero apples in any room, and she and Bob would tie, i.e. Alice was able to force him arbitrarily close to 50:50.
And the strategy to work relies upon the asymmetry in the problem, that you can go arbitrarily high in apples but you can’t go arbitrarily low. Initially I was thinking Coscott’s solution must be wrong, that it must be equivocating somehow on the fact that Alice can choose ANY number of apples. But I think it is right, but that every strategy Bob uses to win can be defeated by Alice if she knows what his strategy is. I think without proof, that is :)
Right about what? The hint I give at the beginning of the solution? My solution?
Watch your quantifiers. The strategy you propose for Bob can be responded to by Alice never putting 0 apples in any room. This strategy shows that Bob can force a tie, but this is not an example of Bob doing better than a tie.
Right about it not being a fair game. My first thought was that it really is a fair game and that by comparing only the cases where fixed numbers a, b, and c are distributed you get the slight advantage for Bob that you claimed. That if you considered ALL possibilities you would have not advantage for Bob.
Then I thought you have a vanishingly small advantage for Bob if you consider Alice using ALL numbers, including very very VERY high numbers, where the probability of ever taking the first room becomes vanishingly small.
And then by thinking of my strategy, of only picking the first room when you were absolutely sure it was correct, i.e. it had in it as low a number of apples as a room can have, I convinced myself that there really is a net advantage to Bob, and that Alice can defeat that advantage if she knows Bob’s strategy, but Alice can’t find a way to win herself.
So yes, I’m aware that Alice can defeat my 0 apple strategy if she knows about it, just as you are aware that Alice can defeat your 2^-n strategy if she knows about that.
What? I do not believe Alice can defeat my strategy. She can get arbitrarily close to 50%, but she cannot reach it.