Ancient Treasure

The ESPR & PAIR 2023 Admissions puzzle game:

You stumble upon an ancient treasure locked behind a convoluted puzzle mechanism: a rotating box with 4 identically looking buttons on it.

Each button has two states - on and off - but it's impossible to distinguish these states from the outside. You can simultaneously press any number of buttons, but immediately after that the box rotates really fast and you lose track of which button ends up where.

You get the treasure if at any moment all the buttons are off.
Can you guarantee this happening? Explain your reasoning.

Below, you can find an implementation of the game. You can play around with it to understand the mechanism better, and maybe even get the treasure!

The Ancient Treasure

You see a mystery box…

5 +3

Solution

For something to be guaranteed to happen, it means that it has to happen in bounded finite time, even under the worst circumstances. In this case, imagine there was a mind-reading adversary who knew ahead what sequence of buttons are you going to press and was aiming to rotate the box such that you couldn’t unlock the treasure. Could you beat the adversary?

  • What if there were only 2 buttons? Could you beat the adversary in this case?

  • What is the one bit of information you get each time the box rotates?

    How can you use it?

  • Yes, you can beat the adversary both in the case of two buttons and in the case of four buttons.

    There exists a finite sequence of button presses that guarantees unlocking the box.

  • There’s an important invariant which can help you solve the puzzle

  • There are five possible initial positions:

    • All buttons on (in binary: 1111)

    • Three buttons on (1110)

    • Two adjacent buttons on (1100)

    • Two diag. opposite buttons on (1010)

    • One button on (1000)

    For a start, how would you solve the puzzle if you knew that the box has either all buttons on, or only two diagonally opposite buttons on?

  • Observation: Every time the box rotates, you receive one bit of information: Are all four buttons off, or not?

    Observation: Invariant: When you press an even number of buttons, you preserve the parity of the number of buttons which are on.

    Observation: Pressing all four buttons applies a XOR operation on the buttons’ states.

    Observation: We can group initial positions into 5 categories (described in Hint 4).

    There’s a sequence of moves that eliminates all possible initial positions:

    • Press all four buttons.

    • Press any two diag .opposite buttons.

    • Press all four buttons.

    • Press any two adjacent buttons.

    • Press all four buttons.

    • Press any two diag. opposite buttons.

    • Press all four buttons.

    • Press any single button - this reverses the parity. Repeat all the previous steps.

    It’s guaranteed that the box will open after one of the 15 presses.

    Still don’t see why? Apply these button presses to each of the initial states and you will see!

    1. Can you generalize this solutions to a different number of buttons?

      What about if there were more than two possible states?

      Look here for a simulation!

    2. Do you now understand how does the puzzle implementation work?