Switch problem

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Switch problem

Postby Oook » Tue Jul 04, 2006 7:54 pm UTC

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.

User avatar
RealGrouchy
Nobody Misses Me As Much As Meaux.
Posts: 6704
Joined: Thu May 18, 2006 7:17 am UTC
Location: Ottawa, Ontario, Canada
Contact:

Postby RealGrouchy » Wed Jul 05, 2006 9:14 am UTC

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:

Postby Penguin » Wed Jul 05, 2006 3:04 pm UTC

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.

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

Postby Oook » Wed Jul 05, 2006 5:00 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:

Postby CactusEater » Wed Jul 05, 2006 5:16 pm UTC

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:

Postby Penguin » Wed Jul 05, 2006 8:30 pm UTC

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.

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

Postby Oook » Wed Jul 05, 2006 8:54 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:

Postby Penguin » Thu Jul 06, 2006 12:38 am UTC

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?

User avatar
xkcd
Site Ninja
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC
Contact:

Postby xkcd » Thu Jul 06, 2006 1:58 am UTC

I think Penguin's got it.

That's a really neat puzzle.

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

Postby Oook » Thu Jul 06, 2006 5:44 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:

Postby Penguin » Thu Jul 06, 2006 8:07 pm UTC

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

Postby Tropylium » Tue Jul 25, 2006 4:41 pm UTC

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? 8)

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

Postby Oook » Sat Jul 29, 2006 10:21 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

Postby Tropylium » Sun Jul 30, 2006 11:15 am UTC

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. :oops:

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…

User avatar
caromalinia
Posts: 17
Joined: Thu Oct 12, 2006 12:20 pm UTC
Location: currently, Washington DC. someday, back in Saskatchewan...?
Contact:

important addendum

Postby caromalinia » Thu Oct 12, 2006 12:30 pm UTC

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

Postby sowiebinich » Sun Oct 15, 2006 6:55 am UTC

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

Postby UltramaticOrange » Fri Oct 12, 2007 8:22 pm UTC

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
Image

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

Re: Switch problem

Postby DrStalker » Sat Oct 13, 2007 6:38 am UTC

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.

User avatar
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

Postby jestingrabbit » Sat Oct 13, 2007 7:49 am UTC

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

Postby crp » Tue Oct 16, 2007 1:38 am UTC

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

sum1 make a diagram of how the solution works?

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

Re: Switch problem

Postby Strilanc » Tue Oct 16, 2007 5:09 am UTC

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.

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

Re: Switch problem

Postby EdgarJPublius » Tue Oct 16, 2007 6:51 am UTC

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

User avatar
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

Postby jestingrabbit » Tue Oct 16, 2007 7:37 am UTC

@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 9 guests