ratsy wrote:

Or, if it helps, there are 8 possible state changes: (see ozy's diagram above - from 00 to 01, or 00 to 10 etc.)  So if the prisoners could organize themselves onto groups they might be able to something with the state changes. 

 

Well, I'm going to go ahead and step on Boris' toes and answer this post.

No, it does not matter how many prisoners there are, though I think the solution for 1 or 2 would be trivial (and not the same as) compared to 3 or more. But as for 23 being specific to the answer, no, it is not.

I can solve it for 2 prisoners. 

4 switch states 00, 01, 10 & 11.

The first time someone is called to the room, they move the switches towards a 00 state.  The second  & subsequent times they move it toward the 11 state.  If you get to the room & see it in 11, you know the other prisoner has been there at least twice.  (need to plan for second visit, because the switches could start in the 11 state).  Since the other guy has been there twice & you have been there at least once, you can say you have all been there.

now how to extrapolate to 23 prisoners.

 

I think you meant to say "If you get to the room A SECOND TIME & see it in 11...".  Even so, it doesn't work.  Example scenario: Starting position is 11, prisoner A visits three times in succession.

For two prisoners, it is simple: either prisoner can make the declaration when he sees the switches are not how he left them on his previous visit.  Given the random selection precondition, this will surely happen and likely quite soon.  But that solution doesn't extrapolate, obviously.

NewlyIdle wrote:

I can solve it for 2 prisoners. 

4 switch states 00, 01, 10 & 11.

The first time someone is called to the room, they move the switches towards a 00 state.  The second  & subsequent times they move it toward the 11 state.  If you get to the room & see it in 11, you know the other prisoner has been there at least twice.  (need to plan for second visit, because the switches could start in the 11 state).  Since the other guy has been there twice & you have been there at least once, you can say you have all been there.

now how to extrapolate to 23 prisoners.

 

 

I think you meant to say "If you get to the room A SECOND TIME & see it in 11...".  Even so, it doesn't work.  Example scenario: Starting position is 11, prisoner A visits three times in succession.

hrm..

Cramchakle wrote:

Well, I'm going to go ahead and step on Boris' toes and answer this post.

No problem, go ahead and answer when needed.

No, it does not matter how many prisoners there are, though I think the solution for 1 or 2 would be trivial (and not the same as) compared to 3 or more. But as for 23 being specific to the answer, no, it is not.

I agree with Cram - 23 isn't important, but scaling down to 2 really changes the problem.  Stick to high single digits.

ratsy wrote:

Or, if it helps, there are 8 possible state changes: (see ozy's diagram above - from 00 to 01, or 00 to 10 etc.)  So if the prisoners could organize themselves onto groups they might be able to something with the state changes. 

Well, with Boris' permission to step in a little bit, and to further help move this along before some angel answerer jumps in with their googled answer, here is a hint:

Organizing into groups is headed down the correct line of thinking.

hint: google isn't helping...

I think maybe if we just think of using one switch, not two.  The second would just be to flip when the first is already in the correct position?  But, I haven't thought it out fully.  But, to simplify things I think I would consider just thinking about one switch.

Berick's suggestion sent everyone running to the hills?

I'm sure there is some set of combinations that is totally unique if you break the prisoners down into groups based on the 4 switch states and the 2 changes that can be made for each state.   And then you can use those groups as counters.  You let the prisoners make the changes until all have been accounted for. 

Or you set a countable number to each state - i.e: uu is 1,5,9 ud, is 2,6,10 du is 3,7,11 dd is 4,8,12 - or something like that and let one prisoner be in charge of keeping track of it - "first time I saw uu, second time I saw uu" - etc  and then you define the set of changes that each prisoner would have to make to keep that system working and counting - without missing a set... 

but I can't work our either system in my head. 

Does it help to note that the full state for a decision can depend on the position of the switches AND what the person remembers from previous trips?

btilly wrote:

Does it help to note that the full state for a decision can depend on the position of the switches AND what the person remembers from previous trips?

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.

That's the essence of puzzles.  Something that you can't imagine mattering, makes all the difference.

Anyways, as someone who knows the answer, that is my hint.  The actions of prisoners depend on the state of the switches, and their memory of what they have seen on past trips.

Note that the scenario you are thinking about is statistically impossible.  It may be assumed that finite combination of visits between prisoners happens infinitely often.

I think my (and others) mental hang-up is we a) think of a system and then b) think of a way it can be thwarted by delivering prisoners in a certain way.

So, the warden is, essentially, unintelligent and truly picks prisoners is a random manner.  Correct? 

Amidon37 wrote:

I think my (and others) mental hang-up is we a) think of a system and then b) think of a way it can be thwarted by delivering prisoners in a certain way.

So, the warden is, essentially, unintelligent and truly picks prisoners is a random manner.  Correct? 

Correct.

If you need him to deliver a particular prisoner to the room, eventually he will.

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?

Should I move the puzzle along with another hint in a couple of days?

btilly wrote:

Amidon37 wrote:

I think my (and others) mental hang-up is we a) think of a system and then b) think of a way it can be thwarted by delivering prisoners in a certain way.

So, the warden is, essentially, unintelligent and truly picks prisoners is a random manner.  Correct? 

Correct.

If you need him to deliver a particular prisoner to the room, eventually he will.

but nevertheless, it's within the realm of possibility that he forgets to take one of the prisoners over the course of the 4 or 500 visits, right?

M57 wrote:

btilly wrote:

Amidon37 wrote:

I think my (and others) mental hang-up is we a) think of a system and then b) think of a way it can be thwarted by delivering prisoners in a certain way.

So, the warden is, essentially, unintelligent and truly picks prisoners is a random manner.  Correct? 

Correct.

If you need him to deliver a particular prisoner to the room, eventually he will.

but nevertheless, it's within the realm of possibility that he forgets to take one of the prisoners over the course of the 4 or 500 visits, right?

Possible, but unlikely.  And for the purposes of the puzzle you may assume that eventually the prisoner will be taken..in fact any combination will show up any number of required times in any required order.  Eventually.

I've been resisting the temptation to figure out how long, on average, the puzzle takes for the prisoners to solve.

i'm fine with the answer now and moving on to another one...

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