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

Is a convex set of permutation matrices $ntimes n$ ($mathbb{P}_{n}cap mathbb{C}$) a singleton?

0  Asked on November 14, 2021 by joey-cho

Let $0leq a leq b leq 1$. Then we have for all natural numbers $mgeq 2$ the inequality $b^{frac m2}-a^{frac m2} leqfrac m2(b-a)$

3  Asked on November 14, 2021 by giuliano-cantina

Let $x=begin{bmatrix}3cr4end{bmatrix}$ and $A=begin{bmatrix}0&x^Tcr x&0end{bmatrix}$ is A diagonizable?

1  Asked on November 14, 2021

Is a directed graph different from a flow graph?

1  Asked on November 14, 2021

The diophantine equation $m = x^2 + 7y^2$

2  Asked on November 14, 2021 by peter-petrov

Is there any visual representation on why (certain) trigonometric functions have infinite derivatives.

2  Asked on November 14, 2021 by teabx

Is $(I circ A – I circ B)$ positive semi-definite if $A$, $B$ and $A – B$ are positive semi-definite?

1  Asked on November 14, 2021

$f^{*}$ is surjective if and only if $f$ is injective

2  Asked on November 14, 2021 by air-mike

Rational singularity of Spec, Proj and Spec of localization of a standard graded $2$-dimensional ring

0  Asked on November 14, 2021

Determine the lie algebra of the subgroup of SO(4)

3  Asked on November 14, 2021 by shreedhar-bhat

How to use general recursion to generate a set of words?

2  Asked on November 14, 2021 by pwelb

Calculate Hessian of a “weird” function

2  Asked on November 12, 2021 by ben-schneider

Find volume under given contraints on the Cartesian plane.

2  Asked on November 12, 2021 by pavel-fedotov

Equivalence of Classical Nullstellensatz to “Affine schemes have points”

1  Asked on November 12, 2021

A donut shop sells 12 types of donuts. A manager wants to buy six donuts, one for himself and 5 for his employees.

1  Asked on November 12, 2021 by daniel-sidorkin

A compact normal operator is diagonalisable.

1  Asked on November 12, 2021 by user745578

If complex matrices $A$, $B$, $AB-BA$ are nilpotent, show that $A+B$ is nilpotent.

0  Asked on November 12, 2021 by rex-wang

Integral with an index

1  Asked on November 12, 2021

How do I find the probability distribution of a dependent variable given the probability distributions of its independent variables?

0  Asked on November 12, 2021 by tempuserperson

Show that $sup_{k geq 1 }inf_{n geq k} a_n = inf_{k geq 1} sup_{n geq k} a_n$ for an alternating sequence

1  Asked on November 12, 2021 by fratsourced