Switch problem

[Oook]

After enjoying the various problems already posted here, I thought I'd share one I found quite interesting:

You have 50 people taken prisoner. They are gathered together, and told the following rules:

Once they have been told the rules, they will have time to discuss a plan amongst themselves. After they have finished, they will each be placed in a separate cell, and unable to communicate with each other.

At unspecified (and unpredictable) time intervals, one of them will be selected (independent of prior selections), and led to a room, in which there is a single switch, which can be set to 0 or 1. They are not told what position it will start in. Once in the room, the can either flick the switch or not. Either way, they are then led back to their cell. This process then repeats.

At any point, if any of them knows for certain that all of them have been in the room at least once, they can say so, and all of them will go free. They must be able to explain why they know for certain. Simply waiting a long time and hoping that everyone has been through isn't good enough.

You can assume they're all perfectly logical, trying to escape, and will act according to the plan.

I think that's it - just say if there's anything I've missed, or anything you want clarification on.

[RealGrouchy]

Would the solution not involve something along the lines of, "if this is your first time in the room, leave the switch in the 'down' position, if it's your second time, put it in the up position"?

However, the rules clearly state that selections are independent of prior ones, so that would not work.

It seems we have a bit of a singularity here...

[Penguin]

Identify one prisoner to be the counter - he will be the only one who will be able to declare that everyone has been in the room. He will also be the only one who may flip the switch to 0.

Every other prisoner, upon visiting the room for the first time (and the first time only), must switch it to 1 if it is in the 0 position, and not switch it at all if it is already in the 1 position.

Then, knowing the number of prisoners n, the counter simply has to wait until he has switched it back to 0 a total of n+1 times. It must be n+1 because if the switch starts in the 1 position, then the counter's total will always be 1 more than the number of prisoners who have visited the room. Once he has flipped the switch to 0 the 51st time, he will know for certain that regardless of the starting position of the switch, everyone has flipped the switch once and hence has visited the room once.

[Oook]

Penguin - good try, but not quite. Prisoners can be selected more than once (that's what I meant by independently, should have made that clearer), so you could get one person and the counter alternating 51 times, say.

[CactusEater]

can you please pm me with the answer because it gave me a monster headache trying to work it out yesterday and i dont want another today

[Penguin]

Perhaps I wasn't clear - once the one person you have alternating with the counter has flipped the switch once, he does not switch it again. He chooses instead not to flip the switch when he enters the room the second, third, fourth times. If the counter then enters the room and the switch is still in the 0 position, he knows that nobody new has been in the room since the last time he entered and does not add one to the count. That way the counter only counts each person once.

Edit: haha, I forgot to add the "for the first time" to that sentence up there. Apologies! It's fixed now.

[Oook]

Very close, but it still doesn't quite work - if the switch starts in position 0, the total count will be equal to the number of people who have been in the room. Thus it will never reach n+1, so they'll never finish. But nearly there

[Penguin]

Oooh, good point.

What if we have each prisoner flip the switch twice, then, and only twice? Then the counter has to wait for 2(n-1): n-1 because he's had to be in the room an awful lot to get that far and therefore doesn't have to count himself, and 2 times it because that means one of two things... if the switch started in the 0 position, then each man has been in the room twice, or if the switch started in the 1 position, then each man has been in the room twice except for one man who has only visited it once.

That should work, right?

[xkcd]

I think Penguin's got it.

That's a really neat puzzle.

[Oook]

Yep, that's it - well done Penguin

Yeah, it's a nice problem, with various little bits you need to sort out on the way. I'm not sure where it's from, as I only heard it third (at least) hand.

[Penguin]

I heard some permutation of it once upon a time on Car Talk, but never heard the answer... my first response was based on what I'd come up with for their version of it. But that had two switches and some other complication. I don't know where it originated, either.

Yay! Thanks

[Tropylium]

A quicker tweak to Penguin's solution would be to have everyone except the counter to flip the switch from 0 to 1 the first time they find it at 0. The counter may now safely declare everyone free after the 50th time xe has flipped it from 1 to 0.

Now, assuming that the time between visits must be a minimum of 30 minutes, that the prisoners have no means of mezhuring time, & that they each have 40 years left to liv, what is the probability that the prisoners get out before dying of old age?

[Oook]

I don't think you can use that tweak - don't you run into the potential problem of never finishing (or finishing too soon, depending on how you set it up), due to the uncertainty of the initial position? Or have I misunderstood what you meant?

As for your follow up question, interesting - but what's the mean waiting time?

[Tropylium]

I don't think you can use that tweak - don't you run into the potential problem of never finishing (or finishing too soon, depending on how you set it up), due to the uncertainty of the initial position? Or have I misunderstood what you meant?

… Oh, yeah, sorry. I misunderstood your 2nd reply to Penguin.

As for your follow up question, interesting - but what's the mean waiting time?

Let's say it's an even probability distribution between 30 - 60 min…

[caromalinia]

The non-counter people must be informed (and this was not clear in anyone's previous description, I think), that if on their first (and second) times in the room the switch is already up, they must not count those visits as real visits, which is to say, they should still flip the switch the next time they are in there.

Leaving the switch up will never produce a count; only flipping it up will. Suppose person 1 comes in for the first time, and flips up the switch. Then person 2 comes in for the first time, and leaves it up. After these two have been in the room, in comes the counter. She must count "1" (not 2, although there have been 2 people in the room). She has only counted the first person, who actually flipped the switch. Person two should count herself as not having visited the room yet for the purposes of counting.

Those prisoners are going to be there for a long time, aren't they? And they better hope the guards don't catch on to the plan, because it would take long enough if the counter was chosen only with the same frequency as everyone else--imagine if she were intentionally chosen only infrequently or not at all. However you slice it, the counter has got to be in there at least 2(n-1) times to reach the full count.

[sowiebinich]

My only concern is that this means that the counter is going to have to enter the room at least once for each fellow prisoner. The variation I heard was that whoever is controlling this little exercise can overhear the strategy. This being said, the captor (who, let's suppose doesn't want these guys getting out), has nothing to do but allow the counter fewer visits than captives?

[UltramaticOrange]

I recently ran across this logic problem elsewhere and decided to write out the solution in C++ to see how long it would take. You may have seen this code in another (now locked) thread. Don't use it. There's a rather hefty memory leak (which is actually the only reason why I'm posting the correction) and a bug that causes execution time to be way (waaaaaaaaay) too long.

If you're one of the 3 people that download the old code, delete it and use this code instead.

Sadly, this was written in Visual C++ 6 and will need modification to work with GNU GCC (read: ANSI standard C++).

[DrStalker]

See the last post in viewtopic.php?f=3&t=13669&hilit=prisoners

This puzzle has come up before, usually with 100 prisoners and a light bulb.

In particular, see viewtopic.php?p=87536#p87536 for a link to an academic paper discussing in great detail several strategies and their estimated times till completion.

[jestingrabbit]

I think UltramaticOrange is aware that this has come up before, and has decided that this is a good place for him to post. I agree with UltramaticOrange on this point.

[crp]

wait... I'm confused....

sum1 make a diagram of how the solution works?

[Strilanc]

wait... I'm confused....

sum1 make a diagram of how the solution works?

On the first day whoever goes in makes sure the light is off.
After that:
One person (the counter) turns the light off when they see it on and keeps track of how many times they have done this.
Everyone else turns the light on if it is off and they have never turned it on before.
The counter declares completion when they have turned the light off 49 times.

Essentially, the light being on means someone the counter hasn't counted yet has been in the cell.

[EdgarJPublius]

wouldn't it be faster if the first person in becomes the counter? it seems like nobody else has to know who the counter is, so the first person picked to go in the room makes sure the light is off and then becomes the counter.

It wouldn't be much faster, but a little bit.

[jestingrabbit]

@edgar: The problem with that is the unspecified time intervals. There aren't the days that alky was referring to.