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

Mathematics Asked by Delta Account on August 14, 2020

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.

(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_3dots 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 + 14cdot1 = 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.

Answered by Misha Lavrov on August 14, 2020

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$$

Answered by Delta Account on August 14, 2020

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.

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.

Answered by antkam on August 14, 2020

## Related Questions

### Can Laplace’s transformation be equal to a Gaussian for any integer?

2  Asked on November 2, 2021

### Is there analytical solution to this heat equation?

1  Asked on November 2, 2021 by titanium

### Proving Threshold Properties of a Dynamic Programming Problem

0  Asked on November 2, 2021

### Assumptions in converting between nominal/effective interest/discount

1  Asked on November 2, 2021 by minyoung-kim

### How can I prove that 3 planes are arranged in a triangle-like shape without calculating their intersection lines?

7  Asked on November 2, 2021

### Detailed analysis of the secretary problem

1  Asked on November 2, 2021 by saulspatz

### Are all finite-dimensional algebras of a fixed dimension over a field isomorphic to one another?

6  Asked on November 2, 2021 by perturbative

### Why does the plot of $f(x)=|cos x|-|sin x|$ look almost piecewise linear?

2  Asked on November 2, 2021 by meowdog

### Excluded middle, double negation, contraposition and Peirce’s law in minimal logic

2  Asked on November 2, 2021 by lereau

### Does iterating the complex function $zmapstofrac{2sqrt z}{1+z}$ always converge?

3  Asked on November 2, 2021 by mr_e_man

### If an infinite set $S$ of positive integers is equidistributed, is $S+S$ also equidistributed?

1  Asked on November 2, 2021 by vincent-granville

### How to evaluate $int frac{dx}{sin(ln(x))}$?

6  Asked on November 2, 2021

### $lfloorfrac12+frac1{2^2}+frac1{2^3}+cdotsrfloor;$ vs $;lim_{ntoinfty}lfloorfrac12+frac1{2^2}+cdots+frac1{2^n}rfloor$

2  Asked on November 2, 2021 by drift-speed

### Finding the Center of Mass of a disk when a part of it is cut out.

6  Asked on November 2, 2021

### Do functions with the same gradient differ by a constant?

4  Asked on November 2, 2021

### What loops are possible when doing this function to the rationals?

2  Asked on November 2, 2021 by user808945

### Is there an explicit construction of this bijection?

2  Asked on November 1, 2021 by gregory-j-puleo

### How can I determine the radius of 4 identical circles inside an equilateral triangle $ABC$?

5  Asked on November 1, 2021 by user766881

### Prove that $tan^{-1}frac{sqrt{1+x^2}+sqrt{1-x^2}}{sqrt{1+x^2}-sqrt{1-x^2}}=frac{pi}{4}+frac 12 cos^{-1}x^2$

4  Asked on November 1, 2021

### Why is my value for the length of daylight wrong?

2  Asked on November 1, 2021 by user525966