Mathematical Reflections 2017, Issue 1 - Problem O397

Problem:
Solve in integers the equation: $$(x^3-1)(y^3-1)=3(x^2y^2+2).$$

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

Solution:
The given equation can be written as $$x^3y^3-(x^3+y^3)-3x^2y^2=5.$$ Let $s=x+y$ and $t=xy$. Observe that $x^3+y^3=(x+y)^3-3xy(x+y)=s^3-3st$, so the given equation becomes $$(t^3-s^3)-3t(t-s)=5,$$ i.e. $$(t-s)(t^2+ts+s^2-3t)=5.$$
We obtain the four systems of equations: $$\begin{array}{rcl} t-s&=&\pm 1 \\ t^2+ts+s^2-3t&=& \pm 5, \end{array} \qquad \begin{array}{rcl} t-s&=&\pm 5 \\ t^2+ts+s^2-3t&=& \pm 1 \end{array}$$
If $t-s=\pm 1$, then $t^2-2ts+s^2=1$ and subtracting this equation to the second equation, we get $3ts-3t=4$ or $3ts-3t=-6$. The first equation is impossible, the second gives $t(s-1)=-2$. So, $(s,t) \in \{(-1,1),(0,2),(2,-2),(3,-1)\}$. It's easy to see that none of these pairs satisfies $t-s=\pm 1$, so there are no solutions in this case. If $t-s=\pm 5$, then $t^2-2ts+s^2=25$ and subtracting this equation to the second equation, we get $3ts-3t=-24$ or $3ts-3t=-26$. The second equation is impossible, the first gives $t(s-1)=-8$. So, $(s,t) \in \{(-7,1),(-3,2),(-1,4),(0,8),(2,-8),(3,-4),(5,-2),(9,-1)\}$. As $t-s=\pm 5$, we obtain $(s,t) \in \{(-3,2),(-1,4)\}$. Since $s$ and $t$ also satisfy the condition $s^2-4t=n^2$ for some $n \in \mathbb{Z}$, we obtain $(s,t)=(-3,2)$. So, $x+y=-3$ and $xy=2$, which gives $(x,y) \in \{(-1,-2),(-2,-1)\}$.

Mathematical Reflections 2017, Issue 1 - Problem U402

Problem:
Let $n$ be a positive integer and let $P(x)$ be a polynomial of degree at most $n$ such that $|P(x)| \leq x+1$ for all $x \in [0,n]$. Prove that
$$|P(n+1)|+|P(-1)| \leq (n+2)(2^{n+1}-1)$$

Proposed by Alessandro Ventullo, Milan, Italy

Solution:
In order to prove the inequality, we deduce upper bounds for $|P(-1)|$ and $|P(n+1)|$.
Let $a_0,a_1,\ldots,a_n$ be $n+1$ distinct real numbers. Let $$L_i(x)=\prod_{\begin{smallmatrix} j=0\\ j\neq i\end{smallmatrix}}^{n} \dfrac{x-a_j}{a_i-a_j}$$ be the $n$-th degree Lagrange base polynomials for $i=0,1,\ldots,n$. We first prove that $\{L_0(x),\ldots,L_n(x)\}$ is a basis for $\mathbb{R}_n[x]$. Since $\dim \mathbb{R}_n[x]=n+1$, we only have to prove that $\{L_0(x),\ldots,L_n(x)\}$ are linearly independent. Let $(\lambda_0,\ldots,\lambda_{n+1}) \in \mathbb{R}^{n+1}$ such that $$\lambda_0L_0(x)+\ldots+\lambda_n L_n(x)=0$$ For each $i \in \{0,1,\ldots,n\}$, if $x=a_i$ we have $$0=\sum_{j=0}^n \lambda_j L_j(a_i)=\sum_{j=0}^n \lambda_j \delta_{ji}=\lambda_i,$$ so $\lambda_i=0$ for any $i \in \{0,1,\ldots,n\}$ and this shows that $\{L_0(x),\ldots,L_n(x)\}$ is a basis for $\mathbb{R}_n[x]$. So, if $P \in \mathbb{R}_n[x]$, there exists $(\lambda_0,\ldots,\lambda_n) \in \mathbb{R}^{n+1}$ such that $P(x)=\sum_{j=0}^n \lambda_jL_j(x)$. If $x=a_i$, then $$P(a_i)=\sum_{j=0}^n \lambda_j L_j(a_i)=\sum_{j=0}^n \lambda_j \delta_{ji}=\lambda_i,$$ so we can write $$P(x)=\sum_{j=0}^n P(a_j)L_j(x).$$ If $(a_0,a_1,\ldots,a_n)=(0,1,\ldots,n)$, we have $$P(x)=\sum_{j=0}^n P(j)L(x)$$
Now, we have $$\renewcommand{\arraystretch}{2} \begin{array}{lcl} \displaystyle |L_i(-1)|=\left| \prod_{\begin{smallmatrix} j=0\\ j\neq i\end{smallmatrix}}^{n} \dfrac{-1-j}{i-j} \right|&=& \displaystyle \prod_{j=0}^{i-1} \dfrac{j+1}{i-j} \prod_{j=i+1}^n \dfrac{j+1}{j-i}\\&=& \displaystyle \dfrac{i!}{i!}\cdot \dfrac{(n+1)!}{(i+1)!(n-i)!}\\&=& \displaystyle {n+1 \choose i+1} \end{array}$$
and
$$\renewcommand{\arraystretch}{2} \begin{array}{lcl} \displaystyle |L_i(n+1)|=\left| \prod_{\begin{smallmatrix} j=0\\ j\neq i\end{smallmatrix}}^{n} \dfrac{n+1-j}{i-j} \right|&=& \displaystyle \prod_{j=0}^{i-1} \dfrac{n+1-j}{i-j} \prod_{j=i+1}^n \dfrac{n+1-j}{j-i}\\&=& \displaystyle \dfrac{(n+1)!}{i!(n+1-i)!}\cdot \dfrac{(n-i)!}{(n-i)!}\\&=& \displaystyle {n+1 \choose i}. \end{array}$$
Hence, $$\renewcommand{\arraystretch}{2} \begin{array}{lcl} \displaystyle |P(-1)|=\left| \sum_{i=0}^n P(i)L_i(-1) \right| & \leq & \displaystyle \sum_{i=0}^n |P(i)L_i(-1)| \\ & \leq & \displaystyle \sum_{i=0}^n (i+1) {n+1 \choose i+1}\\&=& \displaystyle (n+1) \sum_{i=0}^n {n \choose i}\\&=&(n+1)2^n \end{array}$$ and
$$\renewcommand{\arraystretch}{2} \begin{array}{lcl} \displaystyle |P(n+1)|=\left| \sum_{i=0}^n P(i)L_i(n+1) \right| & \leq & \displaystyle \sum_{i=0}^n |P(i)L_i(n+1)| \\ & \leq & \displaystyle \sum_{i=0}^n (i+1) {n+1 \choose i} \\ &=& \displaystyle \sum_{i=0}^n i{n+1 \choose i}+\sum_{i=0}^n {n+1 \choose i} \\ &=& \displaystyle (n+1) \sum_{i=1}^n {n \choose i-1}+ \sum_{i=0}^n {n+1 \choose i} \\&=&(n+1)(2^n-1)+(2^{n+1}-1). \end{array}$$
Adding the last two inequalities, we get the desired inequality.

Mathematical Reflections 2017, Issue 1 - Problem U401

Problem:
Let $P$ be a polynomial of degree $n$ such that $P(k)=\dfrac{1}{k^2}$ for all $k=1,2,\ldots,n+1$. Determine $P(n+2)$.

Proposed by Dorin Andrica, Babe\c{s}-Bolyai University, Cluj-Napoca, Romania

Solution:
There exists a unique interpolating polynomial $P$ of degree $n$ such that $P(k)=\dfrac{1}{k^2}$ for all $k=1,2,\ldots,n+1$ and this is
$$P(x)=\sum_{k=1}^{n+1} \left(\prod_{\stackrel{1\leq j\leq n+1}{j\neq k}}\frac{x-j}{k-j}\right)\dfrac{1}{k^2}.$$
Observe that $$\renewcommand{\arraystretch}{2} \begin{array}{lll} \displaystyle \prod_{\stackrel{1\leq j\leq n+1}{j\neq k}}\frac{n+2-j}{k-j}&=&\displaystyle\prod_{j=1}^{k-1} \left(\dfrac{n+2-j}{k-j}\right)\prod_{j=k+1}^{n+1} \left(\dfrac{n+2-j}{k-j}\right)\\&=& \displaystyle \dfrac{(n+1)!}{(n-k+2)!(k-1)!}\cdot\dfrac{(n-k+1)!}{(-1)^{n-k+1}(n-k+1)!}\\&=& \displaystyle (-1)^{n-k+1}{n+1 \choose k-1}. \end{array}$$
So, $$P(n+2)=\sum_{k=1}^{n+1} (-1)^{n-k+1}{n+1 \choose k-1}\dfrac{1}{k^2}.$$

Mathematical Reflections 2017, Issue 1 - Problem U397

Problem:
Let $T_n$ be the $n$-th triangular number. Evaluate $$\sum_{n \geq 1} \dfrac{1}{(8T_n-3)(8T_{n+1}-3)}$$

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

Solution:
Let $t_n=\dfrac{1}{(8T_n-3)(8T_{n+1}-3)}$.
Observe that $$\renewcommand{\arraystretch}{2} \begin{array}{lll} \dfrac{1}{t_n}=(8T_n-3)(8T_{n+1}-3)&=&\left(8\dfrac{n(n+1)}{2}-3\right)\left(8\dfrac{(n+1)(n+2)}{2}-3\right)\\&=&(4n^2+4n-3)(4n^2+12n+5)\\&=&(2n-1)(2n+3)(2n+1)(2n+5). \end{array}$$
We get $$\renewcommand{\arraystretch}{2} \begin{array}{lll} t_n&=&\dfrac{1}{(2n-1)(2n+3)(2n+1)(2n+5)}\\&=&\dfrac{1}{8}\dfrac{1}{(2n-1)(2n+5)}-\dfrac{1}{8}\dfrac{1}{(2n+1)(2n+3)}\\&=&\dfrac{1}{48}\left(\dfrac{1}{2n-1}-\dfrac{1}{2n+5}\right)-\dfrac{1}{16}\left(\dfrac{1}{2n+1}-\dfrac{1}{2n+3}\right)\\&=&\dfrac{1}{48}\left(\dfrac{1}{2n-1}-\dfrac{1}{2n+1}\right)+\dfrac{1}{48}\left(\dfrac{1}{2n+3}-\dfrac{1}{2n+5}\right)-\dfrac{1}{24}\left(\dfrac{1}{2n+1}-\dfrac{1}{2n+3}\right). \end{array}$$
So, $$\renewcommand{\arraystretch}{2} \begin{array}{lll} \displaystyle \sum_{n \geq 1} t_n&=& \displaystyle \dfrac{1}{48}\sum_{n=1}^\infty \left(\dfrac{1}{2n-1}-\dfrac{1}{2n+1}\right)+\dfrac{1}{48}\sum_{n=1}^\infty \left(\dfrac{1}{2n+3}-\dfrac{1}{2n+5}\right)-\dfrac{1}{24}\sum_{n=1}^\infty \left(\dfrac{1}{2n+1}-\dfrac{1}{2n+3}\right) \\ &=&\dfrac{1}{48}+\dfrac{1}{48}\cdot\dfrac{1}{5}-\dfrac{1}{24}\cdot\dfrac{1}{3} \\ &=& \dfrac{1}{90}. \end{array}$$

Mathematical Reflections 2017, Issue 1 - Problem S402

Problem:
Prove that $$\sum_{k=1}^{31} \dfrac{k}{(k-1)^{4/5}+k^{4/5}+(k+1)^{4/5}}<\dfrac{3}{2}+\sum_{k=1}^{31} (k-1)^{1/5}.$$

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

Solution:
Observe that $$\dfrac{k}{(k-1)^{4/5}+k^{4/5}+(k+1)^{4/5}}<\dfrac{k}{3(k-1)^{4/5}},$$ so
$$\begin{array}{lll} \displaystyle \sum_{k=1}^{31} \left(\dfrac{k}{(k-1)^{4/5}+k^{4/5}+(k+1)^{4/5}}-(k-1)^{1/5}\right)&<& \displaystyle \dfrac{1}{1+2^{4/5}}-\dfrac{1}{3}\sum_{k=2}^{31} \dfrac{2k-3}{(k-1)^{4/5}} \\ &<& \displaystyle \dfrac{1}{1+2^{4/5}}-\dfrac{1}{3}\sum_{k=2}^{31} \dfrac{2k-3}{k-1}\\&<& \displaystyle \dfrac{1}{1+2^{4/5}}-\dfrac{1}{3}\left(1+\dfrac{3}{2}\right)<0. \end{array}$$
So, $$\sum_{k=1}^{31} \left(\dfrac{k}{(k-1)^{4/5}+k^{4/5}+(k+1)^{4/5}}-(k-1)^{1/5}\right)<0<\dfrac{3}{2}.$$

Mathematical Reflections 2017, Issue 1 - Problem S400

Problem:
Find all $n$ for which $(n-4)!+\dfrac{1}{36n}(n+3)!$ is a perfect square.

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

Solution:
Clearly, $n \geq 4$. We have $$\begin{array}{lll} (n-4)!+\dfrac{1}{36n}(n+3)!&=&(n-4)!\left(1+\dfrac{1}{36n}(n-3)(n-2)(n-1)n(n+1)(n+2)(n+3)\right)\\&=&(n-4)!\left(1+\dfrac{1}{36}(n^2-9)(n^2-4)(n^2-1)\right)\\&=&(n-4)!\left(\dfrac{n^6-14n^4+49n^2}{36}\right)\\&=&(n-4)!\left(\dfrac{n(n^2-7)}{6}\right)^2. \end{array}$$
Observe that $n(n^2-7)=n^3-7n \equiv n^3-n \equiv 0 \pmod{6}$, so $\dfrac{n(n^2-7)}{6}$ is an integer. It follows that $(n-4)!\left(\dfrac{n(n^2-7)}{6}\right)^2$ is a perfect square if and only if $(n-4)!$ is a perfect square. If $n=4$ or $n=5$, then $(n-4)!=1$, which is a perfect square. Let $n>5$ and let $p$ be the greatest prime that divides $(n-4)!$. By Bertrand's Postulate, there exists a prime $q$ such that $p<q<2p$. If $2p \leq n-4$, then $q<n-4$, which gives $q \ | \ (n-4)!$, contradiction. So, $n-4<2p$, which means that $p \ | \ (n-4)!$ and $p^2 \nmid (n-4)!$. So, $(n-4)!$ is not a perfect square if $n>5$. Therefore, $n \in \{4,5\}$.

Mathematical Reflections 2017, Issue 1 - Problem S397

Problem:
Let $a,b,c$ be positive real numbers. Prove that $$\dfrac{a^2}{a+b}+\dfrac{b^2}{b+c}+\dfrac{c^2}{c+a}+\dfrac{3(ab+bc+ca)}{2(a+b+c)} \geq a+b+c.$$

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

Solution:
The given inequality is equivalent to $$(a+b+c)\left(\dfrac{a^2}{a+b}+\dfrac{b^2}{b+c}+\dfrac{c^2}{c+a}\right)+\dfrac{3}{2}(ab+bc+ca) \geq (a+b+c)^2,$$ i.e.

$$\dfrac{a^2c}{a+b}+\dfrac{b^2a}{b+c}+\dfrac{c^2b}{c+a} \geq \dfrac{1}{2}(ab+bc+ca) \qquad (1)$$

By the AM-GM Inequality, we have $$\dfrac{2a^2c}{a+b}+\dfrac{c(a+b)}{2} \geq 2ca,$$ $$\dfrac{2b^2a}{b+c}+\dfrac{a(b+c)}{2} \geq 2ab,$$ $$\dfrac{2c^2b}{c+a}+\dfrac{b(c+a)}{2} \geq 2bc.$$ Adding these three inequalities, we get inequality (1). The equality holds if and only if $a=b=c$.

Mathematical Reflections 2017, Issue 1 - Problem J401

Problem:
Find all integers $n$ for which $n^2+2^n$ is a perfect square.

Proposed by Adrian Andreescu, Dallas, Texas

Solution:
Clearly, $n \geq 0$. If $n=0$, we get $n^2+2^n=1$, which is a perfect square. Let $n>0$. If $n$ is even, then $n=2k$ for some $k \in \mathbb{N}^*$. If $k \geq 7$, then $$(2^k)^2=2^{2k}<4k^2+2^{2k}<2^{2k}+2^{k+1}+1=(2^k+1)^2,$$ so $n^2+2^n$ is not a perfect square if $n$ is even and $n \geq 14$. So, $n \in \{2,4,6,8,10,12\}$. An easy check gives the solution $n=6$. If $n$ is odd, then $n=2k+1$ for some $k \in \mathbb{N}$. If $k=0$, we get no solutions, so assume $k \geq 1$. Let $m \in \mathbb{N}^*$ such that $(2k+1)^2+2^{2k+1}=m^2$. Then, $$(m-2k-1)(m+2k+1)=2^{2k+1}.$$ Since $m-2k-1<m+2k+1$ and the two factors have the same parity, then $$\begin{array}{lll} m-2k-1&=&2^a \\ m+2k+1&=&2^b, \end{array}$$ where $a,b \in \mathbb{N}$, $1 \leq a \leq b \leq 2k$ and $a+b=2k+1$. If $a \geq 2$, then subtracting we get $2(2k+1)=2^b-2^a=2^a(2^{b-a}-1)$, i.e. $2k+1=2^{a-1}(2^{b-a}-1)$, contradiction. So, $a=1$ and $b=2k$, which gives $2k+1=2^{2k-1}-1$, i.e. $k=2^{2k-2}-1$. If $k \geq 2$, then $k<2^{2k-2}-1$, so it must be $k=1$. But if $k=1$, we get no solutions. So, there are no solutions when $n$ is odd. We conclude that $n \in \{0,6\}$.

Mathematical Reflections 2017, Issue 1 - Problem J400

Problem:
Prove that for all real numbers $a,b,c$ the following inequality holds:
$$\dfrac{|a|}{1+|b|+|c|}+\dfrac{|b|}{1+|c|+|a|}+\dfrac{|c|}{1+|a|+|b|} \geq \dfrac{|a+b+c|}{1+|a+b+c|}.$$
When does the equality occur?

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

Solution:
 Put $s=a+b+c$. By Triangle Inequality, we have $|s| \leq |a|+|b|+|c|$, so $|s|(1+|a|+|b|+|c|) \leq (1+|s|)(|a|+|b|+|c|)$, i.e.
$$\dfrac{|s|}{1+|s|} \leq \dfrac{|a|+|b|+|c|}{1+|a|+|b|+|c|}.$$ Using the fact that $|x| \geq 0$ for all real numbers $x$, we have
$$\begin{array}{lll} \dfrac{|a|+|b|+|c|}{1+|a|+|b|+|c|}&=&\dfrac{|a|}{1+|a|+|b|+|c|}+\dfrac{|b|}{1+|a|+|b|+|c|}+\dfrac{|c|}{1+|a|+|b|+|c|} \\ & \leq & \dfrac{|a|}{1+|b|+|c|}+\dfrac{|b|}{1+|c|+|a|}+\dfrac{|c|}{1+|a|+|b|}. \end{array}$$
So, $$\dfrac{|s|}{1+|s|} \leq \dfrac{|a|}{1+|b|+|c|}+\dfrac{|b|}{1+|c|+|a|}+\dfrac{|c|}{1+|a|+|b|},$$ which is the desired inequality. Equality occurs if and only if $|a|=|b|=|c|=0$, i.e. if and only if $a=b=c=0$.

Mathematical Reflections 2017, Issue 1 - Problem J399

Problem:
Two nine-digit numbers $m$ and $n$ are called cool if

   (a) they have the same digits but in different order,
   (b) no digit appears more than once,
   (c) $m$ divides $n$ or $n$ divides $m$.

Prove that if $m$ and $n$ are cool, then they contain digit $8$.

Proposed by Titu Andreescu, Dallas, Texas

Solution:
Assume by contradiction that there exist two \emph{cool} numbers $m$ and $n$ not containing digit $8$. Then in $m$ and $n$ appear the digits $0,1,2,3,4,5,6,7,9$ exactly once. Since the sum of their digits is $37$, then $m,n \equiv 1 \pmod{9}$. Assume without loss of generality that $m$ divides $n$. Then, $n=mk$, where $k$ is a natural number. Hence, $n-m=m(k-1)$. Reducing modulo $9$ this equation, we get $k-1 \equiv 0 \pmod{9}$, i.e. $k-1$ is divisible by $9$. Since $m$ and $n$ have the same digits in different order, then $m \neq n$, which gives $k \neq 1$. So, $k \geq 10$. But then $n \geq 10m$, i.e. $n$ has more digits than $m$, contradiction.