wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Hard: BUTTON TRAP ROOM
        
(Message started by: Viorel Canja on Jul 26^th, 2002, 2:46am)

Title: Hard: BUTTON TRAP ROOM
Post by Viorel Canja on Jul 26^th, 2002, 2:46am

I thought I had found a 5 turns solution . Before posting anything I coded a little proggie to check and ... it turns out that my "solution" is wrong and the minimal solution has 7 turns :(

Title: Re: Hard: BUTTON TRAP ROOM
Post by srowen on Jul 26^th, 2002, 3:53pm

Is this the answer people have found?

Work backwards. First some observations:

A.
Say that two of the four buttons were on, and they were on opposing walls (across from each other, not adjacent). In this situation (call it A), pushing the two buttons on either pair of opposing walls gets you out. Pushing two adjacent walls puts you in the next situation...

B. Now say that two of the four were on, but on adjacent walls. Call this situation B (all four possibilities here are really the same since you have no idea which are which anyway).
If you push the two buttons on any pair of adjacent walls, then either you get out, or you are left in situation A.
On the other hand if you push two opposing walls, you definitely end up in situation B again.

C & D. Finally, let me call the situation where 1 button is on C, and 3 buttons on D. Note that pushing any two buttons in situation C or D leaves you in situation C or D. Pushing any one button on a wall puts you into A or B.

Now, here we go.

At the outset you are in situation A, B, C or D, though you don't know which.

1) Push buttons on two opposite walls.
If you were in A, you're free!
If you were in B, you're in B again.
If you were in C or D, then you are still in C or D.
2) Push buttons on two adjacent walls.
If you were in B, you're either free now, or in A.
If you were in C or D, then you are still in C or D.
3) Push buttons on two opposite walls.
If you were in A, you're free!
If you were in C or D, then you are still in C or D.

If not free by this point, you know you are in C or D.
4) Push any button.
You are in A or B.
Now repeat the above:

5) Push buttons on two opposite walls.
If you were in A, you're free!
If you were in B, you're in B again.
6) Push buttons on two adjacent walls.
If you were in B, you're either free now, or in A.
7) Push buttons on two opposite walls.
You are free!

I suppose there is the possibility that the buttons were all on, or all off, at the start. So really we need an eighth move:

0) Push no buttons.

So my answer is 8, really. Are there better ways that account for this situation?

Title: Re: Hard: BUTTON TRAP ROOM
Post by tim on Jul 29^th, 2002, 4:05am

No, if the buttons may be all the same at the beginning, 8 is the minimum (otherwise 7). This is true even if the room doesn't spin. It is even true if you have three hands! ;)

Consider the non-spinning case, and no limit on the number of buttons you can push. Without loss of generality, you want the east, south and west buttons to match the north button. There are 8 initial combinations, and you don't know which combination you are in until you are free. All you can do is try them all until one works. Another way to look at the problem is to consider that the room's initial state as a 3-bit key. You have to XOR it with a sequence of numbers until you get a result of 000.

Obviously, spinning the room doesn't give you any extra information that might reduce the number of combinations you have to try. No does limiting you to two hands. So 8 (or 7) is optimal.

Title: Re: Hard: BUTTON TRAP ROOM
Post by mallen on Aug 29^th, 2002, 8:08pm

on 07/29/02 at 04:05:10, tim wrote:

Consider the non-spinning case, and no limit on the number of buttons you can push. Without loss of generality, you want the east, south and west buttons to match the north button. There are 8 initial combinations, and you don't know which combination you are in until you are free. All you can do is try them all until one works.

No... you could do it in 4 tries in this case.

1. Switch east and west on.
2. Switch south on.

At this point, if north is on, the door must have opened by now.

3. Switch east and west off.
4. Switch south off.

If north is off, the door opens now.

I think you might not fully understand the problem.

Title: Re: Hard: BUTTON TRAP ROOM
Post by AlexH on Aug 29^th, 2002, 8:16pm

You don't get to turn the buttons to ON or to OFF, you just get to toggle them without learning their state. Otherwise you could do it in 2 turns with 2 hands in the stationary case.
1: N and S ON
2: E and W ON

Title: Re: Hard: BUTTON TRAP ROOM
Post by Mickey1 on Dec 10^th, 2010, 5:46am

-Some preliminary investigations for a 5 button trap. I believe the method can be generalized, but it doesn’t solve Wu’s original question so I leave that for now.
I present some statements (and "=" means here that two state are equivalent; 2k=k does not mean that 2=1, it is just that 010 is the same as 001):
1.
Cyclic button combinations (here for 5 buttons), BC, of can be presented either as a ring or as a string of 1’s and 0’s such as 00001, where 00001= 00010 = 00100=01000=10000. The arrangement or combination of pressed buttons in one particular try, PC, can be represented the same way as BS above. A certain BC followed by a PC will give a resulting BC, a process we might describe as BC+PC.
2.
PC is similar to a BC in that (starting from a neutral state NS = the state that would set you free) NS+PC would yield a button combination BC with the same representation as PC used. Therefore BC+PC = NS+PC+BC, where the last BC is a Pressed Button PB combination with the same representation as the button combination BC.
3.
The states representation 00001, 00010 etc. can be given a formal representations used not only as strings but binary numbers with certain rules given below. For simplicity the leading 0 are kept. Here, the representing number for a certain state is the lowest number. In the specification of the different states, all states with trailing zeros are represented by the remaining odd states. The reason for this is that 2k=k (00010=00001 etc), since they amount to the same situation for the trapped person according to the rules in the riddle.
4.
The application of a PC =A to a BC =B is simply represented by A+B (mod 31 ) expressed (or decoded) in binary code. (Remember that 31=32 = 2^5 for the studied 5 button version) by the rules of the game. Also, k=31-k, so that 10101=01010 so all states can be represented by numbers with at most two 1’s. The reason for this is the same as given in 3.
5.
The state 1 is therefore 1=30 since k=31-k and =15 since 2k=k. Continuing, 3=28=14=7, 5=26=13, 7 (was=3), 9=22=11. We check for consistency by using k=31-k once more on the results and discover that 13=18=9=22=11=10=5 binding together the two last groups 5=9=11=13 (reflecting that 00101=01001). There are thus three state groups I (with only one 1), II (2 1’s next to each other) and III (two 1’s separated by one or two 0’s. ).

Looking only at states without tracking individual combinations (as is enough for N=4), I don’t see that the three states can converge to one. I have the combinations I+I (here all states must be used, not only one) = II&III, I+II=I&II&III, I+III= I&II, II+II=I&III, II+III=II&III and III+III=I&II. The number of combinations is reduced by the communicative rule (2). Am I missing something?

Title: Re: Hard: BUTTON TRAP ROOM
Post by Mickey1 on Jan 20^th, 2011, 9:33pm

An addendum:

3 buttons would be part of a generalization. There we have onle one state (other than 000 and 111 which would let you out according to the riddle rules). 110=011=001 is the only state.

You can easily see that no winning strategy exist, you will just come back to the same basic state.

2 buttons give the same picture, 10=01.

If I had to guess, I would say that no winning strategy exists for any button number except 4, but then I have no computer skill.

Title: Re: Hard: BUTTON TRAP ROOM
Post by rmsgrey on Jan 21^st, 2011, 6:55am

on 01/20/11 at 21:33:28, Mickey1 wrote:

With 2 buttons, press one and go free.

With 3 buttons, I agree with your reasoning - pressing all three buttons obviously has the same effect as pressing none, and pressing two as pressing one. Pressing none does nothing, and pressing one either frees you or switches the odd-one-out between the other two buttons.

From my dim memories of working on the related problem where you know what states the buttons you're interacting in are in before choosing whether to press them or not, I suspect there may be a 4-hand solution for 6 buttons (with only 3 hands, it's possible for one pair of buttons to never get pressed)

Title: Re: Hard: BUTTON TRAP ROOM
Post by Grimbal on Jan 21^st, 2011, 9:41am

Isn't pressing 4 buttons the same as pressing the 2 remaining ones?

Title: Re: Hard: BUTTON TRAP ROOM
Post by rmsgrey on Jan 22^nd, 2011, 10:03pm

on 01/21/11 at 09:41:55, Grimbal wrote:

Isn't pressing 4 buttons the same as pressing the 2 remaining ones?

Good point.

So with 6 buttons, a pair can be chosen such that whatever you do, on each turn, either they're both pressed, or neither is pressed, meaning if they start out in opposite states, you can never win.

When the number of buttons is a power of two, there's always a move that will split any given pair - if the pair to split are n and n+k (where k is known but n is not) then pressing the first c buttons, leaving the next c, pressing the next c, leaving the next c, and so on, where c is the greatest power of 2 that divides k, will always press exactly one of the chosen pair.

8 is solvable in 127 steps using the following seven moves:

A) 01010101
B) 00110011
C) 00010001
D) 00001111
E) 00000101
F) 00000011
G) 00000001

in the pattern

ABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABA

The basic pattern of the solution is to have a sequence of moves that partitions the set of positions into equivalence classes where applying the sequence to a given position will take it to various other positions within the same class, and will always take a position in the same class as the winning positions to one of the winning positions, and a move that takes any position in a specific, non-winning, equivalence class and takes it to a position in the winning equivalence class. Applying the sequence, then the move, then the sequence creates a new sequence that will win from any position in either the winning class or the other specific class.

For a starting position abcdefgh, the winning class is a=b=c=d=e=f=g=h. A moves positions in the class a=~b=c=~d=e=~f=g=~h into the winning class by adding 1 either to a, c, e and g, or to b, d, f and h.
For the sequence A, the new winning class is a=c=e=g, b=d=f=h. B moves positions in the class a=~c=e=~g, b=~d=f=~h into the winning class by adding 1 both to either a and e or c and g, and to either b and f or d and h.
For the sequence ABA, the new winning class is a=e, b=f, c=g, d=h, a+c=b+d. C brings in a=e, b=f, c=g, d=h, a+c=~(b+d) by adding 1 to precisely one of a, b, c, or d.
ABACABA's winning class is a=e, b=f, c=g, d=h. D brings in a=~e, b=~f, c=~g, d=~h by adding 1 to precisely one of each pair.
The new winning class is a+e=b+f=c+g=d+h. E brings in a+e=~(b+f)=c+g=~(d+h) by either adding 1 to one each of a and e, and c and g, or one each of b and f, and d and h.
The new winning class is a+c+e+g=b+d+f+h=0. F brings in a+c+e+g=b+d+f+h=1 by adding 1 to precisely one of each quartet.
The new class is a+c+e+g=b+d+f+h. G brings in a+c+e+g=~(b+d+f+h) by adding 1 to precisely one place, making the new class the complete set of possible positions.

Note: The first three moves are copied from the solution for 4 buttons by repeating the move pattern, and win from any starting position abcdabcd in 7 steps.

I suspect there's a solution for 16 buttons, using 15 different moves and taking 32767 steps to guarantee victory, but I'm not about to try demonstrating it...

Title: Re: Hard: BUTTON TRAP ROOM
Post by Mickey1 on Jan 23^rd, 2011, 1:08am

An advertisement: see olso my continued treatment of the number of stable states in the Topic about Mersenne Primes and non-primes.