A move replaces the real numbers $a$, $b$, $c$, $d$ by $a - b$, $b - c$, $c - d$, $d - a$. If $a$, $b$, $c$, $d$ are not all equal, show that at least one of
the numbers can exceed $1985$ after a finite number of moves.
Proposed in All-Union Mathematical Olympiad 1985, Soviet Union, Problem 15.
Let $a_n, b_n, c_n, d_n$ be the values of $a, b, c, d$ after $n$ iterations:
$$
\begin{cases}
a_0 &= a,\\
b_0 &= b,\\
c_0 &= c,\\
d_0 &= d,
\end{cases}\qquad
\begin{cases}
a_{n+1} &= a_n - b_n,\\
b_{n+1} &= b_n - c_n,\\
c_{n+1} &= c_n - d_n,\\
d_{n+1} &= d_n - a_n.
\end{cases}
$$
We can express this recurrence relation as the following matrix-vector product $$ \begin{equation} \begin{pmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \\ d_{n+1} \end{pmatrix} = \underbrace{\begin{pmatrix} 1 & -1\\ & 1 & -1\\ & & 1 & -1\\ -1 & & & 1 \end{pmatrix}}_{A} \begin{pmatrix} a_n \\ b_n \\ c_n \\ d_n \end{pmatrix} \implies \begin{pmatrix} a_n \\ b_n \\ c_n \\ d_n \end{pmatrix} = A^n \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}; \end{equation} $$ since we want to study the behavior of $A^n$, it is sensible to try to diagonalize $A$. Notice first that $A = \mathbf 1 - P$, where $P$ is a permutation matrix (i.e., a matrix with the columns of the identity but shuffled); permutation matrices are orthogonal, and therefore they enjoy the property that $\trans P = P^{-1}$. Putting these two facts together proves that $A$ itself is normal $$ A \trans A = (\mathbf 1 + P)(\mathbf 1 + P^{-1}) = 2\mathbf 1 + P + P^{-1} = (\mathbf 1 + P^{-1})(\mathbf 1 + P) = \trans A A; $$ hence, the spectral theorem for normal matrices guarantees that $A$ is orthogonally diagonalizable. From here, through cofactor expansion we can easily obtain the characteristic polynomial of $A$ and solve for its eigenvalues. $$ \chi_A(\lambda) = \det(A - \lambda \mathbf 1) = \begin{vmatrix} 1 - \lambda & -1\\ & 1 - \lambda & -1\\ & & 1 - \lambda & -1\\ -1 & & & 1 - \lambda \end{vmatrix} = (1-\lambda)^4 - 1 = \lambda(\lambda - 2)(\lambda - (1 + i))(\lambda - (1 - i)). $$ Letting now $E(A; \lambda) := \ker(A - \lambda \mathbf 1)$ denote the eigenspace of $A$ corresponding to the eigenvalue $\lambda$, it can be seen after Gaussian elimination that $$ E(A; 0) = \operatorname{span}\left\{\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}\right\}, \qquad E(A; 2) = \operatorname{span}\left\{\begin{pmatrix} -1 \\ 1 \\ -1 \\ 1 \end{pmatrix}\right\}, \qquad E(A; 1+i) = \operatorname{span}\left\{\begin{pmatrix} -i \\ -1 \\ i \\ 1 \end{pmatrix}\right\}, \qquad E(A; 1-i) = \operatorname{span}\left\{\begin{pmatrix} i \\ -1 \\ -i \\ 1 \end{pmatrix}\right\}, $$ and so $$ A = Q\Lambda \adj Q,\qquad Q = \frac{1}{2}\begin{pmatrix} 1 & -1 & -i & i\\ 1 & 1 & -1 & -1\\ 1 & -1 & i & -i\\ 1 & 1 & 1 & 1 \end{pmatrix},\qquad \Lambda = \begin{pmatrix} 0\\ & 2 \\ & & 1 + i\\ & & & 1 - i \end{pmatrix}. $$ All together, one obtains a closed formula for $a_n, b_n, c_n$, and $d_n$ from $(1)$: $$ \begin{align} \begin{pmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \\ d_{n+1} \end{pmatrix} &= A^n \begin{pmatrix} a_n \\ b_n \\ c_n \\ d_n \end{pmatrix} = Q \Lambda^n \adj Q \begin{pmatrix} a_n \\ b_n \\ c_n \\ d_n \end{pmatrix} = \frac{1}{4} \begin{pmatrix} 1 & -1 & -i & i\\ 1 & 1 & -1 & -1\\ 1 & -1 & i & -i\\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0\\ & 2^n\\ & & (1+i)^n\\ & & & (1-i)^n \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1\\ -1 & 1 & -1 & 1\\ i & -1 & -i & 1\\ -i & -1 & i & 1 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}\nonumber\\ &= \frac{1}{4} \begin{pmatrix} 2^n + (1 - i)^n + (1 + i)^n & - 2^n - i(1-i)^n + i(1+i)^n & 2^n - (1 - i)^n - (1 + i)^n & - 2^n + i(1-i)^n - i(1+i)^n\\ - 2^n + i(1-i)^n - i(1+i)^n & 2^n + (1 - i)^n + (1 + i)^n & -2^n - i(1-i)^n + i(1+i)^n & 2^n - (1 - i)^n - (1 + i)^n\\ 2^n - (1 - i)^n - (1 + i)^n & - 2^n + i(1-i)^n - i(1+i)^n & 2^n + (1 - i)^n + (1 + i)^n & - 2^n - i(1-i)^n + i(1+i)^n\\ -2^n - i(1-i)^n + i(1+i)^n & 2^n - (1 - i)^n - (1 + i)^n & - 2^n + i(1-i)^n - i(1+i)^n & 2^n + (1 - i)^n + (1 + i)^n \end{pmatrix} \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}\nonumber\\ &= \frac14 \left(\begin{alignat*}{3} (a - b + c - d)2^n &+ (a - ib - c + id)(1-i)^n &&+ (a + ib - c - id)(1+i)^n\\ -(a - b + c - d)2^n &+ i(a - ib - c + id)(1-i)^n &&- i(a + ib - c - id)(1+i)^n\\ (a - b + c - d)2^n &- (a - ib - c + id)(1-i)^n &&- (a + ib - c - id)(1+i)^n\\ -(a - b + c - d)2^n &- i(a - ib - c + id)(1-i)^n &&+ i(a + ib - c - id)(1+i)^n \end{alignat*}\right); \end{align} $$ it is a rather long expression, although some structure is revealed under closer inspection. Notice that the factors multiplying each power follow the powers of $i$ and $-i$ (and $-1$ for $2^n$); this also occurs when comparing them between rows, but with the opposite sign. From here, we devote our attention to simplify the next two expressions: $$ \begin{align*} (1 + i)^n + (1 - i)^n &= (1 + i)^n + \overline{(1 + i)^n} = 2\re(1+i)^n = 2(\sqrt2)^n \cos(n\pi/4),\\ (1 + i)^n - (1 - i)^n &= (1 + i)^n - \overline{(1 + i)^n} = 2i\im(1+i)^n = i2(\sqrt2)^n \sin(n\pi/4). \end{align*} $$ Thus, equation $(2)$ becomes the following (where $\xi = \pi/4$): $$ \begin{cases} 4a_{n+1} &= (a - b + c - d)2^n + ([a - c]\cos(n\xi) + [-b + d]\sin(n\xi)) 2(\sqrt2)^n,\\ 4b_{n+1} &= -(a - b + c - d)2^n + ([a - c]\sin(n\xi) - [-b + d]\cos(n\xi)) 2(\sqrt2)^n,\\ 4c_{n+1} &= (a - b + c - d)2^n + (-[a - c]\cos(n\xi) - [-b + d]\sin(n\xi)) 2(\sqrt2)^n,\\ 4d_{n+1} &= -(a - b + c - d)2^n + (-[a - c]\sin(n\xi) + [-b + d]\cos(n\xi)) 2(\sqrt2)^n. \end{cases} $$
Finally, determining which one of the numbers can grow arbitrarily large is clear from above. First, we need to evaluate the number $\Delta:=a-b+c-d$:
We can express this recurrence relation as the following matrix-vector product $$ \begin{equation} \begin{pmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \\ d_{n+1} \end{pmatrix} = \underbrace{\begin{pmatrix} 1 & -1\\ & 1 & -1\\ & & 1 & -1\\ -1 & & & 1 \end{pmatrix}}_{A} \begin{pmatrix} a_n \\ b_n \\ c_n \\ d_n \end{pmatrix} \implies \begin{pmatrix} a_n \\ b_n \\ c_n \\ d_n \end{pmatrix} = A^n \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}; \end{equation} $$ since we want to study the behavior of $A^n$, it is sensible to try to diagonalize $A$. Notice first that $A = \mathbf 1 - P$, where $P$ is a permutation matrix (i.e., a matrix with the columns of the identity but shuffled); permutation matrices are orthogonal, and therefore they enjoy the property that $\trans P = P^{-1}$. Putting these two facts together proves that $A$ itself is normal $$ A \trans A = (\mathbf 1 + P)(\mathbf 1 + P^{-1}) = 2\mathbf 1 + P + P^{-1} = (\mathbf 1 + P^{-1})(\mathbf 1 + P) = \trans A A; $$ hence, the spectral theorem for normal matrices guarantees that $A$ is orthogonally diagonalizable. From here, through cofactor expansion we can easily obtain the characteristic polynomial of $A$ and solve for its eigenvalues. $$ \chi_A(\lambda) = \det(A - \lambda \mathbf 1) = \begin{vmatrix} 1 - \lambda & -1\\ & 1 - \lambda & -1\\ & & 1 - \lambda & -1\\ -1 & & & 1 - \lambda \end{vmatrix} = (1-\lambda)^4 - 1 = \lambda(\lambda - 2)(\lambda - (1 + i))(\lambda - (1 - i)). $$ Letting now $E(A; \lambda) := \ker(A - \lambda \mathbf 1)$ denote the eigenspace of $A$ corresponding to the eigenvalue $\lambda$, it can be seen after Gaussian elimination that $$ E(A; 0) = \operatorname{span}\left\{\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}\right\}, \qquad E(A; 2) = \operatorname{span}\left\{\begin{pmatrix} -1 \\ 1 \\ -1 \\ 1 \end{pmatrix}\right\}, \qquad E(A; 1+i) = \operatorname{span}\left\{\begin{pmatrix} -i \\ -1 \\ i \\ 1 \end{pmatrix}\right\}, \qquad E(A; 1-i) = \operatorname{span}\left\{\begin{pmatrix} i \\ -1 \\ -i \\ 1 \end{pmatrix}\right\}, $$ and so $$ A = Q\Lambda \adj Q,\qquad Q = \frac{1}{2}\begin{pmatrix} 1 & -1 & -i & i\\ 1 & 1 & -1 & -1\\ 1 & -1 & i & -i\\ 1 & 1 & 1 & 1 \end{pmatrix},\qquad \Lambda = \begin{pmatrix} 0\\ & 2 \\ & & 1 + i\\ & & & 1 - i \end{pmatrix}. $$ All together, one obtains a closed formula for $a_n, b_n, c_n$, and $d_n$ from $(1)$: $$ \begin{align} \begin{pmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \\ d_{n+1} \end{pmatrix} &= A^n \begin{pmatrix} a_n \\ b_n \\ c_n \\ d_n \end{pmatrix} = Q \Lambda^n \adj Q \begin{pmatrix} a_n \\ b_n \\ c_n \\ d_n \end{pmatrix} = \frac{1}{4} \begin{pmatrix} 1 & -1 & -i & i\\ 1 & 1 & -1 & -1\\ 1 & -1 & i & -i\\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0\\ & 2^n\\ & & (1+i)^n\\ & & & (1-i)^n \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1\\ -1 & 1 & -1 & 1\\ i & -1 & -i & 1\\ -i & -1 & i & 1 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}\nonumber\\ &= \frac{1}{4} \begin{pmatrix} 2^n + (1 - i)^n + (1 + i)^n & - 2^n - i(1-i)^n + i(1+i)^n & 2^n - (1 - i)^n - (1 + i)^n & - 2^n + i(1-i)^n - i(1+i)^n\\ - 2^n + i(1-i)^n - i(1+i)^n & 2^n + (1 - i)^n + (1 + i)^n & -2^n - i(1-i)^n + i(1+i)^n & 2^n - (1 - i)^n - (1 + i)^n\\ 2^n - (1 - i)^n - (1 + i)^n & - 2^n + i(1-i)^n - i(1+i)^n & 2^n + (1 - i)^n + (1 + i)^n & - 2^n - i(1-i)^n + i(1+i)^n\\ -2^n - i(1-i)^n + i(1+i)^n & 2^n - (1 - i)^n - (1 + i)^n & - 2^n + i(1-i)^n - i(1+i)^n & 2^n + (1 - i)^n + (1 + i)^n \end{pmatrix} \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}\nonumber\\ &= \frac14 \left(\begin{alignat*}{3} (a - b + c - d)2^n &+ (a - ib - c + id)(1-i)^n &&+ (a + ib - c - id)(1+i)^n\\ -(a - b + c - d)2^n &+ i(a - ib - c + id)(1-i)^n &&- i(a + ib - c - id)(1+i)^n\\ (a - b + c - d)2^n &- (a - ib - c + id)(1-i)^n &&- (a + ib - c - id)(1+i)^n\\ -(a - b + c - d)2^n &- i(a - ib - c + id)(1-i)^n &&+ i(a + ib - c - id)(1+i)^n \end{alignat*}\right); \end{align} $$ it is a rather long expression, although some structure is revealed under closer inspection. Notice that the factors multiplying each power follow the powers of $i$ and $-i$ (and $-1$ for $2^n$); this also occurs when comparing them between rows, but with the opposite sign. From here, we devote our attention to simplify the next two expressions: $$ \begin{align*} (1 + i)^n + (1 - i)^n &= (1 + i)^n + \overline{(1 + i)^n} = 2\re(1+i)^n = 2(\sqrt2)^n \cos(n\pi/4),\\ (1 + i)^n - (1 - i)^n &= (1 + i)^n - \overline{(1 + i)^n} = 2i\im(1+i)^n = i2(\sqrt2)^n \sin(n\pi/4). \end{align*} $$ Thus, equation $(2)$ becomes the following (where $\xi = \pi/4$): $$ \begin{cases} 4a_{n+1} &= (a - b + c - d)2^n + ([a - c]\cos(n\xi) + [-b + d]\sin(n\xi)) 2(\sqrt2)^n,\\ 4b_{n+1} &= -(a - b + c - d)2^n + ([a - c]\sin(n\xi) - [-b + d]\cos(n\xi)) 2(\sqrt2)^n,\\ 4c_{n+1} &= (a - b + c - d)2^n + (-[a - c]\cos(n\xi) - [-b + d]\sin(n\xi)) 2(\sqrt2)^n,\\ 4d_{n+1} &= -(a - b + c - d)2^n + (-[a - c]\sin(n\xi) + [-b + d]\cos(n\xi)) 2(\sqrt2)^n. \end{cases} $$
Finally, determining which one of the numbers can grow arbitrarily large is clear from above. First, we need to evaluate the number $\Delta:=a-b+c-d$:
- $\Delta \neq 0$: When $\Delta > 0$ both $a_n$ and $c_n$ divergent to positive infinity because $2^n$ dominates asymptotically over $(\sqrt2)^n$. On the contrary, if $\Delta$ is negative, by the same argument $b_n$ and $d_n$ are the increasing ones.
- $\Delta = 0$: Notice that both $a - c$ and $b - d$ cannot be zero as well, since that would imply first $a = c, b = d$, and next $a = b$; they
are all equal, which contradicts the original statement.
- If $a - c \neq 0$, pick $n = 8k$ to make the sine zero again; if $a - c > 0$ then $a_n \to \infty$, otherwise $c_n \to \infty$.
- If $b - d \neq 0$, pick $n \equiv 2 \pmod 8$ to cancel the cosine; when $b - d > 0$ then $c_n \to \infty$, if not $a_n \to \infty$.