berickf wrote:

Ok, I thought it out for single switch and still get stuck...

First prisoner goes in.  If the 1st switch (switch on the left) is on (up, whatever), he assumes that it has been turned on previously and flips the other switch.  If it's off/down he turns it on/up.  Since the visits are infinite and random, every prisoner will follow the same except for one who's in charge of turning it off.  Every time he turns it off he knows that at least one new prisoner has visited before him and also makes it possible for a new prisoner to turn it on again after he leaves.  Repeat, count, repeat, count, etc.

Ok, now we have a method of counting, but, we need to address that the switch can be "on" or "off" to start.  This is my stumbling block for the single switch method at this point because, so he doesn't make a mistake he has to assume that it was "on" to start, but if he makes this assumption then he needs his count to reach 23 (once to cancel the on and then 22 prisoners besides himself).  If he reaches 23 then he can confidently tell the warden that everyone has visited at least once.  But, if it was off and someone turned it on before him then he'll only ever reach 22 and he can't be sure because 23 might never come.  So, this method gets stuck half the time, but, maybe someone can figure out a way around this?

that's where i was going back in #184 (although spelled out much cleaner). I haven't seen anything else that improves on this or shows the potential to improve upon it.

btilly wrote:

Would you be OK with another one now, and the answer later?

dunno if we want to confuse things.

honestly though, with all our smart ppl in here not getting it in this amount of time, I'm guessing we're all serving the complete length of our sentences...

I think I have a solution.  with utilizing one switch to do all the work I was stuck because of 22 or 23 counts being required depending on if the switch is up or down to start, but, what if everyone is counted twice?  Then if it's off to start and the first prisoner clicks it on, then the prisoner in charge of turning it off does so, then the next one will turn it on again, eventually the one in charge of turning it off comes along again turns it off and so on and so on until every prisoner has turned it on twice.  Follow this along and if every prisoner flicks it on twice with the switch having started in the off position then eventually the one turning it off will reach 44 meaning that everyone else has visited twice.  If it is on to start then he'd reach 45 by the time everyone came twice, but, since everyone is being counted twice he only need to reach 44 regardless of if it started in the on or off position because whether the switch were on or off to start 44 would mean everyone visited twice if it started off as being off and 21 prisoners visited twice and one visited once if it were on to start, which still satisfies that everyone had visited at least once, including the prisoner who was in charge of turning it off the 44 times.

I'm not sure I understand b's solution, but it did guide me toward my idea for a solution. But I have one more question.

Will the first prisoner to enter the room know that they are the first prisoner?

M57, no.

For the record, berickf's solution is not the one that I knew.

berickf wrote:

Then if it's off to start and the first prisoner clicks it on,  

How does this prisoner know they are the first prisoner?  If the person who is the counter doesn't enter the room for the first 50 visits by other prisoners, how do prisoners know when the count starts?

Can you give an example of the what the first few prisoners do if the switches start A: ON, B: ON.

Here's my solution -- It may be the same as berickf's but I don't think so.

1. One prisoner is designated as the Counter.
2. Prisoners are charged with moving Switch A UP whenever they see it in a DOWN position. They are instructed to do this two times ONLY. Afterward they simply hit switch B whenever they enter the room.
3. The "Counter" flips Switch A DOWN every time he gets to the room, and counts until he has seen Switch A in the UP position 43 times.

If the Counter is certain that he is the first person to enter the room, he can simply make sure that Switch A is in the Down position and only need to see it in the UP position 22 times (with the proviso that each prisoner is instructed to bring Switch A to the UP position ONLY once.

The reason for 43 (and two UPs per prisoner) is that the first prisoner to visit the room (who is unlikely to be the counter) may very well find Switch A in the DOWN position, and he will have no idea if the "Counter" had already put it there.  But no worries; once it is UP, no other prisoner can make this "mistake" because only the Counter can pull it DOWN.

The prisoners don't need to know who is first.

22 prisoners are being counted, one is counting.

If the switch on the left is off then if any of the 22 come in they will turn it on.  If it is already on then they will flip the other and leave.

If the prisoner monitoring the count is the first then if it is on he'll turn it off and count one in his head.  If it is off then he knows that he is the first to visit by default because anyone else would have turned it on and everyone else would have left it on after that by flipping the other switch.

Every time the monitor leaves the switch off then the next prisoner who is still yet to add to his count, be it his first or second time flipping the switch on, will flip it on, after which everyone else will leave it be for the monitor to record that it is on and do his job of recording that prisoners place in the switch room before turning it off again and allowing the next prisoner to be counted.

If a prisoner has already turned the left switch on twice then they will only flip the right switch for all subsequent visits until the monitor has had the opportunity to record 1-2 visits for every prisoner besides himself.

I do realize that by the time the monitor tells the warden that every prisoner has visited at least once that in all likelihood every prisoner would have visited several times, including the monitor who has to visit at least 44 times to count the on switches and more if he returns to find it still off, but, this is the only way I can come up with the monitor knowing with 100% certainty that his job is done.

M57 wrote:

Here's my solution -- It may be the same as berickf's but I don't think so.

1. One prisoner is designated as the Counter.
2. Prisoners are charged with moving Switch A UP whenever they see it in a DOWN position. They are instructed to do this two times ONLY. Afterward they simply hit switch B whenever they enter the room.
3. The "Counter" flips Switch A DOWN every time he gets to the room, and counts until he has seen Switch A in the UP position 43 times.

If the Counter is certain that he is the first person to enter the room, he can simply make sure that Switch A is in the Down position and only need to see it in the UP position 22 times (with the proviso that each prisoner is instructed to bring Switch A to the UP position ONLY once.

The reason for 43 (and two UPs per prisoner) is that the first prisoner to visit the room (who is unlikely to be the counter) may very well find Switch A in the DOWN position, and he will have no idea if the "Counter" had already put it there.  But no worries; once it is UP - only the Counter can pull it DOWN to reset.

 

Yes, you have understood my solution.

berickf wrote:

If it is off then he knows that he is the first to visit by default because anyone else would have turned it on and everyone else would have left it on after that by flipping the other switch.

This is a good point.  But he would still have to count to only 43.

However, the one minor problem with your solution is that if the first prisoner in the room is NOT the Counter, the counter will only count 1 flip for that person.  I.e., the count would never reach forty-four 96% of the time.

M57 wrote:

Here's my solution -- It may be the same as berickf's but I don't think so.

1. One prisoner is designated as the Counter.
2. Prisoners are charged with moving Switch A UP whenever they see it in a DOWN position. They are instructed to do this two times ONLY. Afterward they simply hit switch B whenever they enter the room.
3. The "Counter" flips Switch A DOWN every time he gets to the room, and counts until he has seen Switch A in the UP position 43 times.

If the Counter is certain that he is the first person to enter the room, he can simply make sure that Switch A is in the Down position and only need to see it in the UP position 22 times (with the proviso that each prisoner is instructed to bring Switch A to the UP position ONLY once.

The reason for 43 (and two UPs per prisoner) is that the first prisoner to visit the room (who is unlikely to be the counter) may very well find Switch A in the DOWN position, and he will have no idea if the "Counter" had already put it there.  But no worries; once it is UP, no other prisoner can make this "mistake" because only the Counter can pull it DOWN.

 

Except, the monitor has to count to 44 not 43.  If it was already on and he turned it off before the prisoners started to turn it on then 43-1=42 & 42/2=21.  So, it is possible that only recording 43 up positions could theoretically result in one prisoner being left uncounted.

M57 wrote:

berickf wrote:

If it is off then he knows that he is the first to visit by default because anyone else would have turned it on and everyone else would have left it on after that by flipping the other switch.

This is a good point.  But he would still have to count to only 43.

However, the one minor problem with your solution is that if the first prisoner in the room is NOT the Counter, the counter will only count 1 flip for that person.  I.e., the count would never reach forty-four 96% of the time.

The count will always reach 44 since 22*2=44.  But, if it starts in the on position it can also reach 45.  But, he never has to reach 45 since 44 would still mean that every prisoner has visited at least once even if it started in the on position.  44-1=43.  43/2=21.5.  So, with the switch starting with being on and reaching a 44 count, of the 22 prisoners to be counted by the monitor, 21 prisoners came twice and one only once.

We are "counting" differently..

If the first prisoner (who is not the counter) puts the switch in the UP position, the Counter will have no idea if he is first or not.  Therefore, the Counter can NOT count that as a 'visit.' 

On the other hand, the first prisoner upon finding the switch DOWN MUST throw it UP and MUST count this as his first visit (He can't be sure that the Counter didn't throw it DOWN.  In fact, it is highly likely that the Counter will not ever count the first visit. 

22 prisoners "visiting" twice = 44 visits, - 1 that the the counter is unlikely to see = 43.

M57 wrote:

We are "counting" differently.. 

If the first prisoner (who is not the counter) puts the switch in the UP position, the Counter will have no idea if he is first or not.  Therefore, the Counter can NOT count that as a 'visit.' 

On the other hand, the first prisoner upon finding the switch down MUST throw it up and MUST count this as his first visit.  In fact, it is highly likely that the Counter will not ever count the first visit. 

22 prisoners "visiting" twice = 44 visits, - 1 that the the counter is unlikely to see = 43.

So you're ignoring the first visit by the counter, even though it's still a visit, and in so doing creating an uncounted on (which is most likely in 45 of 46 instances), whereas I'm counting that on and dealing with it.  It makes no difference either way.  But for simplicity I'd sooner have him count every instance of it being on rather then have him ignore the first instance and count from there.  Counted or not, the total instances of the switch being on will be 43 counted +1 ignored or 44 counted.  So, the same.

Anyways, that's why I made it two trips for each, so that if the first on switch is real or fake it becomes irrelevant since 44 (all real)/2=22 and 44-1(fake) = 43 of which 43/2=21.5.  Automatically every prisoner is accounted for either way and takes into account either possibility.

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.  

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.

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.

but what if the first prisoner enters the room and sees the switch ON?  how does he know that the counter hasn't been there?  If he assumes the counter has been there and flips the switch off (and counts it as his ONE), then the count will never get to 22.

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 problem with this solution is that that it assumes the counter visits the room immediately after each and every prisoner has flipped a switch.

If two prisoners flip the switch in a row, and the counter returns, he might assume that no one has flipped the switch.  In fact, he won't be able to tell if 0,2,4, etc, prisoners have flipped the switch.

M57 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.

but what if the first prisoner enters the room and sees the switch ON?  how does he know that the counter hasn't been there?  If he assumes the counter has been there and flips the switch off (and counts it as his ONE), then the count will never get to 22.

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.

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.

The whole point being that the switch only starts being moved once the counter is there, and each other prisoner only flips it when he knows that his flip will be properly included in the count.  That gets rid of the potential off by 1 issue that you previously had.

I do not know which solution is faster on average, though I certainly know how to work that out.