btilly wrote:

If the first prisoner enters and sees it on, that prisoner remembers the fact, sees that it is not off, and does not flip it.

So how does the first prisoner upon seeing the switch OFF know if the Counter has already been there and flipped it down? Doesn't he have to flip it ON?  If he does this, should he count it as his "one?"  Should the Counter, on seeing the switch ON when he first visits the room assume that someone has been there and Count it?

There is no assumption about order of prisoners.  If, between visits by the counter, 1 or 50 visits by other prisoners are made, it is immaterial.  At most 1 will decide to flip the switch from off to on, at which point nobody else touches it.

Sorry, I missed the part about the Counter flipping the switch ON with every visit.

M57 wrote:

btilly wrote:

If the first prisoner enters and sees it on, that prisoner remembers the fact, sees that it is not off, and does not flip it.

So how does the first prisoner upon seeing the switch OFF know if the Counter has already been there and flipped it down? Doesn't he have to flip it ON?  If he does this, should he count it as his "one?"  Should the Counter, on seeing the switch ON when he first visits the room assume that someone has been there and Count it?

No.  The counter knows that he is the first to change the switch.  Whatever it is when he's first there, is what the warden set it to.

If it is on, then the counter hopes that someone already saw it was on, and has a chance to be counted by his next visit when he turns it off.  On average 11 people saw that, and 5-6 of them will return before he does, so there are good odds that someone will flip it on before he gets back. :-)

There is no assumption about order of prisoners.  If, between visits by the counter, 1 or 50 visits by other prisoners are made, it is immaterial.  At most 1 will decide to flip the switch from off to on, at which point nobody else touches it.

Sorry, I missed the part about the Counter flipping the switch ON with every visit.

The counter flips with every visit.  Off to on (to let people know he was there) or on to off (so someone else can be counted).  Eventually he'll get everyone.

M57 wrote:

Yes,  you are right about the need for 2 trips (you all but solved the puzzle with that idea), but do you agree that the count is extremely unlikely to reach 44? ..and there's no way it can get to 45.  

Like you said, we are counting differently.  I am counting the first "on" whether it's real or not, you're voiding it.  So, for my way of counting the counter will always reach 44 and sometimes 45, except,he never needs to reach 45 as 44 is always enough regardless if the first count was real or not.  For your way of counting the first "on" is voided (unless the counter is the first to visit and witnesses it to be off, then the first on he sees now counts).  By voiding the first on, however, your count is always one less but to the same end whereby you will always reach 43 and sometimes 44, but, since the first on, the suspect on, is voided, 43 suffices by your count.

btilly wrote:

The other solution is that the counter always flips the switch, and keeps track of how many times it was moved from off to on.  When that hits 22, they stop.

The other prisoners turn it from off to on exactly once, only if they have previously seen it on.

This means that the other prisoners will not move the switch until after the counter is known to have entered, and therefore every prisoner will be properly counted by the counter.

I'm still trying to wrap my brain around your solution btilly.

The counter always flips the switch and counts 22 times from off to on.

Every prisoner turns it on once but only if they have previously seen it on.

So, explain me this... In all the wardens randomness, what if one prisoner comes in at all the wrong times such that he does not see it "on" prior to the counter switching it off (if that was even the case and it was not off to start), and then always comes in when it is off from that point forward, ie, just after the counter and/or any number of prisoners who had already turned it on previously such that they all leave it off.  By your method isn't it theoretically possible to have the switch turned off such that 21 prisoners have already turned it on and been counted and leave it off and the one remaining has never seen it on and therefore has not satisfied the condition of already seeing it on so that he may turn it on himself?  As of such the switch never gets turned on by the final prisoner to be counted and they serve life sentences.

I suppose at some point of "staleness" the counter could then turn it on himself and hope that the one remaining prisoner remaining to be counted sees it on before the counter turns it off again... But that would not be a sure thing and they could go on like that for quite some time, if not forever.

btilly wrote:

M57 wrote:

btilly wrote:

If the first prisoner enters and sees it on, that prisoner remembers the fact, sees that it is not off, and does not flip it.

So how does the first prisoner upon seeing the switch OFF know if the Counter has already been there and flipped it down? Doesn't he have to flip it ON?  If he does this, should he count it as his "one?"  Should the Counter, on seeing the switch ON when he first visits the room assume that someone has been there and Count it?

No.  The counter knows that he is the first to change the switch.  Whatever it is when he's first there, is what the warden set it to.

If it is on, then the counter hopes that someone already saw it was on, and has a chance to be counted by his next visit when he turns it off.  On average 11 people saw that, and 5-6 of them will return before he does, so there are good odds that someone will flip it on before he gets back. :-)

I'm refering to the VERY first prisoner in the room.  When he enters the room, he doesn't know he's the first prisoner. IF hes sees the switch OFF, how does he know that the Counter didn't already move the switch UP (Initiating the count), and then a someone else moved it DOWN?  If he moves it UP (and counts it), and the Counter has not yet entered the room, then his 'tick' will never be counted.

M57 wrote:

btilly wrote:

M57 wrote:

btilly wrote:

If the first prisoner enters and sees it on, that prisoner remembers the fact, sees that it is not off, and does not flip it.

So how does the first prisoner upon seeing the switch OFF know if the Counter has already been there and flipped it down? Doesn't he have to flip it ON?  If he does this, should he count it as his "one?"  Should the Counter, on seeing the switch ON when he first visits the room assume that someone has been there and Count it?

No.  The counter knows that he is the first to change the switch.  Whatever it is when he's first there, is what the warden set it to.

If it is on, then the counter hopes that someone already saw it was on, and has a chance to be counted by his next visit when he turns it off.  On average 11 people saw that, and 5-6 of them will return before he does, so there are good odds that someone will flip it on before he gets back. :-)

I'm refering to the VERY first prisoner in the room.  When he enters the room, he doesn't know he's the first prisoner. IF hes sees the switch OFF, how does he know that the Counter didn't already move the switch UP (Initiating the count), and then a someone else moved it DOWN?  If he moves it UP (and counts it), and the Counter has not yet entered the room, then his 'tick' will never be counted.

By btilly's way only the counter moves it down and the counted only move it up after seeing it up previously, so, by the way I understand it, what you're saying can't happen.

http://anttila.ca/michael/100prisoners/

berickf wrote:

btilly wrote:

The other solution is that the counter always flips the switch, and keeps track of how many times it was moved from off to on.  When that hits 22, they stop.

The other prisoners turn it from off to on exactly once, only if they have previously seen it on.

This means that the other prisoners will not move the switch until after the counter is known to have entered, and therefore every prisoner will be properly counted by the counter.

I'm still trying to wrap my brain around your solution btilly.

The counter always flips the switch and counts 22 times from off to on.

Every prisoner turns it on once but only if they have previously seen it on.

So, explain me this... In all the wardens randomness, what if one prisoner comes in at all the wrong times such that he does not see it "on" prior to the counter switching it off (if that was even the case and it was not off to start), and then always comes in when it is off from that point forward, ie, just after the counter and/or any number of prisoners who had already turned it on previously such that they all leave it off.  By your method isn't it theoretically possible to have the switch turned off such that 21 prisoners have already turned it on and been counted and leave it off and the one remaining has never seen it on and therefore has not satisfied the condition of already seeing it on so that he may turn it on himself?  As of such the switch never gets turned on by the final prisoner to be counted and they serve life sentences.

It is statistically impossible for this to happen.  Just like it is statistically impossible in your solution for the counter to never visit again, leaving one of the prisoners uncounted.

btilly wrote:

berickf wrote:

btilly wrote:

The other solution is that the counter always flips the switch, and keeps track of how many times it was moved from off to on.  When that hits 22, they stop.

The other prisoners turn it from off to on exactly once, only if they have previously seen it on.

This means that the other prisoners will not move the switch until after the counter is known to have entered, and therefore every prisoner will be properly counted by the counter.

I'm still trying to wrap my brain around your solution btilly.

The counter always flips the switch and counts 22 times from off to on.

Every prisoner turns it on once but only if they have previously seen it on.

So, explain me this... In all the wardens randomness, what if one prisoner comes in at all the wrong times such that he does not see it "on" prior to the counter switching it off (if that was even the case and it was not off to start), and then always comes in when it is off from that point forward, ie, just after the counter and/or any number of prisoners who had already turned it on previously such that they all leave it off.  By your method isn't it theoretically possible to have the switch turned off such that 21 prisoners have already turned it on and been counted and leave it off and the one remaining has never seen it on and therefore has not satisfied the condition of already seeing it on so that he may turn it on himself?  As of such the switch never gets turned on by the final prisoner to be counted and they serve life sentences.

It is statistically impossible for this to happen.  Just like it is statistically impossible in your solution for the counter to never visit again, leaving one of the prisoners uncounted.

I'm not saying that he's not visiting again, I'm saying that one prisoner might only come when the switch is down (off), which seems possible to me.  The counter might eventually solve this by turning it on with the hope that the last remaining prisoner will then see it on and know it's time for him to flip it on after the counter turns it back off again, but, as statistically unlikely as this might be it still seems possible using brute force logic.  Maybe you can explain how it's statistically impossible for him to always encounter the switch down though instead of just being statistically improbable.  Thanks.

Remember, the counter always flips the switch.  So after every 2 visits from the counter, the switch has been up and down.  And the last prisoner has even odds of seeing each of those states.

So after 40 visits from the counter, the odds of the last prisoner failing to see it on are under 1/1000000.  After another 40 visits, the odds of the last prisoner not getting counted are under 1/1000000.  For any probability of success that you want, there is a finite number of visits that gets you there.  So in the long run, failure to succeed is statistically impossible.

btilly wrote:

Remember, the counter always flips the switch.  So after every 2 visits from the counter, the switch has been up and down.  And the last prisoner has even odds of seeing each of those states.

So after 40 visits from the counter, the odds of the last prisoner failing to see it on are under 1/1000000.  After another 40 visits, the odds of the last prisoner not getting counted are under 1/1000000.  For any probability of success that you want, there is a finite number of visits that gets you there.  So in the long run, failure to succeed is statistically impossible.

It has been a long time since I studied or even utilized statistics, but I tend to think that 1/1000000 is statistically improbable, but not statistically impossible.  Anyway, no worries, it looks like at some point the prisoner should find it up and then know to flip it up himself to finish the count upon the next time he's visiting and finds it down.  So, one method has a more open ended termination that runs on 1/100000 cycles of failure but with less total counts whereas the other has a concrete termination but more total counts.  According to Amidon's post there are quite a number of ways to solve this puzzle, many of which were way over my head, but I'd still like to understand yours.

So, out of curiosity, how do you get 1/1000000?  As far as I can tell if the counter leaves it on or off equally the final prisoner to be counted has a 50/50 chance of seeing it when it's on and a 50/50 chance of seeing it when it's off.  Furthermore, in 40 counter visits it'll be on between 20 of those visits when he needs to see it on and off between the other 20 which does him no good.  Every other prisoner has already been counted so they no longer flip that switch at all so we're just down to this switch dance between the counter and the final prisoner to be counted.  For the first half of the solution between these two the final prisoner needs to find it on to know that he can then turn it on himself next time he finds it off, for the second part he needs to find it off so that he can turn it on to complete the count upon the counter's next visit.  So, for a 50/50 probability over 40 cycles with 20 having a real opportunity of finding it on (the other 20 cycles it is off and thus irrelevant) would be what statistically then?  That would be the chance of the final prisoner finding it on to signal him to turn it on himself over a 40 visit cycle by the counter.  Then the same would be applied for him to find it off over the next 40 visits by the counter such that he can then turn it on to complete the count. Again, I'm not saying that it won't solve, but, there does seem to be a small window there to frustrate completion and while being highly unlikely is still possible.  Can you write out the math so I can have a statistics refresher?

Also, and this is me speaking completely from my gut, but if the counter thinks that he might have reached such a conundrum since he knows his count is at 21, couldn't he decide to skew the odds and leave it on for a prolonged period of time, say over 5 visits instead of leaving it equal on/off, and then since the final prisoner to be counted had a higher exposure to see it on couldn't he then leave it off for a prolonged period to give the final prisoner an opportunity to flip it back on and complete the count.  Wouldn't that statistically make it solve faster by increasing the exposure of each needed state at the correct time that it might be needed? Thanks.

I was thinking about it and if the uncounted prisoner has a 50/50 chance of coming when it is on, when he needs it to be on, then, over 40 visits by the counter, and approximately the same by the one who needs to be counted, all things being random, then doesn't that mean that the probability of him finding it on is 50% over the 20 periods when the counter left it on, or 10 of the 40 total visits.  So, wouldn't that be about a 25% chance of finding it in the correct position to proceed to the next step, then a 25% chance of finding it off so as to flip it on over the next 40 visits?

Mind you, I know very little about statistics, so I'm just talking.

For a pair of visits by the counter, there is a period when it is on, and a period when it is off.

In the period when it is on, the uncounted prisoner has 1/2 of not showing, 1/2 of showing at least once, 1/4 of showing at least 2x, 1/8 of showing at least 3x, and so on.  So a pair of visits by the counter gives even odds of the uncounted prisoner seeing the switch on.

It also gives even odds of the uncounted prisoner seeing the switch off.

These are independent.  So in 40 visits by the counter, you have 20 pairs.  In each of which you have even odds of the prisoner showing up.  And these are all independent.

After one pair of visits the odds of the prisoner not seeing it are 1/2.  After the second pair it is half that, or 1/4.  After the third pair it is half that, or 1/8.  And so on.

After 10 pairs we have 1/1024, which is just slightly below 1/1000.  After 20 pairs we have 1/1048576, which is just slightly below 1/1000000, as I said.

And yes, it is possible for the counter to be sophisticated and realize at certain points that it is better to be clever about leaving the switch off a few times because the last prisoner is more likely to have seen it on and be looking for an off rather than vice versa.  But the logic needed to get that right is complex, and the savings tend to be low.

Thanks!

M57 wrote:

I can't imagine that would be helpful.

I keep creating scenarios where 3 people from different groups (with different instructions) visit multiple times in a row.  A person from the fourth group could potentially see the switches in any state depending on who came before them.

So it follows that the only way to a solution that I can imagine involves 2 or three groups at most, and there would have to be a 'group' of one.

Regardless, any solution that I can imagine is broken in the scenario where the warden takes every prisoner to the room except one for 100 or 1000 or 10000 trips.   Obviously, there's no way for the prisoner who has not entered the room to 'signal' that he has not been to the room.

Somewhere in this jumble of thoughts is the crux of it... and also a few wrong answers. But you're so close I can taste it.

btilly wrote:

For a pair of visits by the counter, there is a period when it is on, and a period when it is off.

In the period when it is on, the uncounted prisoner has 1/2 of not showing, 1/2 of showing at least once, 1/4 of showing at least 2x, 1/8 of showing at least 3x, and so on.  So a pair of visits by the counter gives even odds of the uncounted prisoner seeing the switch on.

It also gives even odds of the uncounted prisoner seeing the switch off.

These are independent.  So in 40 visits by the counter, you have 20 pairs.  In each of which you have even odds of the prisoner showing up.  And these are all independent.

After one pair of visits the odds of the prisoner not seeing it are 1/2.  After the second pair it is half that, or 1/4.  After the third pair it is half that, or 1/8.  And so on.

After 10 pairs we have 1/1024, which is just slightly below 1/1000.  After 20 pairs we have 1/1048576, which is just slightly below 1/1000000, as I said.

And yes, it is possible for the counter to be sophisticated and realize at certain points that it is better to be clever about leaving the switch off a few times because the last prisoner is more likely to have seen it on and be looking for an off rather than vice versa.  But the logic needed to get that right is complex, and the savings tend to be low.

Sorry to bother you again btilly.  I'm just trying to fully understand the statistics of this.  Again, my statistics knowledge is pretty much non-existent, but, if in two visits by the counter the chance of the counted finding it in the right state are 0% after one of the counter's visits and 50% after the other, then shouldn't the two combined be 25% of the counted finding it in the correct state and a 75% chance of being in the wrong state?  Sorry to keep asking what are probably stupid questions, but, I was just reviewing and wondering why it was a 1/2 chance of not seeing it in the correct state and not a 3/4 chance of it not being in the correct state since in one of the two cycles he had no chance at all.  I don't think it makes a whole lot of difference to your math, was just a bit puzzled by the 1/2 after the first pair of counter visits?

It is because success does not later become failure.

If you find it in the right state and then the wrong state, you still remember seeing it in the right state that first time.  So any possibility where you succeed at any point is a possibility where you have succeeded.

If I am understanding the discussion correctly. The key to the 'missing' prisoner to finally get counted is not statistics but the definition of random. If it is random, every possible order will occur at some point, including the order where he gets counted. This would be the same as the question of whether the digits in Pi are random (or normal I think they call it). If so then every possible number exists in the digits of Pi, including your phone number, birth date, social security number, and the entire works of Shakespeare encoded into binary.