The crew of the USS enterprise gets stranded on an alien planet and is captured by an evil king who lives in a medieval castle. He imprisons them all, agreeing to release them if they suceed at a game he wants to play with them. The conditions of the game are as follows:
1. He will, at any random time, choose a random person from the crew and bring the person to a chamber that has two switches, one red and one blue. The person is forced to choose a switch and then change its position. Such visits may, or course, be repeated.
2. All the crew members are kept in solitary confinement, and are not allowed to communicate, except for one time when they are allowed to decide upon their strategy.
3. The starting positions of the switches are unknown.
4. Everyone is released when any one of the crew members tells the guards that everyone else has visited the chamber.
5. The crew members are unaware of the passage of time, that is, they cannot count days or anything like that.
Come up with a strategy for the prisoners' release. Hint: Look at my previous post. Its all there.
Subscribe to:
Post Comments (Atom)
12 comments:
Hmm. One thought one had it, but there appears to be a problem with one's solution.
The crew choose a leader. This chap is supposed to turn on the red switch each time he goes in; unless it’s already on, in which case he toggles the blue switch. The others turn off the red switch the first time they see it on, but not after that (if the red switch is off, or if they’ve already turned it off once, they just toggle the blue). The leader can count the turning-offs of the red switch, and then inform the guards when everyone’s done it once.
Problem being, we don’t know if the red switch was on to begin with (condition 3). This might cause the leader to miss one turning-off and they’d all wait perpetually. Not very pleasant, going by the previous post.
Very very close, and quite creditable. a small twist gets you over the problem of the first turning-off.
Well .. the first person to go in could appoint himself leader, but of course he has no way of knowing if he's the first, right?
Otherwise there has to be some way to indicate whether the leader has visited the chamber. How this could be done is quite beyond me.
yes, the trick is precisely in finding some way of indicating whether the leader has visited the chamber (under the scheme you mentioned in your earlier previous comment). there is, indeed, such a scheme.
it may not be obvious, but its also there in my solution.
if you want (and i don't think you would), i can outline the solution..
Hang on .. will have a leetle think.
Okay, how about this:
The crew members turn off the red switch the first time they see it on after they've seen it off at least once.
So if the switch was on to begin with, nobody would touch it until the leader came along. When the leader came, he'd turn off the switch. Next time he came in, he'd turn on the switch and start counting.
If the switch was off to begin with, the leader would turn it on and count as before.
It's possible for crew members to miss seeing the turned-off switch, which would mean that they leave it unchanged when they encounter it in the on position. The leader would then have to turn it off himself once in a while before turning it back on.
Admittedly a little inelegant, and I don't know if it's the solution you had in mind, but I think it would work.
yes, that's it. completely echo the last line : inelegant, but it works. i'm trying to find a more elegant one, but haven't so far.
i don't think you need the leader to turn it off from time to time.. basically, the fact that the process is completely random ensures that with probability one, everyone gets to turn the switch off in a finite time.. but doing that might very well decrease the time taken. I'll have to see.
Nice, very nice.
Thanks. One thinks it might become necessary for the leader to turn off the switch himself (not just a matter of decreasing time taken). Assume the following: the leader has turned the switch on and is counting turn-offs. He counts turn-offs for all his crewmates but one. This unfortunate crewmate had never gone in at a time when the switch was off, so although he now encounters a turned-on switch each time, he will not turn it off according to the scheme we agree on.
The leader should, under such circumstances, guess that this chap is in this situation, turn off the switch himself, and wait for some time for the chap to see it. If the leader does not do this, we have a perpetual wait ahead.
(Your point about every crewmate getting to turn the switch off in a finite time overlooks the fact that we now impose an additional condition - namely, that he must've seen the switch in the off position before. So, even if everyone gets a chance to turn off the switch in a finite time, he may not do so because the condition has not been met.)
i see your point. agreed.
we discussed this before. the leader would change the position of the switch every time he comes in, but would, of course, count only the times when he finds that someone has changed it from on to off since the previous time he came in.
he has to keep changing it to make sure everyone sees it.
here is a more elegant solution:
the four possible positions of the switches are - 00, 01, 10, 11. now from any of these positions its possible to go to either set1=(00, 01) or set2=(10, 11). So lets say the crew decides that whenever a person goes in for the first time they put it to set1 else set2. so every crew member keeps his own count of how many times has he seen set1. the first person from the crew whose count of set1 equals the no. of crew members can claim that everyone has been to the chamber once.
Post a Comment