Turning on a nuclear briefcase with the smallest possible number of keystrokes

Question

On the front panel of the "nuclear briefcase" there are $12$ buttons. Each button controls its own switch: pressing it toggles it from ON to OFF and back. The initial position of the switches is unknown. The nuclear case triggers an inaudible (ultrasonic) frequency alarm when at least eight switches are in the ON position.

Find the shortest way using as few keystrokes as possible to ensure that the suitcase will sound an alarm.

I tried to do this with examples, but actually I've not idea how can I determine which button to press.

Answer 1

UPDATE: A better answer with $47$ moves. (Credit: inspired by comment of @WW1 in main thread.)

Paint the buttons $2$ red, $1$ green, $9$ blue.

Using a gray code or similar, you can have the $2$ red buttons go through all $4$ states with $3$ moves.

Lemma: If you press green, then all the blues once each, then green again, then at some point there are $\ge 6$ ONs among these $10$.

Proof: After pressing green and all the blues, the $10$ bits will be negated. Either the initial state has $6+$ ON, or the final state has $6+$ ON, or both states have $5$ ON. So we only need to worry about this last case.

• If green initial state is OFF, then among the initial blue there were already $5$ ON. When you press green the first time you already got $6$ ON simultaneously.

• If green initial state is ON, then before pressing green the second time, green was OFF and there are $5$ blues ON. The second green press will be the $6$th ON. $~~~~~~~~\square$

So if you do the red buttons as an outer loop and the other buttons as an inner loop, you need only $4 \times (11 + 1) = 48$ moves.

As Ross Milikan pointed out, this can be slightly optimized by omitting the first gray-code move, for $11 + 1 + 11 + 1 + 11 + 1 + 11 = 47$ moves.

---

My original answer:

Not a provably optimal answer, but a method that takes only $80 \ll 2^8 = 256$ moves.

Paint the last $3$ buttons red. Using a gray code or similar, you can have them go through all $8$ possibilities in $8$ moves.

For the first $9$ buttons, if you press each once then either the initial state or the final (bitwise negated) state will have $5$ or more switches ON.

So if you do the red buttons as an outer loop and the other buttons as an inner loop, you need only $8 \times (9 + 1) = 80$ moves.

Answer 2

let's divide 12 buttons into two groups of 9 buttons and 3 buttons. consider a group of 9 buttons there may be 5 switched on switches and in this case we need to switch three switches so that we have a total of 8 switched on switches. in a group of three buttons, we can consider all possible combinations and in this case we will definitely have 8 switches on. the number of combinations in a group with three buttons will be $2^3-1=7$ , since initially there is already a combination . now if, in our original group with nine buttons, five of these switches were not on but off, then we need 9 more moves to turn all the switches and then we will have 5 switched on switches, then again all the combinations to the second group with three buttons and then we will certainly have 8 switched on switches and the total number of moves is $7+9+7=23$

Answer 3

(I improved my previous answer, and now I think it corresponds to Delta Account's answer, but maybe in a bit more detail.)

Consider the following list of $16$ switch states where 0 corresponds to "in its original position" and 1 corresponds to the opposite:

000000000 0 0 0
000000000 0 0 1
000000000 0 1 1
000000000 0 1 0
000000000 1 1 0
000000000 1 1 1
000000000 1 0 1
000000000 1 0 0
111111111 1 0 0
111111111 1 0 1
111111111 1 1 1
111111111 1 1 0
111111111 0 1 0
111111111 0 1 1
111111111 0 0 1
111111111 0 0 0

(The spacing is there to help the pattern be clear, but doesn't mean anything.)

The "all switches are ON" position corresponds to some unknown sequence of twelve 0s and 1s. Whatever it is, it is four steps away from one of the states above. To see this, take an arbitrary state $x_1x_2x_3\dots x_{12}$. Then replace the first $9$ switches by whichever of 0 and 1 occurs more often among them, changing at most 4 switches, and you'll get one of the states above.

To go through the states above in order, we need $9 + 14\cdot1 = 23$ steps: there is one step where we press $9$ buttons to get from one state to the next, and fourteen steps where we just need to press $1$ button.