Two neat puzzles I learned recently. If you already know the answers, people don’t just blurt them out (without spoiler boxes), to allow people the fun of discussing them:
(1) Ten people are sitting in a circle. One of them is holding a valuable object. Then they begin doing the following: whoever is holding the object flips a coin. Heads they pass it left, tails they pass it right. The continue to do so until there’s only one person left who has NOT touched the object. That person keeps the object.
The question is: which person, or persons, (based on their starting position), is most likely to end up with the object? And how likely is that? (The person who starts out holding it is already eliminated and can never end up with it.)
(2) There are twenty prisoners in a special jail. The warden gathers them all together in a room. In that room is a table, in the center of which is a coin, currently showing heads. He says “starting tonight, I’m doing a new thing… every night, I will roll a twenty sided die, picking one of you at random. I will escort that person into this room. They can look at this table, and look at the coin. They can then choose to flip the coin over, or not. They can not touch or change anything else. Then they can, if they wish, announce that they believe that every prisoner has been selected at least once. If they announce that, and they are correct, then you can all go free. If they announce that, and they are wrong, I will kill you all. Now, you have an hour to discuss a strategy… after that you will be locked in your cells with no way to communicate with each other at all, and no way to see who is being selected”. (The prisoners do have the ability to tell day from night, and thus can count how many nights have passed.)
What’s a strategy the prisoners can use to guarantee that (a) they will not make the announcement incorrectly, and (b) after enough time passes, the probability that they will be able to make the announcement correctly approaches 100%? (Note: it does not need to guarantee that they make the announcement correctly the first time it is in fact correct to do so.)
The coin is likely to stay near the starting position, and the further away less likely. So the person opposite the starting person is more likely to be the last …just a little bit more likely than others. 20% for opposite and 5% for guy near. ? something do with poissons distribution.
They agree to turn the coin 10 degrees the first time they are selected, so when the person sees its turned well past 200 degrees, they must have all been selected (or won the coin toss ? ) once ?
The significance of the coin toss isn’t stated, but even if it means they can only announce anything if they win the coin toss, well they only turn the 10 degrees if they win the coin toss. Don’t know whether the rules specific who returns the coin to the table… it all goes wrong if the warden decides to return the coin to the table without realising it was an ambiguity of his game. Perhaps they can put a mark on the table instead. Its unclear what happens, would the warden then be allowed to polish the table to remove the mark ?
Obviously the more days delayed after the first 21 or first 40 or first 100, the closer to 100% the chance.Knowing for sure its 100% requires some way to obtain information about the previous selections and coin tosses. If there is some information they can obtain, they should be able to know its 100%, so why ask about probabilities.
If they agree on all but one committing suicide, then the last remaining one will know he is the last remaining one.
Nothing in the description indicates that they know the original angle of the coin or that they’re allowed to rotate it without flipping it. Try thinking inside the rules of the puzzle rather than cheap shortcuts.
For 1 I’m going to guess it’ll be something counter-intuitive, like the guys directly adjacent to the first guy are the most likely to get it as it’s more likely to go round without ever hitting them than to oscillate enough for the 4 step and 5 step away guys to get a chance. The guy 5 steps away is SOL as it would have to reach a 4 step guy, then go all the way back around for him to get a chance.
I think it is probably the people either side of the person starting with the gift as the probability of someone winning is the probability that the gift reaches the person to one side of them and then reaches the person to the other side of them without going through them.
For the second one:[spoiler]This is a very slow method, but should eventually work if the die is fair.
The prisoners are numbered 1-20. We will put them on a repeating 20-day “month”, with the days also numbered 1-20.
The rules are:
If prisoner 1 is called in on day 1, then he sets the coin to heads. Everyone else sets it to tails.
If prisoner 20 is called in on day 20, and the coin is currently heads, then he calls it: all prisoners have been called in.
On all other days: if the day of the month doesn’t match the prisoner number, then set it to tails.
Basically, if the prisoners are called in exactly 1-20 order, aligned with the days of the month, then the coin will stay heads the whole time and they go free. If there’s any mismatch, the coin will turn tails until the month resets.
This only works in like 1 out of 20[sup]20[/sup] months, but hey, it’s something…[/spoiler]
Second puzzle:
The first prisoner is designated the counter. He turns the coin to heads. Every prisoner that comes in thereafter, if the coin is heads he turns it to tails. If it is already tails he leaves it.
When the first prisoner is called again, he notes if the coin has been flipped to tails. if it is, he flips it back to heads.
Every prisoner (except the counter) is told to flip the coin only once (i.e. if they are called in for the second time but they already flipped it, they leave it alone).
Once the counter has reset the coin 19 times, he knows with 100% certainty that every prisoner has been to the room (some undoubtedly have been more than once). He himself is the 20th.
Someone with better math skills than me can check me, but this should take approximately 400 days (20x20).
That’s a somewhat worse version of the solution I came up with, which is itself not the optimal solution. My version also takes advantage of 20-day months, but doesn’t pre-number the prisoners. Basically on day one of the month, whoever was called flips it to heads. Then, any time someone is called for the second time in the same 20-day-month, they flip it to tails. Then if someone is called on the 20th day of the month, and they weren’t called previous that month, and the coin is heads, then everyone must have been called exactly once that month. So instead of requiring the month to be 1-20 in order, it just requires the month to be each prisoner, exactly once. So more likely by a factor of 20!, but still not very efficient.
Problem (1) [SPOILER]Each person, except the one eliminated at the beginning, is equally likely to win!
Consider the person at position n. Eventually the jewel will arrive at either the person immediately to n’s left or the person to n’s right. Wlog suppose it arrives first at n’s left. Player’s only chance is that, after that arrival, the jewel will end up going clockwise all the way around to n’s right before penetrating counter-clockwise to n. What is that chance? It is 1/(M-1) where M is the number of seats at the table but we needn’t even prove that! It is enough to note that this chance is independent of n.
Yes, depending on n, it may be much more likely that we get to n’s left before n’s right but who cares! Once there, the subsequent chance of success is the same either way.[/SPOILER]
Problem (2) Appoint one prisoner the Counter. Each other prisoner will always leave the coin unchanged except for the very first time he sees heads — then he changes it to tails. The Counter is the only one who turns the coin to heads and he does this every chance he gets. Once he’s seen his 19th tails, he knows that every other prisoner has acted. (In simulation, the prisoners are freed on average after 89.9 days.)
[spoiler]A better way is to have 1 Master Counter and 4 Deputy counters, and have phases: For example phase 1=200 days, phase 2=100 days, phase 1 continued=50 days, phase 2 continued=25 days, phase 1 continued=50 days, phase 2 continued=25 days etc. I’m sure the timeframe can be much better balanced.
At the beginning of all phases the coin is set to heads.
During phase 1 all non-counters turn the coin from heads to tails if they have never done so and all counters move the coin from tails to heads until they’ve counted 3 non counters. During phase 2 all deputy counters move the coin from heads to tails if they’ve never done it, and the master counter moves it from tails to heads until he’s counted the 4 deputy counters at which point he announces. If the coin is tails on the last day of a phase then the person who is there on that day takes on the uncounted role in addition to his own.[/spoiler]
Are these special prisoners who’ve demonstrated the ability to trust other prisoners? … the first one in may think dying is a small sacrifice to kill them other 19 bastards …
This is a clearly impossible figure. Under this system the counter needs to visit a minimum of 19 times, which will take a average of 380 days. Of couse, the likleyhood of the counter managing to successfully count on every occasion he visits is pretty small, so you’ll need to add a few more visits into the average.
Ouch! My sense of smell is almost gone, and now this. :eek:
[SPOILER]In the “simulation,” prisoners were happily “checking in” whether the coin was heads-up or not. :smack:
I’d computed by hand that 4 days average are needed for the 2-prisoner case, and confirmed that the simulator produced that answer. But the bug doesn’t manifest until N>2. When I was a professional programmer I was more reliable than this, believe me! :o
Instead of simulating, here’s a formula, I think: When 20 prisoners use the method of #10, escape requires on average 20 * (19 + 1 + 1/2 + 1/3 + 1/4 + … + 1/19) ~= 450.95 days [/SPOILER]
By the way, there is an aspect of Problem (1) I should mention before it causes confusion.
[SPOILER]Supposing the jewel starts at person 3, everyone except person 3 has a 1/9 chance of winning as I showed before.
Suppose the jewel then passes to person 4. Persons 5, 6, 7, 8, 9, 10, and 1 each still have a 1/9 chance of winning by the same argument as before. Persons 3 and 4 have zero chance. So person 2 now has a 2/9 chance! — the chances must sum to 1. If the jewel then passes to person 5 (and then 6), person 2’s chance goes up to 3/9 (and then 4/9). What gives?
In the cases we considered where the chance is 1/9, person n succeeds only if the jewel passes to person (n-1) and person (n+1) without reaching person n. But person 2 in the above scenario doesn’t require that the jewel come around to kill person 3 — that guy is already dead.[/SPOILER]
umm…i gave this virtually exact solution in post #8, along with an estimate of the amount of time it would take that turns out to be pretty close to the one given above. Where’s the love?
The solutions are not identical. The difference is that you specified the first prisoner called is the counter, which is valid because all prisoners know which the first day is.
The solution in 10 involved all the prisoners agreeing on a single prisoner being the counter in advance, and to basically do nothing useful until that prisoner is randomly called.
Your solution is **better **than the solution as stated in post #10 in 19 of 20 trials, and identical on the scenario where the agreed prisoner happens to be called first.