Switch problem

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Oook
Posts: 13
Joined: Tue Jul 04, 2006 7:30 pm UTC

Switch problem

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
Nobody Misses Me As Much As Meaux.
Posts: 6704
Joined: Thu May 18, 2006 7:17 am UTC
Location: Ottawa, Ontario, Canada
Contact:
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...
Jack Saladin wrote:etc., lock'd
Mighty Jalapeno wrote:At least he has the decency to REMOVE THE GAP BETWEEN HIS QUOTES....
Sungura wrote:I don't really miss him. At all. He was pretty grouchy.

Penguin
Posts: 98
Joined: Wed Jul 05, 2006 2:54 pm UTC
Location: Cambridge, MA
Contact:
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.
Last edited by Penguin on Wed Jul 05, 2006 8:38 pm UTC, edited 1 time in total.

Oook
Posts: 13
Joined: Tue Jul 04, 2006 7:30 pm UTC
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
Posts: 17
Joined: Fri Jun 23, 2006 10:01 pm UTC
Contact:
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
{o,o}
|)__)
-"-"-

Penguin
Posts: 98
Joined: Wed Jul 05, 2006 2:54 pm UTC
Location: Cambridge, MA
Contact:
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
Posts: 13
Joined: Tue Jul 04, 2006 7:30 pm UTC
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
Posts: 98
Joined: Wed Jul 05, 2006 2:54 pm UTC
Location: Cambridge, MA
Contact:
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
Site Ninja
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC
Contact:
I think Penguin's got it.

That's a really neat puzzle.

Oook
Posts: 13
Joined: Tue Jul 04, 2006 7:30 pm UTC
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
Posts: 98
Joined: Wed Jul 05, 2006 2:54 pm UTC
Location: Cambridge, MA
Contact:
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
Posts: 127
Joined: Tue Jul 25, 2006 9:40 am UTC
Location: Finland
A quicker twerk 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
Posts: 13
Joined: Tue Jul 04, 2006 7:30 pm UTC
I don't think you can use that twerk - 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
Posts: 127
Joined: Tue Jul 25, 2006 9:40 am UTC
Location: Finland
Oook wrote:I don't think you can use that twerk - 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
Posts: 17
Joined: Thu Oct 12, 2006 12:20 pm UTC
Location: currently, Washington DC. someday, back in Saskatchewan...?
Contact:

important addendum

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

sowiebinich
Posts: 2
Joined: Fri Oct 13, 2006 2:06 am UTC

Lots of visits

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
Posts: 45
Joined: Wed May 30, 2007 3:31 am UTC
Contact:

Re: Switch problem

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++).
Attachments
it.zip
(3.9 KiB) Downloaded 131 times

DrStalker
Posts: 271
Joined: Thu Aug 30, 2007 8:15 am UTC
Location: Sydney

Re: Switch problem

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.
There are two types of people in the world: 1) those that can extrapolate from incomplete data.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Switch problem

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

crp
Posts: 118
Joined: Tue Oct 16, 2007 1:17 am UTC

Re: Switch problem

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

sum1 make a diagram of how the solution works?

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

Re: Switch problem

crp wrote: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.
Don't pay attention to this signature, it's contradictory.

EdgarJPublius
Official Propagandi.... Nifty Poster Guy
Posts: 3727
Joined: Tue Oct 09, 2007 4:56 am UTC
Location: where the wind takes me

Re: Switch problem

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.
Roosevelt wrote:
I wrote:Does Space Teddy Roosevelt wrestle Space Bears and fight the Space Spanish-American War with his band of Space-volunteers the Space Rough Riders?

Yes.

-still unaware of the origin and meaning of his own user-title

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Switch problem

@edgar: The problem with that is the unspecified time intervals. There aren't the days that alky was referring to.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 8 guests