| 1 |
riddles / hard / Re: Hard: BUTTON TRAP ROOM |
Dec 5th, 2024, 4:24am |
| Started by Viorel Canja | Last post by rmsgrey |
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. |
 Reply  Quote  Notify of replies
|
| 6 |
riddles / easy / Re: Geometric puzzle, two triangles |
Apr 15th, 2024, 8:24pm |
| Started by rmsgrey | Last post by rloginunix |
That, clearly, means that that trajectory of the crossing point, shown in red, belongs to a (smaller) circular arc, as a I tried to capture that fact in the animation below.
The center of the said circle is located trivially: just construct the perpendiculars to the sides of the given equilateral triangles, etc. |
|
Reply Quote Notify of replies
|
| 8 |
riddles / easy / Re: Symbol |
Mar 29th, 2024, 6:03am |
| Started by alien2 | Last post by alien2 |
| Clue (possible spoiler): Too bad that there is no toilet inside the room... Or, perhaps, that fact just might spark a lifesaving idea! |
|
Reply Quote Notify of replies
|
| 10 |
riddles / easy / Re: The Spider-Man of Paris |
Jan 17th, 2024, 7:54am |
| Started by alien2 | Last post by rmsgrey |
For the third variation, your expected return from taking 6 paintings is always the same, so, if you're just concerned with the monetary return, the only question is how risk-averse or risk-seeking you are. If you're risk-averse, taking 3 of each type guarantees a 3-painting payout; if you're risk-seeking, taking 6 and 0 gives you either all or nothing.
You can get more interesting by delving into utility curves - if, rather than 2 paintings being twice as valuable to you as 1, 3 paintings being triple, and so on, if you instead have some other relative values for different numbers of paintings, then that changes your expected value for various strategies.
You have four options, each of which gives you a 50% chance of each of two possible outcomes - taking all the paintings from one set gives you 0 or 6; taking five from one and one from the other gives you 1 or 5; taking four and two gives you 2 or 4; and taking three of each gives you 3 or 3, which is just a guaranteed 3. Whichever pair gives you the highest total utility across the two possibilities would be your personal best pick. |
|
Reply Quote Notify of replies
|
Return to the board index.
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register