Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Freezer Roulette

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.
Associated Topics:
High School Permutations and Combinations
High School Puzzles

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/