Mathematical Reflections 2014, Issue 5 - Problem U313

Problem:
Let $X$ and Y be nonnegative definite Hermitian matrices such that $X-Y$ is also non-negative definite. Prove that $\textrm{tr}(X^2) \geq \textrm{tr}(Y^2)$.

Proposed by Radouan Boukharfane

Solution:
We use Klein's Inequality:
For all nonnegative-definite Hermitian $n \times n$ matrices $A$ and $B$, and all differentiable convex functions $f:\mathbb{R}^+ \longrightarrow \mathbb{R}$, the following inequality holds:
$${\rm tr}[f(A)- f(B)- (A - B)f'(B)] \geq 0.$$

Take $A=X, B=Y$ and $f(x)=x^2$. By Klein's Inequality, we get $$\textrm{tr}\left(X^2-Y^2-(X-Y)\cdot2Y\right) \geq 0.$$ Moreover, since $X$ and $X-Y$ are nonnegative, then $$\textrm{tr}\left((X-Y)Y\right) \geq 0.$$ This can be proved by Cholesky decomposition: $X-Y=L_1L_1^*$ and $Y=L_2L_2^*$ for some lower triangular matrices $L_1,L_2$ with real and nonnegative diagonal entries. So, $$\textrm{tr}\left((X-Y)Y\right)=\textrm{tr}(L_1L_1^*L_2L_2^*)=\textrm{tr}(L_2^*L_1L_1^*L_2)=\textrm{tr}((L_1^*L_2)^*(L_1^*L_2))\geq 0.$$ Hence,
$$\begin{array}{lll}\textrm{tr}\left(X^2\right)-\textrm{tr}\left(Y^2\right)&=&\textrm{tr}\left(X^2-Y^2\right)\\&=&\textrm{tr}\left(X^2-Y^2-(X-Y)\cdot2Y\right)+2\textrm{tr}\left((X-Y)Y\right) \geq 0, \end{array}$$ which is the desired conclusion.

Mathematical Reflections 2014, Issue 5 - Problem J318

Problem:
Determine the functions $f : \mathbb{R} \longrightarrow \mathbb{R}$ satisfying $f(x-y)-xf(y) \leq 1-x$ for all real numbers $x$ and $y$.

Proposed by Marcel Chirita

Solution:
Observe that if $x=0$, we get $f(-y) \leq 1$ for all $y \in \mathbb{R}$, i.e. $f(x) \leq 1$ for all $x \in \mathbb{R}$. If $y=0$, then

$f(x)-xf(0) \leq 1-x,$                               (1)

and if $y=x$, then

$f(0)-xf(x) \leq 1-x.$                               (2)

Summing up (1) and (2), we get $(1-x)(f(x)+f(0)) \leq 1-x$ and if $x>1$, we obtain $f(x)+f(0) \geq 2$, for all $x \in (1,\infty)$, i.e. $f(x) \geq 2-f(0) \geq 1$. Therefore, $f(x)=1$ for all $x \in (1,\infty)$ and $f(0)=1$. Now, setting $x=1$ in the given relation, we have $f(1-y) \leq f(y)$ and for all $1-y>1$, we have $1 \leq f(y)$. So, $f(x)=1$ for all $x \in (-\infty,0)$. Now, setting $x=1$ in (1) and (2), we get $f(0)=f(1)$. Finally, if we set $x=1/t$ and $y=x$ in the given relation, we get $$f(0)-\dfrac{1}{t}f\left(\dfrac{1}{t}\right) \leq 1-\dfrac{1}{t},$$ i.e. $$tf(0)-f\left(\dfrac{1}{t}\right) \leq t-1.$$ This relation, $f(0)=1$ and (1) give $$f(x) \leq f\left(\dfrac{1}{x}\right),$$ so $f(x)=1$ for all $x \in (0,1)$. In conclusion, $f(x)=1$ for all $x \in \mathbb{R}$. 

Mathematical Reflections 2014, Issue 5 - Problem J316

Problem:
Solve in prime numbers the equation $$x^3+y^3+z^3+u^3+v^3+w^3=53353.$$

Proposed by Titu Andreescu.

Solution:
Assume $x \leq y \leq z \leq u \leq v \leq w$. Since $53353$ is odd, then $x=2$. We have
$$y^3+z^3+u^3+v^3+w^3=53345.$$ Moreover, $5w^3 \geq 53345 \geq w^3$, so $w \in \{23,29,31,37\}$. A case by case analysis gives $(x,y,z,u,v,w)=(2,3,5,7,13,37)$.

Mathematical Reflections 2014, Issue 4 - Problem U312

Problem:
Let $p$ be a prime and let $R$ be a commutative ring with characteristic $p$. Prove that the
sets $S_k = \{x \in R \ | \ x^p=k\}$, where $k \in \{1,\ldots,p\}$, have the same number of elements.

Proposed by Corneliu Manescu-Avram.

Solution:
If for any $x \in R$ and $k \in \{1,\ldots,p\}$ it holds $x^p \neq k$, then there is nothing to prove. Assume that there is some $x \in R$ such that $x^p=k$ for some $k \in \{1,\ldots,p\}$. Hence, $k \in R$. Consider the set $S=\{x+k \ | \ x \in R\}$. Observe that the mapping $\varphi:R \longrightarrow S$ defined by $\varphi(x)=x+k$ is bijective. Indeed, if $\varphi(x)=\varphi(y)$, then $x+k=y+k$, i.e. $x=y$ and this proves that $\varphi$ is injective. If $y \in S$, then $y=x+k$ for some $x \in R$, so it's enough to take $x=y-k \in R$ in order to have $y=\varphi(x)$, and this proves that $\varphi$ is surjective. Let $n \in \{1,\ldots,p\}$ and consider the set $S_n = \{x \in R \ | \ x^p=n\}$. Since $(x+k)^p=x^p+k^p=x^p+k$, then $$\varphi(S_n)=\begin{cases} S_{n-k} & \textrm{if } n>k \\ S_{p-k+n} & \textrm{if } k \leq n. \end{cases}$$ It follows that $|S_n|=|S_{n-k}|$ or $|S_n|=|S_{p-k+n}|$. By arbitrarily of $n \in \{1,\ldots,p\}$, we conclude that $|S_1|=|S_2|=\ldots=|S_p|$.

Mathematical Reflections 2014, Issue 4 - Problem U307

Problem:
Prove that any polynomial $f \in \mathbb{R}[X]$ can be written as a difference of increasing polynomials.

Proposed by Jishnu Bose.

Solution:
Let $f(X)=a_nX^n+a_{n-1}X^{n-1}+\ldots+a_1X+a_0$. We construct the following algorithm. Set $g_0(X)=a_0, h_0(X)=0$ and for $k=1,\ldots,n$, if $k$ is odd, then $$g_k(X)=\begin{cases} a_kX^k & \textrm{if } a_k \geq 0 \\ 0 & \textrm{if } a_k<0, \end{cases}$$ $$h_k(X)=\begin{cases} 0 & \textrm{if } a_k \geq 0 \\ -a_kX^k & \textrm{if } a_k<0, \end{cases}$$ and if $k$ is even, then $$ g_k(X)=\begin{cases}a_k(X^{k+1}+X^k+X^{k-1}) & \textrm{if } a_k \geq 0 \\ -a_k(X^{k+1}+X^{k-1}) & \textrm{if } a_k < 0,  \end{cases}$$ $$h_k(X)=\begin{cases}a_k(X^{k+1}+X^{k-1}) & \textrm{if } a_k \geq 0 \\ -a_k(X^{k+1}+X^k+X^{k-1}) & \textrm{if } a_k < 0. \end{cases}$$
Observe that for all $k=0,\ldots,n$, we have $g_k(X)-h_k(X)=a_kX^k$ and $g'_k(X) \geq 0$, $h'_k(X) \geq 0$ for all $x \in \mathbb{R}$. Setting $$g(X)=\sum_{k=0}^n g_k(X), \qquad h(X)=\sum_{k=0}^n h_k(X),$$ we have that $g(X)$ and $h(X)$ are increasing polynomials and $f(X)=g(X)-h(X)$.

Mathematical Reflections 2014, Issue 4 - Problem S307

Problem:
Let $ABC$ be a triangle such that $\angle ABC - \angle ACB = 60^{\circ}$. Suppose that the length of the
altitude from $A$ is $\dfrac{1}{4}BC$. Find $\angle ABC$.

 Proposed by Omer Cerrahoglu and Mircea Lascu.

Solution:
Let $\alpha=\angle ABC$ and let $H$ be the foot of the altitude from $A$. Observe that $\alpha>60^{\circ}$, so $\tan \alpha>\sqrt{3}$. We have $$\dfrac{AH}{BH}=\tan \alpha, \qquad \dfrac{AH}{CH}=\tan (\alpha-60^{\circ}).$$ Since $AH=\dfrac{1}{4}BC$, then $$BC=BH+CH=\dfrac{1}{4 \tan \alpha}BC+\dfrac{1}{4 \tan (\alpha-60^{\circ})}BC,$$ which gives $$\dfrac{1}{\tan \alpha}+\dfrac{1}{\tan (\alpha-60^{\circ})}=4.$$ Since $\dfrac{1}{\tan (\alpha)-60^{\circ}}=\dfrac{1+\tan 60^{\circ}\tan \alpha}{\tan \alpha-\tan 60^{\circ}}$, setting $x=\tan \alpha$, we get $$\dfrac{1}{x}+\dfrac{1+\sqrt{3}x}{x-\sqrt{3}}=4 \iff (4-\sqrt{3})x^2-2(2\sqrt{3}+1)x+\sqrt{3}=0.$$ As $x>\sqrt{3}$, then $x=2+\sqrt{3}$, i.e. $\alpha=75^{\circ}$. 

Mathematical Reflections 2014, Issue 4 - Problem J311

Problem:
Let $a, b, c$ be real numbers greater than or equal to $1$. Prove that
$$\dfrac{a(b^2+3)}{3c^2+1}+\dfrac{b(c^2+3)}{3a^2+1}+\dfrac{c(a^2+3)}{3b^2+1} \geq 3.$$

Proposed by Titu Andreescu.

Solution:
First, observe that $x \geq 1$ is equivalent to $$(x-1)^3 \geq 0 \iff x^3+3x \geq 3x^2+1 \iff \dfrac{x(x^2+3)}{3x^2+1} \geq 1.$$
By the AM-GM Inequality, we have
$$\dfrac{a(b^2+3)}{3c^2+1}+\dfrac{b(c^2+3)}{3a^2+1}+\dfrac{c(a^2+3)}{3b^2+1} \geq 3\sqrt[3]{\dfrac{a(a^2+3)}{3a^2+1}\cdot\dfrac{b(b^2+3)}{3b^2+1}\cdot\dfrac{c(c^2+3)}{3c^2+1}} \geq 3,$$ which is the desired conclusion.

Mathematical Reflections 2014, Issue 4 - Problem J309

Problem:

Let $n$ be an integer greater than $3$ and let $S$ be a set of $n$ points in the plane that are not the vertices of a convex polygon and such that no three are collinear. Prove that there is a triangle with the vertices among these points having exactly one other point from $S$ in its interior.

Proposed by Ivan Borsenco.

Solution:

We use the following theorem.

Carathéodory's Theorem.
If $\mathbf{x} \in \mathbb{R}^d$ lies in the convex hull of a set $S$, there is a subset $S'$ of $S$ consisting of $d+1$ or fewer points such that $\mathbf{x}$ lies in the convex hull of $S'$.

Let $\mathbf{x} \in S$ such that $\mathbf{x}$ lies in the interior of the convex hull of $S$. Hence, by Caratheodory's Theorem ($d=2$), there is a subset $S'$ of $S$ having at most $3$ points such that $\mathbf{x}$ lies in the convex hull of $S'$. Since the points are not collinear, then $|S'| \neq 2$ and since $\mathbf{x}$ lies in the interior of the convex hull of $S$, then $|S'| \neq 1$. So, $|S'|=3$ and there exists a triangle $T$ whose vertices are in $S$ which contains $\mathbf{x}$. If $\mathbf{x}$ is the unique point of $S$ in $T$, we are done. If there is another point $\mathbf{y} \neq \mathbf{x}$ of $S$ in $T$, joining $\mathbf{x}$ with the three points in $S'$ we have that $\mathbf{y}$ lies in the interior of one among these triangles. Proceeding in this way and using the fact that $S$ has finitely many points, then there exists a triangle whose vertices are in $S$ which has exactly one point of $S$ in its interior.

Mathematical Reflections 2014, Issue 4 - Problem J308

Problem:
Are there triples $(p, q, r)$ of primes for which $(p^2-7)(q^2-7)(r^2-7)$ is a perfect square?

Proposed by Titu Andreescu.

Solution:
The answer is no. Let $N=(p^2-7)(q^2-7)(r^2-7)$. If exactly one or exactly three among $p,q,r$ are equal to $2$, then $N<0$ and if exactly two numbers are equal to $2$, then $N \equiv 2 \pmod{4}$. In every case $N$ is not a perfect square. Assume that $p,q,r$ are all odd. Then there exist $a,b,c \in \mathbb{N}$ such that $p^2=4a+1,q^2=4b+1,r^2=4c+1$ and
$$N=2^3(2a-3)(2b-3)(2c-3).$$ Since in the factorization of $N$ the number $2$ has an odd exponent, we conclude that $N$ is not a perfect square. Therefore, $N$ is never a perfect square.

Mathematical Reflections 2014, Issue 4 - Problem J307

Problem:
Prove that for each positive integer $n$ there is a perfect square whose sum of digits is equal to $4^n$.

Proposed by Mihaly Bencze.

Solution:
Consider the sequence $$\begin{array}{rcl}a_1&=&4 \\ \qquad a_n&=&\underbrace{11\ldots1}_{n-1 \textrm{ times}}0\underbrace{22\ldots2}_{n-1 \textrm{ times}}4, \end{array} \qquad n \geq 2.$$
Every term of the sequence is a perfect square. Indeed, $a_0$ is clearly a perfect square and $$\begin{array}{lll} a_n&=&\dfrac{10^{n-1}-1}{9}\cdot10^{n+1}+2\cdot\dfrac{10^{n-1}-1}{9}\cdot10+4\\ &=&\dfrac{10^{2n}-8\cdot10^n+16}{9}\\&=&\left(\dfrac{10^n-4}{3}\right)^2, \end{array}$$ where $n \geq 2$.
Furthermore, if $s$ denotes the sum of the digits of $a_n$, we have $s(a_1)=4$ and $s(a_n)=(n-1)+2(n-1)+4=3n+1$ for all $n \geq 2$. Since $4^n \equiv 1 \pmod{3}$ for all $n \in \mathbb{N}$, we have that for all $n \in \mathbb{N}$ there exists $k \in \mathbb{N}$ such that $4^n=3k+1=s(a_k)$ and the conclusion follows.