# Solution Invariant Explanation Trick

Suppose not all 4 integers, $a,b,c,d$ are equal. Start with $(a,b,c,d)$ and repeatedly replace $(a,b,c,d)$ by $(a−b,b−c,c−d,d−a)$. Then show that at least one number of the quadruple will become arbitrarily large.

Solution:

We have $$(a_{n+1},b_{n+1},c_{n+1},d_{n+1}) = (a_n-b_n,b_n-c_n,c_n-d_n,d_n-a_n)$$ As you have rightly observed, the invariant is $a_n+b_n+c_n+d_n = 0$ for all $n \geq 1$, where $a_0 = a$, $b_0=b$, $c_0 = c$ and $d_0 = d$. Let us now look at $a_{n+1}^2+b_{n+1}^2 + c_{n+1}^2 + d_{n+1}^2$. We have \begin{align} a_{n+1}^2+b_{n+1}^2 + c_{n+1}^2 + d_{n+1}^2 & = (a_n-b_n)^2+(b_n-c_n)^2+(c_n-d_n)^2 + (d_n-a_n)^2\\ & = 2(a_n^2+b_n^2+c_n^2+d_n^2) - 2(a_nb_n+b_nc_n+c_nd_n+d_na_n) & (\spadesuit) \end{align} We shall now show that $- 2(a_nb_n+b_nc_n+c_nd_n+d_na_n)$ is non-negative for $n \geq 1$. Since $a_n+b_n+c_n+d_n=0$, we have \begin{align} 0 & = (a_n+b_n+c_n+d_n)^2 = (a_n+c_n)^2 + (b_n+c_n)^2 + 2(a_n+c_n)(b_n+d_n)\\ & = (a_n+c_n)^2 + (b_n+c_n)^2 + 2a_nb_n + 2b_nc_n + 2c_nd_n + 2d_na_n \end{align} This gives us $$-2(a_nb_n+b_nc_n+c_nd_n+d_na_n) = (a_n+c_n)^2 + (b_n+c_n)^2 \geq 0 \,\,\, (\clubsuit)$$ Making use of $(\clubsuit)$ in $(\spadesuit)$, we obtain that $$a_{n+1}^2+b_{n+1}^2 + c_{n+1}^2 + d_{n+1}^2 \geq 2(a_n^2+b_n^2+c_n^2+d_n^2)$$ This gives us $$a_{n+1}^2+b_{n+1}^2 + c_{n+1}^2 + d_{n+1}^2 \geq 2^n(a_1^2+b_1^2+c_1^2+d_1^2)$$ Since $a, b,c,d$ are distinct, one of the terms $a_1,b_1,c_1$ or $d_1$ is non-zero. Hence, $a_{n+1}^2+b_{n+1}^2 + c_{n+1}^2 + d_{n+1}^2$ grows unbounded, which means the largest of the terms must keep growing unbounded.

I understand everything until the end. I got:

$$a_{n+1}^2 + b_{n+1}^2 + c_{n+1}^2 + d_{n+1}^2 \ge 2(a_n^2 + b_n^2 + c_n^2 + d_n^2)$$

How do you get to:

$$a_{n+1}^2+b_{n+1}^2 + c_{n+1}^2 + d_{n+1}^2 \geq 2^n(a_1^2+b_1^2+c_1^2+d_1^2)$$

• $\phantom{}$ Induction. – Jack D'Aurizio Apr 29 '15 at 17:15

Set $x_n=a_n^2+b_n^2+c_n^2+d_n^2$. The relationship, to be used repeatedly, is $$\color{red}{ x_{n+1}\ge 2 x_n,\text{ for all }n\in\mathbb{N}}.$$ Hence $$x_4\ge 2x_3\ge 2(2x_2)\ge 2(2(2x_1))=2^3x_1$$ We can prove by induction that $x_{n+1}\ge 2^n x_1$.
The base case is $n=1$, and $x_2\ge 2^1x_1$.
Suppose now that $x_{n+1}\ge 2^n x_1$. By the relationship property we are given, $x_{n+2}\ge 2x_{n+1}$. Combining with the inductive hypothesis we have $$x_{n+2}\ge 2x_{n+1}\ge 2(2^n x_1)=2^{n+1}x_1$$ This establishes the induction.