Date: 07/26/2002 at 11:14:26 From: Kev Subject: Probability or logic? Two people are trapped in a small freezer that is gradually getting colder and colder. There are four walls, each with a small button in the centre. Each person can reach only one button, allowing either one or two buttons to be pushed at the same time. Each button changes the state of a switch that is either on or off, but this state cannot be determined by sight, sound or feel. If all four buttons are put in the same state (i.e. all on or all off), a concealed hatch will open to free the people. However, pushing the buttons causes the freezer will spin, temporarily disorienting the people and, since the four walls are identical, mixing the buttons up. The freezer will reach a lethal temperature in ten minutes. It takes a minute for the people to recover from a spin. Is it possible for them to escape? If so, how? What's the maximum number of minutes required to escape given ANY initial combination of button states? I initially considered trying to write down every possible starting state and the possible changes. Then I realised that, because the buttons get mixed up, that each time they go to press a button they are in a similar situation to when they started. That means it must be a probability question, doesn't it? So how do I go about tackling this?
Date: 07/28/2002 at 15:48:33 From: Doctor Rick Subject: Re: Probability or logic? Hi, Kev. That's a nice problem -- pretty challenging for a 15-year-old! It isn't a probability question. The first question ("Is it possible?") could sound that way, but if it were, the follow-up question would be, "If so, what is the probability that they would escape in ten minutes?" Instead, the follow-up questions are "If so, how?" (That is, what strategy should they use?) Also, "What's the maximum number of minutes required?" In a probability problem, most likely the probability of escaping would increase if they have more time, but would not quite reach 100%. I did find a strategy that enables them to escape within nine button- pressing cycles. Here are some things to think about. First, how many states are there that the switches could be in? I found a very useful fact: the number of possible states is effectively only half what it at first seems to be. The state "off-on- off-off" (which you might abbreviate as 0100" can be combined with the state "on-off-on-on" (1011) because, for instance, pushing the second button puts them into the states 0000 and 1111 respectively, and both of these cause the prisoners to be released. You may have to think about this a bit -- it's not obvious that it works! Second, how many things can the prisoners do that are really different? There are surprisingly few. For instance, pushing the "north" and "east" buttons on one cycle is not guaranteed to be different from pushing the "east" and "south" buttons on another cycle, because the room may have rotated in such a way that what was "north" is now "east" and what was "east" is now "south." Thus pushing NE on one cycle, then ES on the next, might just put you back in the same state you were in to start with. That wouldn't be very helpful. So, what things can they do that are guaranteed NOT to be the same (even if they are done on different cycles)? The strategy you come up with will be a particular sequence of these few different actions. The goal in choosing this sequence is to ensure that, whatever the initial state of the buttons, you are bound to reach a 0000 or 1111 state by the time you've finished the sequence. So far I haven't given you a lot of help, but I don't want you to lose the chance to solve such a nice problem on your own. Take another shot at it before reading further. Still stuck? I'll give you a direction to explore. First, I used the notation: S (press any single button) O (press the buttons on either pair of opposite walls) A (press the buttons on any two adjacent walls) Also, I numbered the states using binary notation: 0 = 0000 or 1111 1 = 0001 or 1110 2 = 0010 or 1101 3 = 0011 or 1100 etc. The next thing I did was to write down the effect of each action on each state. For instance, action S changes state 1 into one of the states 0, 3, 5, or 6, depending on the orientation of the freezer (whether the button pushed is switch 1, 2, 3, or 4). Once you've tabulated all this information, you can start to play with sequences of only two actions. Start by finding a sequence such that you can be sure of winning by the end of the sequence, IF you've got some particular initial state. See where you can go with this. Have fun! - Doctor Rick, The Math Forum http://mathforum.org/dr.math/
Date: 07/31/2002 at 07:25:28 From: Kev Subject: Probability or logic? Thanks, Dr. Rick. I think I've got it now! (Though I had to consult a boffin I know from school to get the final bit done.) I picked up your notation but I found in more helpful to think to the switch vs room orientation in terms of F(ront), B(ack), (L)eft, and R(ight). Then I made up a table to show the effect of each action (S, O, or A) on the state of the switches depending on where the first switch was. I took S to mean pressing the switch in the F position, O to press F and B, and A to press F and R. Action: S O A First switch: F R B L F R B L F R B L State 1 6 5 3 0 4 4 4 4 2 7 2 7 2 5 6 0 3 7 7 7 7 1 4 1 4 3 4 7 1 2 6 6 6 6 0 5 0 5 4 3 0 6 5 1 1 1 1 7 2 7 2 5 2 1 7 4 0 0 0 0 6 3 6 3 6 1 2 4 7 3 3 3 3 5 0 5 0 7 0 3 5 6 2 2 2 2 4 1 4 1 Here's where I got stuck. Then I saw that doing O gave the same state whatever way round the room was! A gives only 2 states each way round but S gives a different state for each position. So I started with O then followed with A. Saw some 0s (freedom!) appearing and carried on till I had done OAOAO. After that I could see that I wouldn't get any more 0s by repeating it. What it had done was to get rid of those states where an even number of switches were on or off. So I needed to do S to change the remaining 'odd' states into 'even' states. Then I could go back to OA, etc. I found that OAOAOSOAO, 9 moves, is certain to give freedom.
Date: 07/31/2002 at 09:03:09 From: Doctor Rick Subject: Re: Probability or logic? Hi, Kev. Excellent work! My solution was quite similar; I had the same insight about using S in the middle. Comparing our solutions, I discovered a shorter solution! My solution was AOAOSAOAO. I found that AOAO takes initial states 3, 5, and 6 to a win; if I haven't won yet, the switches are in state 1, 2, 4, or 7. After the S action, the switches can only be in state 3, 5, or 6 (unless I've won). Then I apply the same sequence AOAO to ensure a win in these cases. Is yours the same - after the S action, the state is 3, 5, or 6? If so, then if OAO takes care of all these cases, my solution could be shortened by one step. Let's see. What does OAO do? O A O 3 ---> 6 ---> 0 or 5 ---> 0 5 ---> 0 6 ---> 3 ---> 0 or 5 ---> 0 What do you know, it works! Now we have an 8-step solution: AOAOSOAO And it raises the question: can the first part be shortened in the same way, to OAO? We know OAO takes initial states 3, 5, and 6 to a win; what does it do with the other states, 1, 2, 4, and 7? O A O 1 ---> 4 ---> 2 ---> 7 or 7 ---> 2 2 ---> 7 ---> 1 ---> 4 or 4 ---> 1 4 ---> 1 ---> 2 ---> 7 or 7 ---> 2 7 ---> 2 ---> 1 ---> 4 or 4 ---> 1 Yes, we're in good shape: we can apply action S to change each of these to 0, 3, 5, or 6. Thus we have a 7-step solution: OAOSOAO What do you think? Does it really work, or did I miss something that required you to have an extra OA at the beginning? Check it your way and let me know. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/
Date: 08/01/2002 at 03:42:36 From: Kev Subject: Probability or logic? You're right, Dr. Rick - 7 presses does it! I can't see any way to get it lower. You need three presses to be sure of taking 3, 5, and 6 to 0. Then you need the S to change the 1, 2, 4 and 7 into 3, 5, 6, or 0. Then you need the three presses again to change the new 3, 5, and 6 into 0.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.