Problem 3. We are given a combination lock consisting of 6 rotating discs. Each disc consists of digits $0,1,2, \ldots, 9$, in that order (after digit 9 comes 0 ). Lock is opened by exactly one combination. A move consists of turning one of the discs one digit in any direction and the lock opens instantly if the current combination is correct. Discs are initially put in the position 000000, and we know that this combination is not correct.

a) What is the least number of moves necessary to ensure that we have found the correct combination?

b) What is the least number of moves necessary to ensure that we have found the correct combination, if we know that none of the combinations $000000,111111,222222, \ldots, 999999$ is correct?

(Ognjen Stipetić, Grgur Valentić)
Solution. We will solve the subproblems seperately.

a) In order to ensure that we have discovered the code we need to check all but one of the combinations (as otherwise all unchecked codes can be the correct combination). Total number of combinations is $10^{6}$ (as each of the 6 discs consists of 10 digits). As we are given that 000000 is not the correct combination we require at least $10^{6}-2$ moves. We will now prove that there is a sequence of $10^{6}-2$ moves each checking a different combination. We will prove this by induction on the number of wheels where the case $n=6$ is given in the problem.

Claim: For a lock of $n$ wheels and for any starting combination of the wheels $\left(a_{1} a_{2} \ldots a_{n}\right)$ there is a sequence of moves checking all $10^{6}$ combinations exactly once, for all $n \in \mathbb{N}$.

BASIS: For $n=1$ and for the starting combination $(a)$, we consider the sequence of moves

$$
a \rightarrow a+1 \rightarrow a+2 \rightarrow \ldots \rightarrow 9 \rightarrow 0 \rightarrow 1 \rightarrow \ldots \rightarrow a-1
$$

Assumption: The induction claim is valid for some $n \in \mathbb{N}$.

Step: We will prove that the claim holds for $n+1$ as well. We consider an arbitrary starting state $\left(a_{1} a_{2} \ldots a_{n} a_{n+1}\right)$. By the induction hypothesis there is a sequence of moves such that starting from this state we can check all the states showing $a_{n+1}$ on the last disc. Let this sequence of moves end with the combination $\left(b_{1} b_{2} \ldots b_{n} a_{n+1}\right)$.

Now we make the move $\left(b_{1} b_{2} \ldots b_{n} a_{n+1}\right) \rightarrow\left(b_{1} b_{2} \ldots b_{n} a_{n+1}+1\right)$ (if $a_{n+1}$ is 9 , then we turn the disc to show 0 ).

We continue in the same way applying the induction hypothesis on first $n$ discs and the rotation the $n+1$-st disc. This way we get the sequence of moves

$$
\begin{gathered}
\left(a_{1} a_{2} \ldots a_{n} a_{n+1}\right) \rightarrow\left(b_{1} b_{2} \ldots b_{n} a_{n+1}\right) \rightarrow\left(b_{1} b_{2} \ldots b_{n} a_{n+1}+1\right) \\
\quad \rightarrow\left(c_{1} c_{2} \ldots c_{n} a_{n+1}+1\right) \rightarrow\left(c_{1} c_{2} \ldots c_{n} a_{n+1}+2\right) \\
\quad \ldots \\
\quad \rightarrow\left(j_{1} j_{2} \ldots j_{n} a_{n+1}-2\right) \rightarrow\left(j_{1} j_{2} \ldots j_{n} a_{n+1}-1\right)
\end{gathered}
$$

This sequence checks each combination exactly once finishing the induction and proving our claim.

b) As in the a) part, we conclude that we have to check all the combinations apart from 000000, 111111, ..., 999999 and we can be sure as to what is the solution before the move checking the last combination.

We denote the combination as black if the sum of its digits is even and white if that sum is odd. We can notice that all the combinations 000000, 111111, ..., 999999 are black and by each move we swap the color of the current combination.

Number of black combinations all of which we need to check at least once is $\frac{10^{6}}{2}-10$ while number of such white combinations is $\frac{10^{6}}{2}$.

As we are checking white combinations every second move, in order to check all $\frac{10^{6}}{2}$ white combination swe need at least $2 \frac{10^{6}}{2}-1=10^{6}-1$ moves, thus we need at least $10^{6}-2$ moves to find the correct combination.

An example doing this in $10^{6}-2$ moves has been given in part a).