Mathematical Reflections 2011, Issue 6 - Problem J214

Problem:
Let $a,b,c,d,e \in [1,2]$. Prove that
$$ab+bc+cd+de+ea \geq a^2+b^2+c^2+d^2-e^2.$$

Proposed by Ion Dobrota and Adrian Zahariuc.

Solution:

It is equivalent to prove that given $a,b,c,d,e \in [1,2]$, the following inequality holds
$$(a-b)^2+(b-c)^2+(c-d)^2+(d-e)^2+(e-a)^2 \leq 4e^2.$$
Clearly,
$$(a-b)^2 \leq 1, \qquad (b-c)^2 \leq 1, \qquad (c-d)^2 \leq 1, \qquad (d-e)^2 \leq 1, \qquad (e-a)^2 \leq 1,$$
so
$$(a-b)^2+(b-c)^2+(c-d)^2+(d-e)^2+(e-a)^2 \leq |a-b|+|b-c|+|c-d|+|d-e|+|e-a|.$$
The right hand side is maximum if and only if there is only one term which cancels out when removing the absolute values. Without loss of generality, we can suppose that $b$ cancels out, so
$$|a-b|+|b-c|+|c-d|+|d-e|+|e-a| \leq 2(a+d)-2(c+e) \leq 4 \leq 4e^2,$$
and the desired conclusion follows. From the made observations, we have four cases for the equality:

(i) If $a$ cancels out, then $(b-a)+(b-c)+(d-c)+(d-1)+(a-1)=2(b+d)-2c-2=4 \iff 4 \leq b+d \iff b=d=2, c=1$, and $a=1,2$.

(ii) If $b$ cancels out, then $(a-b)+(b-c)+(d-c)+(d-1)+(a-1)=2(a+d)-2c-2=4 \iff 4 \leq a+d \iff a=d=2, c=1$, and $b=1,2$.

(iii) If $c$ cancels out, then $(a-b)+(c-b)+(d-c)+(d-1)+(a-1)=2(a+d)-2b-2=4 \iff 4 \leq a+d \iff a=d=2, b=1$, and $c=1,2$.

(iv) If $d$ cancels out, then $(a-b)+(c-b)+(c-d)+(d-1)+(a-1)=2(a+c)-2b-2=4 \iff 4 \leq a+c \iff a=c=2, b=1$, and $d=1,2$.

In conclusion, the equality can be obtained if $e=1$ and occurs if and only if $$(a,b,c,d,e) \in \{(1,2,1,2,1),(2,2,1,2,1),(2,1,1,2,1),(2,1,2,2,1),(2,1,2,1,1)\}.$$  

Mathematical Reflections 2011, Issue 6 - Problem J213

Problem:
For any positive integer $n$, let $S(n)$ denote the sum of digits in its decimal representation.
Prove that the set of all positive integers $n$ such that $n$ is not divisible by $10$ and $S(n) >
S(n^2 + 2012)$ is infinite.

Proposed by Preudtanan Sriwongleang.

Solution:

With the notation introduced, let $A = \{ n \in \mathbb{N} : n \neq 10k \textrm{ and } S(n)  > S(n^2+2012), k \in \mathbb{N}\}$. We prove that $A \supset \{5\cdot10^{m}-1, m \in \mathbb{N}\setminus\{0\}\} = \{49,499,\ldots,4\underbrace{9\ldots9}_{m},\ldots\}$, so that $A$ must be infinite. Clearly, $49,499 \in A$, since
$$49 \neq 10k, k \in \mathbb{N}, \qquad S(49)=13 > 12=S(4413)$$ and
$$499 \neq 10k, k \in \mathbb{N}, \qquad S(499)=22 > 12=S(251013).$$
Let $m > 2$. Then $5\cdot10^m-1 \neq 10k, k \in \mathbb{N}$ and $$(5\cdot 10^m - 1)^2+2012=25\cdot10^{2m}-10^{m+1}+2013=24\underbrace{9\ldots9}_{m-1}\underbrace{0\ldots0}_{m+1} + 2013,$$
from which $$S((5\cdot10^m-1)^2+2012)=2+4+9(m-1)+2+1+3=9m+3.$$
Therefore, $S(5\cdot10^m-1)=9m+4 > 9m+3=S((5\cdot10^m-1)^2+2012)$, i.e. $$5\cdot10^m-1 \in A \qquad \forall m \in \mathbb{N}\setminus\{0\},$$ which gives the desired conclusion. 

Mathematical Reflections 2011, Issue 6 - Problem J212

Problem:
Solve in real numbers the system of equations
$$\begin{array}{lll} (x-2y)(x-4z)=6 \\ (y-2z)(y-4x)=10 \\ (z-2x)(z-4y)=-16. \end{array}$$

Proposed by Titu Andreescu.

Solution:

Rewriting the equations, we have
$$\begin{array}{lll} x^2-2xy+8yz-4zx=6 \\ y^2-4xy-2yz+8zx=10 \\ z^2+8xy-4yz-2zx=-16. \end{array}$$
and summing up the equations we obtain $(x+y+z)^2=0$, i.e. $x+y+z=0$. Putting $z=-x-y$, and substituting into the first two equations, we have
$$\begin{array}{lll} 5x^2-6xy-8y^2=6 \\ 3y^2-10xy-8x^2=10,\end{array}$$ so $5(5x^2-6xy-8y^2)-3(3y^2-10xy-8x^2)=49(x^2-y^2)=0$, which gives $y=\pm x$. If $y=x$, the first equation yields $-9x^2=6$, so no real solutions. If $y=-x$, the first equations yields $3x^2=6$, so $x=\pm \sqrt{2}$ and $y=\mp \sqrt{2}$. Therefore, the real solutions are $(\sqrt{2},-\sqrt{2},0)$ and $(-\sqrt{2},\sqrt{2},0)$.

Mathematical Reflections 2011, Issue 5 - Problem U206

Problem:
Prove that there is precisely one group with $30$ elements and $8$ automorphisms.

Proposed by Gabriel Dospinescu.

Solution:
Let $G$ be a group such that $|G|=30$ and $|\textrm{Aut}(G)|=8$. Since $\textrm{Inn}(G)$ is a subgroup of $\textrm{Aut}(G)$ and $G/Z(G) \simeq \textrm{Inn}(G)$, then by Lagrange's Theorem $|\textrm{Inn}(G)|$ divides $|G|$ ($Z(G)$ is a normal subgroup of $G$) and $|\textrm{Aut}(G)|$, so $|\textrm{Inn}(G)|=1,2$. In any case $\textrm{Inn}(G)$ is isomorphic to a cyclic group, so $G/Z(G)$ is isomorphic to a cyclic group and so $G$ is abelian. By the Fundamental Theorem of Finitely Generated Abelian Groups, there is only one abelian group of order $30$ and this is $\mathbb{Z}_{30}$.

Mathematical Reflections 2011, Issue 5 - Problem U205

Problem:
Let $E$ be a vectorial space with norms $\left\|\cdot\right\|_1$ and $\left\|\cdot\right\|_2$. Decide if $\min(\left\|\cdot\right\|_1,\left\|\cdot\right\|_2)$ is a norm.

Proposed by Roberto Bosch Cabrera.

Solution:
The answer is no. Let $E=\mathbb{R}^2, \left\|\underline{x} \right\|_1:=\sqrt{x^2_1+x^2_2}, \left\|\underline{x} \right\|_2:=|x_1|+|x_1-x_2|$. Simple computations show that $\left\|\cdot\right\|_1$ and $\left\|\cdot\right\|_2$ are norms on $\mathbb{R}^2$. Put $\underline{x}=(0,0), \underline{y}=(1,0), \underline{z}=(2,1)$. Then
$$\min(\left\|\underline{x}-\underline{y}\right\|_1,\left\|\underline{x}-\underline{y}\right\|_2) + \min(\left\|\underline{y}-\underline{z}\right\|_1,\left\|\underline{y}-\underline{z}\right\|_2) = \min(1,2) + \min(\sqrt{2},1)=2,$$
but $$\min(\left\|\underline{x}-\underline{z}\right\|_1,\left\|\underline{x}-\underline{z}\right\|_2) = \min(\sqrt{5},3) = \sqrt{5},$$
so $$\min(\left\|\underline{x}-\underline{y}\right\|_1,\left\|\underline{x}-\underline{y}\right\|_2) + \min(\left\|\underline{y}-\underline{z}\right\|_1,\left\|\underline{y}-\underline{z}\right\|_2) < \min(\left\|\underline{x}-\underline{z}\right\|_1,\left\|\underline{x}-\underline{z}\right\|_2).$$

Mathematical Reflections 2011, Issue 5 - Problem S207

Problem:
Let $a,b,c$ be distinct nonzero real numbers such that $ab + bc + ca = 3$ and $ab+bc+ca \neq abc+\dfrac{2}{abc}$. Prove that
$$\left(\sum_{cyc}\dfrac{a(b-c)}{bc-1}\right)\cdot \left(\sum_{cyc}\dfrac{bc-1}{a(b-c)}\right)$$ is the square of an integer.

Proposed by Titu Andreescu.

Solution:
For simplicity, we put $x=ab, y=bc, z=ca$, so that $x+y+z=3$. We obtain
$$P=\left(\dfrac{x-z}{y-1}+\dfrac{z-y}{x-1}+\dfrac{y-x}{z-1}\right)\left(\dfrac{y-1}{x-z}+\dfrac{x-1}{z-y}+\dfrac{z-1}{y-x}\right).$$
We observe that $$\dfrac{x-1}{z-y}+\dfrac{z-1}{y-x}=\dfrac{(x-z)(-x-z+y+1)}{(z-y)(y-x)}=\dfrac{2(x-z)(y-1)}{(z-y)(y-x)}.$$
Likewise,
$$\dfrac{y-1}{x-z}+\dfrac{z-1}{y-x}=\dfrac{2(z-y)(x-1)}{(x-z)(y-x)}, \qquad \dfrac{y-1}{x-z}+\dfrac{x-1}{z-y}=\dfrac{2(y-x)(z-1)}{(x-z)(z-y)}.$$
Hence,
$$\begin{array}{lll}
P & = & 3+2\dfrac{(x-z)^2}{(z-y)(y-x)}+2\dfrac{(z-y)^2}{(x-z)(y-x)}+2\dfrac{(y-x)^2}{(z-y)(x-z)} \\ & = & 3+2\left(\dfrac{y-x}{z-y}+\dfrac{z-y}{y-x}+2+\dfrac{y-x}{x-z}+\dfrac{x-z}{y-x}+2+\dfrac{x-z}{z-y}+\dfrac{z-y}{x-z}+2\right) \\ & = & 3+2(6-3) = 9. \end{array}$$

Mathematical Reflections 2011, Issue 5 - Problem S206

Problem:
Find all integers $n \geq 2$ having a prime divisor $p$ such that $n-1$ is divisible by the
exponent of $p$ in $n!$.

Proposed by Tigran Hakobyan.

Solution:
It is not difficult to show that every power of a prime do the trick. Indeed, let $n=p^k$, where $p$ is a prime number and $k$ is a positive integer. Then $$e_p(n)=e_p(p^k)=\sum_{i\geq 1} \left\lfloor \dfrac{p^k}{p^i} \right\rfloor = p^{k-1}+p^{k-2}+\ldots+p+1$$ and $n-1=p^k-1=\displaystyle(p-1)e_p(n)$. We want to show that these are the only integers which satisfy the given conditions. So, suppose that $n$ is not a power of a prime, namely $n=p^k m$, where $\gcd(p,m)=1$, $m > 1$ and $k$ is a positive integer. Suppose that $e_p(n)|(n-1)$.
$$e_p(n) = \sum_{i=1}^{k} \left\lfloor \dfrac{p^k m}{p^i} \right\rfloor + \sum_{i>k} \left\lfloor \dfrac{p^k m}{p^i} \right\rfloor = me_p(p^k) + e_p(m).$$ Since $$mp^{k-1} < me_p(p^k) = m \dfrac{p^k-1}{p-1}$$ and $$0 < e_p(m) < \dfrac{m}{p-1},$$ we obtain $$mp^{k-1} < me_p(p^k)+e_p(m) < \dfrac{mp^k}{p-1},$$ and rewriting $$\dfrac{n}{p} < e_p(n) < \dfrac{n}{p-1}.$$ Since $e_p(n)$ is an integer, we have $\dfrac{n-1}{p} < e_p(n) \leq \dfrac{n-1}{p-1},$ (otherwise $\dfrac{n-1}{p-1} < e_p(n) < \dfrac{n}{p-1}$, a contradiction) which gives $$p-1 \leq \dfrac{n-1}{e_p(n)} < p,$$ i.e. $n-1=(p-1)e_p(n)$. Hence, $$\dfrac{m(p^k-1)+m-1}{p-1}=me_p(p^k)+\dfrac{m-1}{p-1}=e_p(n),$$ so $e_p(m)=\dfrac{m-1}{p-1}$.
But since $\gcd(p,m)=1$, we also have
$$e_p(n) = me_p(p^k) + e_p(m) = me_p(p^k) + e_p(m-1) = \dfrac{n-m}{p-1}+\dfrac{m-2}{p-1} = \dfrac{n-2}{p-1},$$ contradiction.

Mathematical Reflections 2011, Issue 5 - Problem J205

Problem:
Find the greatest $n$-digit number $a_1a_2\ldots a_n$ with the following properties:
i) all its digits are different from zero and distinct;
ii) for each $k = 2,\ldots,n-1$, $\dfrac{1}{a_{k-1}}, \dfrac{1}{a_k},\dfrac{1}{a_{k+1}}$ is either an arithmetic sequence or a geometric sequence.

Proposed by Titu Andreescu.

Solution:
The two properties imply that $1 \leq n \leq 9$, $1 \leq a_k \leq 9$, $a_i \neq a_j$ if $i \neq j$ and
$$\textrm{(i) } a_k(a_{k-1}+a_{k+1})=2a_{k-1}a_{k+1} \qquad \textrm{or} \qquad \textrm{(ii) } a_{k-1}a_{k+1}=a^2_k.$$
for each $k=2,\ldots,8$. We study each case separately.

(i) (a) $a_k=2,4,6,8$. We obtain the four equations
\begin{equation}\label{first}
a_{k+1}=a_{k-1}(a_{k+1}-1)
\end{equation}
\begin{equation}\label{second}
2a_{k+1}=a_{k-1}(a_{k+1}-2)
\end{equation}
\begin{equation}\label{third}
3a_{k+1}=a_{k-1}(a_{k+1}-3)
\end{equation}
\begin{equation}\label{fourth}
4a_{k+1}=a_{k-1}(a_{k+1}-4)
\end{equation}
The first has no solutions since $a_{k+1}-1$ can't divide $a_{k+1}$.
The second implies that $a_{k+1}-2$ divides $2a_{k+1}$ and since $2a_{k+1}=2(a_{k+1}-2)+4$, $a_{k+1}-2$ must divide $4$, i.e. $a_{k+1}=3,6$ and by symmetry $a_{k-1}=6,3$ respectively.
The third implies that $a_{k+1}-3$ divides $3a_{k+1}$ and since $3a_{k+1}=3(a_{k+1}-3)+9$, $a_{k+1}-3$ must divide $9$, so $a_{k+1}=4,6$ and $a_{k-1}=12,6$ respectively, so there are no solutions.
The fourth implies that $a_{k+1}-4$ divides $4a_{k+1}$ and since $4a_{k+1}=4(a_{k+1}-4)+16$, $a_{k+1}-4$ must divide $16$, so $a_{k+1}=5,6,8$ and $a_{k-1}=20,12,8$ respectively, so there are no solutions.

(b) $a_{k-1}+a_{k+1}=8,10,12$. (we can immediately discard $a_{k-1}+a_{k+1}=4,6,14,16$ because for any $a_{k-1},a_{k+1}$ the LHS would be divisible by $3$, by $4$ or by $7$ and the RHS not). We obtain
\begin{equation}\label{fifth}
a_{k-1}+a_{k+1}=8, \qquad 4a_k=a_{k-1}a_{k+1}
\end{equation}
\begin{equation}\label{sixth}
a_{k-1}+a_{k+1}=10, \qquad 5a_k=a_{k-1}a_{k+1}
\end{equation}
\begin{equation}\label{seventh}
a_{k-1}+a_{k+1}=12, \qquad 6a_k=a_{k-1}a_{k+1}
\end{equation}
The fifth implies that $a_{k-1}=6,2$ and by symmetry $a_{k+1}=2,6$ respectively, so $a_k=3$.
The sixth has no solutions since the LHS of the second equation is divisible by $5$ and the RHS not.
The seventh has no solutions since the LHS of the second equation is divisible by $6$ and the RHS not.

(ii) Since $a_{k-1} \neq a_{k+1}$, it is easy to see that the only solutions are
$$a_k=2, \qquad a_{k-1}=1,4, \qquad a_{k+1}=4,1$$
$$a_k=3, \qquad a_{k-1}=1,9, \qquad a_{k+1}=9,1$$
$$a_k=4, \qquad a_{k-1}=2,8, \qquad a_{k+1}=8,2$$
$$a_k=6, \qquad a_{k-1}=4,9, \qquad a_{k+1}=9,4.$$

In conclusion, we have the strings $$a_{k-1}a_k a_{k+1}=\{643,346,632,236,124,421,139,931,248,842,469,964\}.$$
Juxtaposing the strings, we see that the greatest number we can construct is $9643$.

Italian IMO Team Selection Test 1990

Problem:
Let $P(x)=x^3-x+1$. Prove that, for every natural number $n > 1$, the numbers $n,P(n),P(P(n)),\ldots$ taken pairwise are relatively primes.

Solution:
Let $P_k(n)=\underbrace{P(P(\ldots P(n))))}_{k \ \textrm{times}}$. We prove by induction on $k \in \mathbb{N}^*$ that $P_k(n) \equiv 1 \pmod{P_i(n)}$ for every $0 \leq i \leq k-1$, where we set $P_0(n)=n$. In this way it's clear that taken two arbitrary numbers from the sequence, they will be relatively primes. If $k=1$ it is trivial, since $P(n)-n(n^2-1)=1$. Suppose that the statement is true for some $k$. Then, $$P_{k+1}(n)=P^3_{k}(n)-P_{k}(n)+1 \equiv 1 \pmod{P_{k}(n)}$$ and by induction hypothesis, $P_k(n) \equiv 1 \pmod{P_i(n)}$ for every $0 \leq i \leq k-1$, so $P_{k+1}(n) \equiv 1 \pmod{P_i(n)}$ for every $0 \leq i \leq k$ and the desired conclusion follows by the Principle of Mathematical Induction.

Italian IMO Team Selection Test 1988

Problem:
Decompose the natural number $n$ into a sum of natural numbers so that the product of the summands is maximum.

Solution:
We go further and give explicitly the maximum product. Let $n=a_1+a_2+\ldots+a_m$ and $P=a_1a_2\cdots a_m$, where $a_i \in \mathbb{N}^*$ for every $1 \leq i \leq m$ . If $n=1,2$, clearly $P_{\max}=1$. Assume $n > 2$. To maximize $P$, any number $a_i$ can't be $1$ since $a_i + 1 > a_i \cdot 1$ for every $1 \leq i \leq m$ and we can replace the two summands $a_i$ and $1$ with $a_i + 1$. Likewise, if $a_i > 4$, we can replace $a_i$ with $(a_i-2)+2$ since $2(a_i-2) > a_i$. At last, we observe that it's indifferent to have $4$ or $2+2$, so $P$ can be maximized with $2$'s and $3$'s. Since $3^2 > 2^3$, we can have at most two summands equal to $2$ since we can replace $2+2+2$ with $3+3$. To be more precise, we have $$P_{max} = \left\{ \begin{array}{lll} 3^k & \textrm{if } n=3k \\ 2^2 \cdot 3^{k-1} & \textrm{if } n=3k+1 \\ 2\cdot 3^k & \textrm{if } n=3k+2 \end{array} \right.$$ where $k \in \mathbb{N}^*$.