1
$\begingroup$

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)$$

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

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$.


Details of the induction, as requested:

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.

$\endgroup$
  • $\begingroup$ Details would be helpful if you wouldn't mind. $\endgroup$ – Lebes Apr 29 '15 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.