Author |
Topic: Hard: BUTTON TRAP ROOM (Read 10017 times) |
|
Viorel Canja
Guest
|
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 
|
|
 IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
Re: Hard: BUTTON TRAP ROOM
« Reply #1 on: Jul 26th, 2002, 3:53pm » |
 Quote  Modify
|
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?
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #2 on: Jul 29th, 2002, 4:05am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
mallen
Newbie
Posts: 1
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #3 on: Aug 29th, 2002, 8:08pm » |
Quote Modify
|
on Jul 29th, 2002, 4:05am, 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.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #4 on: Aug 29th, 2002, 8:16pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #5 on: Dec 10th, 2010, 5:46am » |
Quote Modify
|
-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?
|
| « Last Edit: Jan 20th, 2011, 9:24pm by Mickey1 » |
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #6 on: Jan 20th, 2011, 9:33pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #7 on: Jan 21st, 2011, 6:55am » |
Quote Modify
|
on Jan 20th, 2011, 9:33pm, Mickey1 wrote: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.
|
|
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)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #8 on: Jan 21st, 2011, 9:41am » |
Quote Modify
|
Isn't pressing 4 buttons the same as pressing the 2 remaining ones?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #9 on: Jan 22nd, 2011, 10:03pm » |
Quote Modify
|
on Jan 21st, 2011, 9:41am, 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
ABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABAD ABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABA
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...
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #10 on: Jan 23rd, 2011, 1:08am » |
Quote Modify
|
An advertisement: see olso my continued treatment of the number of stable states in the Topic about Mersenne Primes and non-primes.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Hard: BUTTON TRAP ROOM
« Reply #11 on: Dec 5th, 2024, 4:24am » |
Quote Modify
|
I recently encountered a variation on this puzzle where, rather than having to get all the buttons to match, you have to have them all turned on.
Obviously, you need to be able to toggle all the buttons in a single move, so each turn you pick any subset of the n buttons to toggle.
Also obviously, with half as many winning states, you now need to distinguish each state from its complement, so the lower bound on number of moves required is doubled (when including an initial null move).
That makes it trivial to find optimal solutions when n=2k - just take the known solution for the all-match version and press all the buttons after each move (including the initial null move) - the all equal solution will cycle through each complementary pair of states in turn, and pressing all buttons will test the other state in a given pair.
A complete solution emerges:
For any composite m=ab, any solution for n=m will also solve n=a and n=b (not necessarily optimally) since taking every a'th button will give you an embedded copy of the n=b problem, while every b'th button gives you n=a, so the solution for n=m is a solution for n=a where at each step you pick randomly from b possible (not necessarily different) moves depending on which of the b possible positions the "real" buttons for the n=a case end up. Since every winning state for n=m is also a winning state for all the embedded n=a and n=b games, the claimed result holds.
For odd n>1, no solution exists. Suppose an adjacent pair of buttons start in opposite states - one on and one off - then, no matter what move you pick, there's a rotation that has you either leaving both buttons or pressing both buttons. Either way, they remain as one on and one off, so you can never guarantee to arrive at a state where all the buttons are on (nor where all are off). Why can't you guarantee to split those two buttons? A move that presses exactly one of each pair of adjacent buttons must press alternate buttons, but with an odd number of buttons, when you loop around, the first and last buttons would then be treated the same.
From the above two results, there can be no solutions except where n=2k.
Given a solution for n=2k, you can construct a solution for n=2k+1:
- Identify diametrically opposite pairs of buttons. If, for each pair, the two buttons are in the same state, you can solve by performing the n=2k solution, but with each move doubled - so if you make move abcd in the n=4 case, you'd make move abcdabcd in the n=8 case.
- If not, then at least one pair must differ from each other. You can again map the buttons onto the n=2k case by treating each opposite pair as a single virtual button. This time, the virtual button is on when the pair matches, and off when they differ. By performing the moves of the n=2k solution on half the board (so abcd becomes 0000abcd), you toggle the virtual buttons by pressing precisely one of the pair of actual buttons. Whenever all the virtual buttons are on, the actual buttons are in the state above, where each pair's two buttons are in the same state, so applying the doubled move n=2k solution as above between each move of this iteration will solve the n=2k+1 problem.
Note: for the all-match version, you get a similar construction except that, since you need to solve the all-on problem with the virtual buttons, you need to add a press-all move after each move of that n=2k solution - which translates to pressing half the actual buttons in a consecutive arc (eg 00001111) - and add another doubled move n=2k solution following each of those.
Alternatively, you could just take the all-on solution(s) and discard all actual press-all moves.
For k=0, n=1, and the solution is trivial - for all-match, it's already solved; for all-on, press the button.
For k=1, n=2, the all-on solution takes three moves, following the pattern ABA (A=11, B=01), and all-match takes one move: B
For k=2, n=4, and the fifteen move all-on solution is ABACABADABACABA (A=1111, B=0101, C=0011, D=0001) while the all-match solution is the familiar seven move BCBDBCB
For k=3, n=8, all-on takes 255 moves ABACABADABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABAD ABACABAEABACABADABACABAFABACABADABACABAEABACABADABACABAHABACABADABACABAE ABACABADABACABAFABACABADABACABAEABACABADABACABAGABACABADABACABAEABACABAD ABACABAFABACABADABACABAEABACABADABACABA (A=11111111, B=01010101, C=00110011, D=00010001, E=00001111, F=00000101, G=00000011, H=00000001) and all-match (as in my previous post) takes 127 moves: BCBDBCBEBCBDBCBFBCBDBCBEBCBDBCBGBCBDBCBEBCBDBCBFBCBDBCBEBCBDBCBHBCBDBCBE BCBDBCBFBCBDBCBEBCBDBCBGBCBDBCBEBCBDBCBFBCBDBCBEBCBDBCB
The pattern continues for higher powers of two, with n=2k all-on requiring an ABACABA sequence of length 2n-1 using n different moves, while all-match's sequence is 2n-1-1 long, using n-1 different moves.
|
| « Last Edit: Dec 5th, 2024, 4:27am by rmsgrey » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove