HMMT November, 2017

Solution:

To simplify the solution, we instead consider the equivalent problem of reducing a passcode to $0000$ using the given move.

Given a passcode $a_{1} a_{2} a_{3} a_{4}$, define a differential of the passcode to be a quintuple $(d_{1}, d_{2}, d_{3}, d_{4}, d_{5})$ such that $d_{i} \equiv a_{i}-a_{i-1} \pmod{10}$ for $i=1,2,3,4,5$, where we define $a_{0}=a_{5}=0$.

Claim 1: For any passcode, there exists a differential that satisfies the following two conditions:
- $d_{1}+d_{2}+d_{3}+d_{4}+d_{5}=0$;
- The range (difference between the maximum and minimum) of these five numbers is at most $10$.

Proof: We first see that the differential defined by $d_{i}=a_{i}-a_{i-1}$ satisfy the first condition since the sum of the five numbers is $a_{5}-a_{0}=0$. Suppose that a differential satisfying the first condition has a range greater than $10$, then we take one of the largest number $d_{m}$ and one of the smallest number $d_{n}$ (where $d_{m}-d_{n}>10$), and replace the former by $d_{m}-10$ and the latter by $d_{n}+10$. This will either reduce the range or reduce the number of maximal and minimal numbers, so the process will terminate after finitely many iterations. Thus we can find a differential that satisfies both conditions.

(Note: we call such a differential a standard differential from now on, although it is important to remember that there may be more than one standard differential for one passcode. As a corollary, all of the numbers in a standard differential must be in the range $[-9,9]$, as a number greater than $9$ will be more than $10$ away from a negative number, and similar for a number smaller than $-9$.)

Given a passcode, we define the magnitude of one of its standard differentials to be the sum of all the positive values in the differential (which is also the absolute value of the sum all the negative values).

Claim 2: The magnitude of a passcode's standard differential is equal to the passcode's complexity.

Proof: Obviously $0000$ is the only passcode with complexity $0$ whose standard differential has magnitude $0$. Suppose that the magnitude of a standard differential is $M$, then it suffices show that the magnitude can be reduced to $0$ in $M$ moves, and that the magnitude can only decrease by at most $1$ with each move.

The first part can be shown via the following algorithm. When the magnitude is not zero, there must be a positive number $d_{i}$ and a negative number $d_{j}$. WLOG assume that $i<j$, then after taking the dials $a_{i}, a_{i+1}, \ldots, a_{j-1}$ and decreases them all by $1$, $d_{i}$ decreases by $1$ and $d_{j}$ increases by $1$. This will decrease the magnitude by $1$ (and the differential remains standard), so by repeating this process $M$ times we can bring the magnitude down to $0$.

For the second part, we assume WLOG that we take the dials $a_{i}, a_{i+1}, \ldots, a_{j-1}$ and decrease them all by $1$, and then $d_{i}$ is replaced by $d_{i}'=d_{i}-1$ and $d_{j}'=d_{j}+1$. If the differential remains standard, then the magnitude decreases by $1$ (when $d_{i}>0$ and $d_{j}<0$), remains the same (when either $d_{i} \leq 0$ and $d_{j}<0$ or $d_{i}>0$ and $d_{j} \geq 0$), or increases by $1$ (when $d_{i} \leq 0$ and $d_{j} \geq 0$).

In the latter two cases, it is possible that the differential is no longer standard.

If the magnitude previously remained the same (WLOG suppose that $d_{i}>0$ and $d_{j} \geq 0$), then there exists a negative $d_{k}$ that is minimal such that $d_{j}-d_{k}=10$ and now $d_{j}'$ is the unique maximum. Replacing $d_{k}$ by $d_{k}+10=d_{j}$ and $d_{j}'$ by $d_{j}'-10=d_{k}+1$ will reduce the magnitude by $1$, and the new differential will be standard because the unique maximum $d_{j}'$ is no longer present and the minimum is now either $d_{k}$ or $d_{k}+1$. This means that the magnitude decreases by at most $1$.

If the magnitude previously increased by $1$ (when $d_{i} \leq 0$ and $d_{j} \geq 0$), then there exists either a negative $d_{k}$ that is (previously) minimal such that $d_{j}-d_{k}=10$, or a positive $d_{l}$ that is (previously) maximal such that $d_{l}-d_{i}=10$, or both. By similar logic as the previous case, replacing $d_{k}$ by $d_{k}+10$ and $d_{j}'$ by $d_{j}'-10$, or replacing $d_{l}$ by $d_{l}-10$ and $d_{i}'$ by $d_{i}'+10$ (or both, if both $d_{k}$ and $d_{l}$ exist), will decrease the magnitude by $1$, and ensure that the new differential is standard. The replacement will decrease the current magnitude by at most $2$, this means that the original magnitude decreases by at most $1$ in total.

These considerations finishes the second part and therefore the proof.

With this claim, we also see that the magnitudes of all possible standard differentials of a given passcode are the same, so the choice of the differential is irrelevant.

We can now proceed to find the maximum possible complexity. Suppose that there are $m$ positive numbers and $n$ negative numbers in the differential, and suppose that the maximum and the minimum are $x$ and $-y$ respectively. Since the sum of all positive numbers is at most $m x$ and the absolute value of the sum of all negative numbers is at most $n y$, the complexity is at most $C=\min (m x, n y)$. It suffices to maximize $C$ under the condition that $m+n \leq 5$ and $x+y=x-(-y) \leq 10$. It is not difficult to see (via casework) that the maximal $C$ is $12$, achieved by $m=2, n=3, x=6, y=4$ or $m=3, n=2, x=4, y=6$. In the first case, the digits must increase from $0$ by $6$ twice and decrease by $4$ three times (and reduced modulo $10$), which gives the passcode $6284$; in the second case the digits increase by $4$ three times and decrease by $6$ twice instead, which gives the passcode $4826$. Since all inequalities are tight, these two passcodes are the only ones that have the maximal complexity of $12$.