Mathematical Reflections 2016, Issue 3 - Problem O373

Problem:Let $n \geq 3$ be a natural number. On a $n \times n$ table we perform the following operation: choose a $(n-1) \times (n-1)$ square and add or subtract $1$ to all its entries. At the beginning all the entres in the table are $0$. Is it possible after a finite number of operations to obtain all the natural numbers from $1$ to $n^2$ in the table?

Proposed by Alessandro Ventullo, Milan, Italy

Solution:
The answer is no. Observe that after each operation on a $(n-1) \times (n-1)$ square, the sum of all the elements in the $n \times n$ table is constant modulo $(n-1)^2$. Since at the beginning the table is filled with zeros, then after any finite number of operations the sum of the elements in the table is divisible by $(n-1)^2$. On the other hand, $$S=1+2+\ldots+n^2=\dfrac{n^2(n^2+1)}{2}.$$
If $n$ is even, then $n=2k$ where $k \geq 2$, and $$S=2k^2(4k^2+1).$$ Assume that $(2k-1)^2 \ | \ S$. Then $(2k-1)^2 \ | \ 2S=4k^2(4k^2+1)$. Since $(2k-1,2k)=1$, then $((2k-1)^2,4k^2)=1$. It follows that $(2k-1)^2 \ | \ (4k^2+1)$, i.e. $(2k-1)^2 \ | \ 4k$. This leads to $(2k-1)^2 \leq 4k$, which is false for $k \geq 2$.
If $n$ is odd, then $n=2k+1$, where $k \geq 1$ and $$S=(2k+1)^2(2k^2+2k+1).$$ Assume that $4k^2 \ | \ S$. Then $4k^2 \ | \ 2S=(2k+1)^2(4k^2+4k+2)$. Since $(2k,2k+1)=1$, then $(4k^2,(2k+1)^2)=1$. It follows that $4k^2 \ | \ (4k^2+4k+2)$, i.e. $4k^2 \ | \ (4k+2)$. This leads to $4k^2 \leq 4k+2$, which is false for $k \geq 2$. Moreover, if $k=1$, then $4 \nmid 6$.
In conclusion, $(n-1)^2$ doesn't divide $\dfrac{n^2(n^2+1)}{2}$ for any $n \geq 3$ and the conclusion follows.

Note:1) Observe that if $n=2$, it is possible to obtain all the natural numbers from $1$ to $4$ with the above operations, since it is possible to increase any $1 \times 1$ square by any quantity. This accords with the fact that $1$ divides $1+2+3+4=10$ trivially.
2) Li Zhou gave a very clever solution to the general problem in which the entries of the $(n-1) \times (n-1)$ square are not changed by the same quantity (for example to the first entry add $1$, and to the other entries add $-1$ and so on). See the original solution published on Mathematical Reflections 3/2016.

Mathematical Reflections 2016, Issue 3 - Problem U374

Problem:
Let $p$ and $q$ be complex numbers such that two of the zeros $a,b,c$ of the polynomial $x^3+3px^2+3qx+3pq=0$ are equal. Evaluate $a^2b+b^2c+c^2a$.

Proposed by Titu Andreescu, University of Texas at Dallas, USA

Solution:
Assume without loss of generality that $a=b$. Then, $a^2b+b^2c+c^2a=b^3+b^2c+bc^2$. By Vi\`ete's Formulas, we have $$\begin{array}{rcl} abc&=&-3pq \\ ab+bc+ca&=&3q \\ a+b+c&=&-3p. \end{array}$$ Since $a=b$, we have $$\begin{array}{rcl} b^2c&=&-3pq \\ b^2+2bc&=&3q \\ 2b+c&=&-3p. \end{array}$$ Multiplying side by side the last two equations, we get $$(b^2+2bc)(2b+c)=-9pq.$$ Since $-9pq=3(-3pq)=3b^2c$, we get $$(b^2+2bc)(2b+c)=3b^2c,$$ i.e. $$b^3+b^2c+bc^2=0.$$ It follows that $a^2b+b^2c+c^2a=0$.

Mathematical Reflections 2016, Issue 3 - Problem U373

Problem:
Prove the following inequality holds for all positive integers $n \geq 2$,
$$\left(1+\dfrac{1}{2}\right)\left(1+\dfrac{1}{1+2+3}\right)\cdot\ldots\cdot\left(1+\dfrac{1}{1+2+\ldots+n}\right)<3.$$

Proposed by Nguyen Viet Hung, Hanoi University of Science, Vietnam

Solution:
Since $1+2+\ldots+j=\dfrac{j(j+1)}{2}$ for any $j=2,\ldots,n$, we have $$\left(1+\dfrac{1}{2}\right)\left(1+\dfrac{1}{1+2+3}\right)\cdot\ldots\cdot\left(1+\dfrac{1}{1+2+\ldots+n}\right)=\prod_{j=2}^n \left(1+\dfrac{2}{j(j+1)}\right).$$ Using the AM-GM Inequality, we have
$$\prod_{j=2}^n \left(1+\dfrac{2}{j(j+1)}\right) \leq \left(\dfrac{n-1+2\sum_{j=2}^n \frac{1}{j(j+1)}}{n-1}\right)^{n-1}=\left(1+\dfrac{1-\frac{2}{n+1}}{n-1}\right)^{n-1}=\left(1+\dfrac{1}{n+1}\right)^{n-1}.$$
By the Binomial Theorem, we have $$\left(1+\dfrac{1}{n+1}\right)^{n-1}=\sum_{k=0}^{n-1} {n-1 \choose k} \dfrac{1}{(n+1)^k}=\sum_{k=0}^{n-1} \dfrac{(n-1)!}{(n-1-k)!(n+1)^k}\cdot\dfrac{1}{k!}.$$ Since $\dfrac{(n-1)!}{(n-1-k)!(n+1)^k}<1$ and $\dfrac{1}{k!} \leq \dfrac{1}{2^{k-1}}$ for all $k \geq 2$, then
$$\left(1+\dfrac{1}{n+1}\right)^{n-1} \leq \sum_{k=0}^{n-1} \dfrac{1}{k!} < 1+1+\sum_{k=2}^{n-1} \dfrac{1}{2^{k-1}}<3,$$ which gives the desired conclusion.

Mathematical Reflections 2016, Issue 3 - Problem S374

Problem:
Let $a,b,c$ be positive real numbers. Prove that at least one of the numbers $$\dfrac{a+b}{a+b-c}, \qquad \dfrac{b+c}{b+c-a}, \qquad \dfrac{c+a}{c+a-b}$$ is not in the interval $(1,2)$.

Proposed by Titu Andreescu, University of Texas at Dallas, USA

Solution:
Assume by contradiction that all the given numbers are in the interval $(1,2)$. Then,
$$\dfrac{a+b}{a+b-c} > 1, \qquad \dfrac{b+c}{b+c-a} > 1, \qquad \dfrac{c+a}{c+a-b} > 1,$$ which gives
$$\dfrac{c}{a+b-c}>0, \qquad \dfrac{a}{b+c-a}>0, \qquad \dfrac{b}{c+a-b}>0.$$ Since $a,b,c$ are positive real numbers, then $a+b-c>0, b+c-a>0$ and $c+a-b>0$. Moreover,
$$\dfrac{a+b}{a+b-c} < 2, \qquad \dfrac{b+c}{b+c-a} < 2, \qquad \dfrac{c+a}{c+a-b} < 2,$$ which gives $$\dfrac{2c-a-b}{a+b-c}<0, \qquad \dfrac{2a-b-c}{b+c-a}<0, \qquad \dfrac{2b-c-a}{c+a-b}<0.$$ Since all the denominators are positive, then $2c-a-b<0$, $2a-b-c<0$, $2b-c-a<0$. Adding these three inequalities, we get $0<0$, contradiction. It follows that one of the three given numbers is not in the interval $(1,2)$.

Mathematical Reflections 2016, Issue 3 - Problem J375

Problem:
Solve in real numbers the equation $$\sqrt[3]{x}+\sqrt[3]{y}=\dfrac{1}{2}+\sqrt{x+y+\dfrac{1}{4}}$$

Proposed by Adrian Andreescu, Dallas, TX, USA

Solution:
Let $\sqrt[3]{x}=a$ and $\sqrt[3]{y}=b$. Then, $x=a^3$ and $y=b^3$ and the given equation becomes $$a+b-\dfrac{1}{2}=\sqrt{a^3+b^3+\dfrac{1}{4}}.$$ Squaring both sides, we have $$a^2+b^2+2ab-a-b=a^3+b^3,$$ i.e. $$(a+b)(a+b-1)=(a+b)(a^2-ab+b^2).$$ If $a+b=0$, then $x=-y$, but substituting into the original equation, we get $0=1$, contradiction. Then, $$a+b-1=a^2-ab+b^2,$$ i.e. $$a^2-a(b+1)+b^2-b+1=0.$$ Solving this equation for $a$, we obtain the discriminant $\Delta_a=(b+1)^2-4(b^2-b+1)=-3(b-1)^2 \leq 0$, so a real solutions exists if and only if $b-1=0$, i.e. $b=1$. Substituting this value, we get $(a-1)^2=0$, so $a=1$. We conclude that the given equation has only the real solution $(x,y)=(1,1)$.

Mathematical Reflections 2016, Issue 3 - Problem J373

Problem:
Let $a,b,c$ be real numbers greater than $-1$. Prove that $$(a^2+b^2+2)(b^2+c^2+2)(c^2+a^2+2) \geq (a+1)^2(b+1)^2(c+1)^2.$$

Proposed by Adrian Andreescu, Dallas, TX, USA

Solution:
By the AM-GM Inequality, we have $$a^2+b^2+2=(a^2+1)+(b^2+1) \geq 2\sqrt{(a^2+1)(b^2+1)}.$$ Likewise, $b^2+c^2+2 \geq 2\sqrt{(b^2+1)(c^2+1)}$ and $c^2+a^2+2 \geq 2\sqrt{(c^2+1)(a^2+1)}$, so
$$(a^2+b^2+2)(b^2+c^2+2)(c^2+a^2+2) \geq 8(a^2+1)(b^2+1)(c^2+1). \qquad                  (1)$$
By the Cauchy-Schwarz Inequality, we have $$2(a^2+1)=(1+1)(a^2+1) \geq (a+1)^2.$$
Likewise, $2(b^2+1) \geq (b+1)^2$ and $2(c^2+1) \geq (c+1)^2$, so
$$8(a^2+1)(b^2+1)(c^2+1) \geq (a+1)^2(b+1)^2(c+1)^2. \qquad                                (2)$$
By inequalities (1) and (2), we obtain the desired inequality.

Recreatii Matematice 1/2016, Problem VIII.201

Problem:
Prove that the number $2(n^4-n^2+1)$ is the sum of two perfect squares for all $n \in \mathbb{N}$.

Proposed by Alessandro Ventullo, Milan, Italy

Solution:We have $$\begin{array}{lll}2(n^4-n^2+1)&=&2n^2(n^2-1)+2\\&=&2n\cdot(n+1)n(n-1)+2\\&=&[(n+2)+(n-2)](n+1)n(n-1)+2\\&=&(n+2)(n+1)n(n-1)+1+(n+1)n(n-1)(n-2)+1 \\&=&[(n+2)(n-1)(n+1)n+1]+[(n+1)(n-2)n(n-1)+1]\\&=&[(n^2+n-2)(n^2+n)+1]+[(n^2-n-2)(n^2-n)+1]\\&=&(n^2+n-1)^2+(n^2-n-1)^2. \end{array}$$