Nitpick: Isn’t it #10 which is slightly better than #8? In the former, there is a 95% chance the first turn will begin one of the 19 required cycles, while in the latter, the first turn is always wasted. (The coin starts off heads.)
The way I feel after I’ve been locked in a dungeon for several years, delirious and easily confused, I think prisoners should pick a clear-headed guy with good memory rather than leaving the selection of Counter to chance. 
A way to improve on this, but not as good as the multi-phase plan is to have an initial 20 day counter choosing ceremony. During the first 20 days the first person to come in for the second time turns the coin to tails, declares himself the counter and counts all the people who have come in. Anybody who comes in for the first time during the first 20 days can leave the coin on heads knowing they will be counted. If the guy who comes in on day 20 sees a head he can immediately declare.
Yeah, I guess you’re right. Though, to quibble about the quibble, the warden very carefully specified that the process didn’t start until that night, and didn’t guarantee that the coin would be undisturbed prior to that time.
Or it could be that I missed the part about them all being shown the coin in advance 
I think you need to be specific that [spoiler]if the counter gets selected a third time in the first 19 days, he leaves it on tails until the first time he gets selected after the initial 20 days are up. Say the counter gets selected on days 3, 7, and 16. He’s turned the coin to tails on day 7. If he turns it back to heads on day 16:
Excellent! Very neat.
Note that the selected counter need never restore heads; just reverse the subsequent heads/tail sense compared with prior methods. Prisoners who didn’t show up before the switch to tails, will flip to heads the first time they enter the room Day 20 or later. (They needn’t wait for Day 21.)
Assuming my new simulator is correct (maybe a fifty-fifty chance, though I did attempt confirmation for NP=3) here are average days till freedom for the method in #10 and Mr Shine’s method respectively.
NP = 2) 4 4
NP = 3) 10.50 8.833
NP = 4) 19.33 15.724
NP = 20) 450.95 378.92
Note that the selected counter need never restore heads; just reverse the subsequent heads/tail sense compared with prior methods. Prisoners who didn’t show up before the switch to tails, will flip to heads the first time they enter the room Day 20 or later. (They needn’t wait for Day 21.)
Counterexample. with N=3:
1123
Player 1 does nothing.
Player 1 becomes the counter, flips the coin to tails.
Player 2 on day 3 knows it’s now the equivalent of day 20 for N=3, will flip the coin to heads.
Player 3 walks in the room for the first time on day 3 or later. He cannot follow your instructions to flip to heads, as the coin is already heads. Your method, as stated, fails.
Presumably you really meant the first time a non-counter enters after N=20* and sees a tails* he would flip to heads, but the fact that you didn’t specify that in your description makes me worry that you didn’t specify that in your code…
I don’t understand what you mean by ‘just reverse the subsequent heads/tail sense compared with prior methods’- you would need to specify what that means once you clarify what you really meant by your contradictory second sentence. If the counter does anything other than always leave the coin as a tails it appears to waste time, as no one other than the counter is allowed to flip a heads to a tails in this ruleset.
Some Call Me… Tim: “Counterexample”
Beginning Day 20, with Counter selected, the residual players take turns turning the coin to heads. The other players need to wait for this to be acknowledged — for Counter to restore tails — before they can signal their presence.
In #10, counter is the only one to flip to heads; non-counters flip to tails. This is() reversed in the improved method. (- instead, we could have dictated that Day 1 guy always set tails, killing two birds.)
This is just the normal need to wait. Player 2’s heads have not yet been acknowledged by Counter (Player 1) so Player 3 cannot act yet.
There are no less than eight possibilities for the Day 20 event!
[ul][li]First entry, Heads — signal warden for release![/li][li] First entry, Tails — flip to Heads, as a signal to Counter[/li][li] Second or subsequent entry seeing T-…-T — Flip to Heads, as a signal to Counter[/li][li] Second or subsequent entry seeing H-T — do nothing (and continue doing nothing for duration)[/li][li] Second or subsequent entry seeing T-…-H — do nothing (but flip to H next time you see T)[/li][li] Second entry, seeing H-H — flip to Tails, become Counter[/li][li] Third or subsequent entry, seeing H-H-T(…T) — you are Counter, do nothing.[/li][li] Third entry, seeing H-H-H — impossible!, one of fellow inmates has forgotten the protocol.[/li][/ul]
My comment applied to the 2nd and 3rd cases shown. The only “specialness” is that you can begin the signalling Day 20; there’s no need to wait for Day 21. (You cannot begin Day 19: you’d interfere with the Day 20 inferences.)
My simulator might be broken, but it did show 8.8333 as expected time to freedom for N=3 players. Are both my simulator and manual calculation wrong?
[SPOILER]Everything is fine on Day 20 itself, because the only scenario in which a non-counter will enter to find a heads is case 1, which is an instant win.
If the coin is flipped to heads on day 20, and another non-counter prisoner is selected on day 21, then your specification is indeed wrong. You made the claim that “Prisoners who didn’t show up before the switch to tails, will flip to heads the first time they enter the room Day 20 or later. (They needn’t wait for Day 21.)” I have demonstrated that it can be impossible a prisoner on day 21 to take the action that you specifically claimed that they do. Your code does not match your claim of how it works, (as that behavior is impossible) and is thus wrong in the sense that it does not act in the manner that you claimed that it does.
It’s fine if you want to correct your specification of what your code does. It’s not so fine to shift the goalposts to claim you were right all along.
It is possible that your code deviated from your claim of how it behaves in such a way that it fits the requirements of the puzzle, however, so it may be correct in a “two wrongs make a right” sense.
[/SPOILER]
I’m not sure what you’re quibbling about. I wrote "“Prisoners who didn’t show up before the switch to tails, will flip to heads the first time they enter the room.” Would your complaint have disappeared if I had suffixed “when tails are shown” to the sentence you dislike? I could have been more precise, but anyone following the argument realizes that “switching heads to heads” — if that’s what you claim I was implying — will not constitute a usable signal.
i think we should all remember that the prisoners only have an hour to work out and agree upon their plan…best keep it as simple as possible.
Sent from my SM-G935V using Tapatalk
A clarification regarding Problem 1: Suppose a person gets the object in a particular round (and this is not the last round). Now, do they immediately exit the circle; or do they continue to sit in the circle and participate in the play (even though they can never win the game)? In other words, does the circle keep shrinking as the game proceeds? My reading of the question is that the circle remains the same, but the alternative scenario is reasonable too.
Sent from my Nexus 5X using Tapatalk
In that version
the success chances for, say N=7, are in the ratio 1:5:10:10:5:1 where those ratios are the (N-1)th row of Pascal’s triangle.
No, everyone remains in the circle the entire time (including the guy who started out holding it).
Your claim that prisoners took an action that was not possible under some circumstances.
Yes, and it is impossible for them to do this if the coin shows heads the first time they enter the room. They simply cannot take the action that you flatly claim that they do.
Yes, as I stated in post 26 appending the clause “and sees a tails” would have fixed the problem, and the above paraphrase of my post would work as well. Had you made an accurate statement in the first place I would not have needed to point out your inaccuracy.
No, and to use the scare quotes that you seem to enjoy so much, I made no claims whatsoever about what you were “implying”. I simply pointed out that your unequivocal claim that every such prisoner would “flip to heads the first time they enter the room” was nonsense as this action was sometimes impossible for a prisoner to do. You are correct that anyone following the argument would find it as obvious as I did that the behavior you claimed for the prisoners was impossible.
I should also point out that the start of this was in response to a post that purported to describe what some code had been written to do… my mindset when reading a description of code is much more literal and strict with construction than I would be when reading something in a casual non-coding context. It did read like you’d made a mistake and assumed within your code that they would be able to flip the coin the first time they entered the room.
“scare quotes that you seem to enjoy so much … whatsoever … simply … unequivocal … nonsense … impossible … obvious … impossible.”
Wow. Did I say something to offend you?
On top of “all” else, you “needed” to speak of “me” using “scare” quotes, despite that my quotes weren’t scary — they surrounded specific phrases to be inserted into prior sentences. Isn’t that a normal non-scary use of quote marks for clarity?
BTW, my description of the policy was never intended to be a description of the simulating code I wrote — the latter was simplified to take advantage of symmetries and to bypass unnecessary details. That would, in principle, make it more likely to be buggy, so you might have contributed by writing your own simulator to confirm my result, but I guess you felt your time was better spent composing the post “scare quotes that you seem to enjoy so much … whatsoever … simply … unequivocal … nonsense … impossible … obvious … impossible.”
Yeah, now I see how your use of quotation marks was totally necessary and not at all sarcastic.
Sorry, quoting ‘counterexample’ wasn’t intended to be sarcastic or scary — I wanted to make the context of my spoiler clear … I guess I should have set up a quote box just for that one word.
I’m sorry for the misunderstanding. Your fundamental complaint was about the phrasing of my post (and your post did make that clear); I tried to clarify the algorithm. That could have ended the discussion but you followed with (‘shift the goalposts to claim you were right all along … so it may be correct in a “two wrongs make a right” sense’). I found that annoying and over-reacted.
Sorry.
To recapitulate the proposed solutions to Problem (2).
In #6, Dr. Strangelove posts the first solution, but it takes over a quintillion days on average for success.
In #8, turtlescanfly found the basic counting algorithm on which several other methods are based. This method uses on average 451.9 days
In #10 I improved the method of #8 from 451.9 to 450.95 days (while claiming a much better performance which Mr. Shine refutes in #13).
In #11, Mr. Shine proposes a complicated version of #10. AFAIK no one has yet tuned this method or calculated its performance.
In #22, Mr. Shine shows a clever way to improve #10.
In #25 I clarify the method of #22 and claim 378.92 days as its expected cost. (My clarification wasn’t clear – thanks to Some Call Me… Tim for clearing that up).
Left to do:
In a variation of Problem (2), prisoners are unable to count turns (perhaps because the warden calls a variable number of prisoners each night). I think that among solutions proposed so far, only #10 handles that case.
I’ll try to make amends for my errors and unclear posts. I think we can un-Spoiler #11 by now.
Mr. Shine’s method in #11 can get complicated. The special case “coin is tails on the last day of a phase” can even lead to one non-counter “buffering” all the non-counters’ signals and then, as he signals these on one at a time, he can end up buffering deputy counters’ signals as well. (In fact, it’s possible that he can deduce all 20 prisoners have flipped before the master counter does, but that is extremely rare and my simulation doesn’t check for it.)
As Mr. Shine provides, master counter also performs the normal duties of a deputy counter in addition to his main duty. The counters can be assigned different goals, but in my simulations I kept the deputies’ goals fixed at k (k = 7-d, where d is number of deputies). The master counter’s goal is to count d deputies and m non-counters where m = 19 - d*(k+1).
I tried 3, 4, and 5 deputy counters. Here are the expected number of days until success for the methods, from best to worst. (The standard deviation of number of days was about 100 in most cases, somewhat less for method #10.)
() 364.4: Three deputy counters, each waiting for four signals. (Master waits 4+3)
() 366.4: Four deputy counters, each waiting for three signals. (Master waits 3+4)
() 378.9: Method in #25.
() 379.3: Five deputy counters, each waiting for two signals. (Master waits 4+5)
(*) 451.0: Method in #10.
Of course I devoted some effort to tuning phase durations as Mr. Shine suggested. The best durations I tried for the winning Three-deputy method were
This simulation was significantly more complicated than the previous ones I ran. I’ll guesstimate the chance of a bug as 49.9%. 