Forty Cubed, Forty Squared, and the Number You Never Choose

A safe takes three numbers from a dial marked 1 to 40, so there are 64,000 combinations, and the worst case is 1600 attempts rather than 64,000. The third number is supplied by the mechanism instead of guessed, which collapses the search from three dimensions to two, and 1600 is proved both achievable and unavoidable. A dial with a mark of mechanical slack drops the count to 196, which is a covering problem on a cycle of forty.

You have forgotten the combination to your own safe. It takes three numbers in order, each read off a dial marked 1 to 40, and you are prepared to sit there and work through possibilities until it opens. How many attempts does that take in the worst case?

The answer almost everyone gives is 64,000, and the multiplication behind it is faultless. The real figure is 1600. The gap is not an arithmetic slip; it is a factor of forty that comes from paying attention to how the mechanism reports success.

Where 64,000 comes from

A combination is an ordered triple, repeats allowed, each entry from a set of forty. The rule of product gives

40 \times 40 \times 40 \;=\; 40^{3} \;=\; 64{,}000

(1)

Every step there is right. There really are 64,000 combinations, and if you had to present each one as a complete guess and receive a single yes or no, then 64,000 would be the worst-case count and there would be nothing more to say. What the calculation encodes, silently, is a model of what an attempt looks like. That is the part worth doubting.

The coordinate you never choose

A mechanical combination lock does not wait for you to finish before deciding. Each number parks one wheel; when all three wheels are aligned, the bolt drops. So set the first two numbers, then turn the last wheel slowly and continuously. If the pair you set is the right one, the safe opens the moment the third number passes under the mark, and it does so without you having chosen it. If the pair is wrong, the whole sweep produces nothing and you have ruled out all forty triples that begin with that pair.

The third number is therefore not something you search. It is something the hardware hands you. What you search is the set of ordered pairs:

40 \times 40 \;=\; 40^{2} \;=\; 1600 \qquad \frac{40^{3}}{40^{2}} = 40

(2)

One attempt

An attempt is one ordered pair of first and second numbers, followed by one continuous sweep of the third wheel. The whole answer depends on that accounting: an attempt costs a pair and clears forty combinations at once. Charge attempts by the triple instead and you are back to 64,000, which is the correct answer to a question about a lock that only reports on complete entries.

The map that sends a combination $(a, b, c)$ to its pair $(a, b)$ is forty to one and onto. So the 1600 pairs partition the 64,000 combinations into 1600 classes of exactly forty, and a schedule that visits every pair once meets every combination. This was checked by walking all 64,000 triples and confirming that each is opened by exactly one of the 1600 sweeps, with none left over.

Fig. 1 — The search happens in two dimensions, not three. The third axis is collapsed by the sweep, and one cell of the grid stands for forty combinations.

Enough, and also unavoidable

Showing that 1600 attempts suffice is only half the claim. A worst-case count also has to be a lower bound, otherwise some cleverer schedule might do better and the honest answer would be smaller. The lower bound here is short. One attempt eliminates exactly one pair, no more, because a failed sweep tells you nothing about any other pair. So whatever order you choose to visit the pairs in, an adversary who gets to place the true combination after seeing your order can put it in the pair you visit last. That forces all 1600.

This was tested rather than asserted: the adversary was run against the natural ordering and against two hundred randomly shuffled orderings, and every one of them was forced to the full count. So 1600 is the answer to the question as asked, in both directions.

It is a worst case, and that distinction matters more than it looks. If the combination is uniformly random, you expect to find it after roughly half the pairs, so about 800 attempts. Anyone quoting 1600 as the typical effort has mixed up a guarantee with an average.

The general count

Nothing above used the numbers three or forty. For a lock that takes $n$ numbers from a dial of $m$ marks, with the same sweep available on the final wheel:

\#\text{attempts} \;=\; m^{\,n-1} \qquad \text{rather than} \qquad m^{\,n}

(3)

One coordinate is free, and only one. The sweep works on the last wheel because that is the wheel whose alignment completes the mechanism; the earlier wheels have to be parked before the sweep begins, so there is no way to make two of them free at once. Adding a fourth number to the dial multiplies the work by forty again, which is why the exponent, and not the base, is what a lock designer should care about.

What mechanical slack buys

Real dials are not exact. A wheel typically catches even when the dial is parked a mark or so away from the true value, because the notch it has to find is wider than a single graduation. That is a claim about hardware rather than mathematics, and it should be labelled as an assumption, but if it holds then you no longer need to try every mark.

Suppose a setting of $p$ catches whenever the true value lies within $t$ marks of $p$ . Then a set of settings works precisely when the bands of width $2t+1$ around them cover all $m$ marks, which is a covering problem on a cycle of $m$ vertices. The smallest such set has $\lceil m/(2t+1) \rceil$ elements, so the count becomes

\left\lceil \frac{m}{2t+1} \right\rceil^{\,n-1} \;\xrightarrow[\;m=40,\ t=1,\ n=3\;]{}\; \left\lceil \tfrac{40}{3} \right\rceil^{2} = 14^{2} = 196

(4)

Under 200, and the 14 is exact rather than an approximation: thirteen settings cover at most 39 marks, so fourteen are necessary, and an explicit set of fourteen covering all forty was constructed and checked both on the line and on the circle. It is tempting to write $(40/3)^2 \approx 178$ and call that the answer, which is the right order of magnitude and not an attainable count, because you cannot try a third of a mark.

Fig. 2 — With a tolerance of one mark either side, fourteen settings cover a forty-mark dial, and thirteen cannot. Each axis shrinks by that factor, so the pair count falls from 1600 to 196.

Where the argument fails

Two premises carry the whole thing, and both are falsifiable. The first is that the lock acts on a partially correct entry. That is what the sweep exploits, and it is why an electronic keypad is a different problem: a keypad accumulates the digits, compares once, and reports a single verdict, so there is no continuous motion to hide a coordinate inside and the count goes back to $m^n$ . The second is the tolerance, which is a property of a particular piece of metal. A lock built with a notch narrower than one graduation gives you 1600 and nothing better.

There is a general habit here that outlives the puzzle. Before counting a search space, work out what a single probe actually costs and what it actually rules out. The reflex answer counts the states; the right answer counts the probes, and one probe can eliminate a whole family of states at once. That is the same observation behind grouping items into batches when the test is expensive, and behind asking questions that split a set in half rather than questions that check one element.

Sources and further reading

The counting rule behind equations (1) and (2) — Rule of product
How the mechanism in the second section is built — Combination lock
The covering problem in equation (4), whose answer on a cycle is one third of the vertices rounded up — Dominating set
Where worst-case and average-case counts come apart — Worst-case complexity

The counts were verified by exhaustive enumeration rather than by sampling: all 64,000 combinations were walked against all 1600 sweeps, the adversary bound was run over two hundred attempt orderings, and the fourteen-mark covering set was checked against its own lower bound.