Mathematical Reflections 2011, Issue 6 - Problem O213

Problem:
Let $n$ be a positive integer and let $z$ be a complex number such that $z^{2^n-1}-1=0$. Evaluate
$$\prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right).$$

Proposed by Titu Andreescu.

Solution:

It's clear that if $z=1$, then $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=1$. Assume that $z \neq 1$. We have $$z^{2^n-1}-1=(z-1)(z^{2^n-2}+z^{2^n-3}+\ldots+z+1)=0,$$ so $z^{2^n-2}+z^{2^n-3}+\ldots+z+1=0$. Then,
$$\begin{array}{lll} \displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right) & = & \displaystyle \prod_{k=0}^{n-1}\left(z^{2^{k+1}}-z^{2^k}+1\right) \\  & = & \displaystyle  \prod_{k=0}^{n-1} \dfrac{z^{3\cdot2^k}+1}{z^{2^k}+1}.\end{array}$$ Clearly, $$\displaystyle \prod_{k=0}^{n-1} (z^{2^k}+1) = \sum_{k=0}^{2^n-1} z^k = z^{2^n-1} + \sum_{k=0}^{2^n-2} z^k = 1.$$ Let $n$ be odd. Since $\gcd(2^n-1,3)=1$, then $z^{3i} \neq z^{3j} \quad \forall i \not \equiv j \pmod{2^n-1}$. So, $$\displaystyle \prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = z^{3 (2^n-1)} + \sum_{k=0}^{2^n-2} z^{3k} = 1 + \sum_{k=0}^{2^n-2} z^k = 1,$$ which gives $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=1$. Now, let $n$ be even. Then $$z^{2^n-1}-1=(z^3-1)(z^{2^n-4}+z^{2^n-7}+\ldots+z^3+1)=0.$$ If $z$ is a third root of unity, then $z^3=1$ and
$$\prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = 2^n,$$ which gives $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=2^n$. If $z$ is not a third root of unity, since $z^{2^n-(3k+1)}=z^{3(2^n-1-k)}$, then
$$\prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = z^{3k(2^n-1)} + \sum_{k=1}^{2^n-1} z^{3(2^n-1-k)} = 1 + 3 \sum_{k=1}^{\frac{2^n-1}{3}} z^{2^n-(3k+1)} = 1.$$
In summary,
$$\prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=\left\{ \begin{array}{lll} 2^n & \textrm{if } n \textrm{ is even and } z = e^{\frac{2i\pi}{3}},e^{\frac{4i\pi}{3}} \\ 1 & \textrm{otherwise.} \end{array} \right.$$

Mathematical Reflections 2011, Issue 6 - Problem O212

Problem:
Let $f_0(i)=1$ for all $i \in \mathbb{N}$ and let $f_k(n)=\displaystyle \sum_{i=1}^n f_{k-1}(i)$ for $k \geq 1$. Prove that
$$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j)=F_n,$$ where $F_n$ is the $n$-th Fibonacci number.

Proposed by Ivan Borsenco.

Solution:
First we show that if $n,k \geq 1$, then
\begin{equation}\label{identity1}
\sum_{i=k}^{n} {i \choose k} = {n+1 \choose k+1}. \qquad (1)
\end{equation}
By Pascal's Identity,
$$\begin{array}{lll} \displaystyle \sum_{i=k}^{n} {i \choose k} & = &  \displaystyle {k \choose k+1} + \sum_{i=k}^{n} {i \choose k}\\
& = & \displaystyle {k+1 \choose k+1} + \sum_{i=k+1}^{n} {i \choose k} \\ & = & \displaystyle {k+2 \choose k+1} + \sum_{i=k+2}^{n} {i \choose k} \\ & = & \displaystyle \vdots \\ & = & \displaystyle {n+1 \choose k+1}. \end{array}$$
Now, we prove by induction on $k \geq 1$ that $f_k(n)=\displaystyle {n+k-1 \choose k}$ for any $n \in \mathbb{N}$.
For $k=1$ we have $f_1(n)=\displaystyle \sum_{i=1}^n f_{0}(i)=n$, so the equality holds. Suppose that the equality is true for $k$. Then
$$f_{k+1}(n)=\sum_{i=1}^n f_{k}(i)=\sum_{i=1}^n {i+k-1 \choose k} = {n+k \choose k+1}$$ by (1). Now, it is clear that $$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j) = \sum_{j=0}^{\lfloor \frac{n}{2}  \rfloor} {n-j-1 \choose j}.$$ So, we only have to prove that $$\sum_{j=0}^{\lfloor \frac{n}{2}  \rfloor} {n-j-1 \choose j}=F_n,$$ where $F_n$ is the $n$-th Fibonacci number. This can be done by induction on $n$. For $n=1$ and $n=2$ is obvious. Suppose that the equality holds for every $m$ such that $1 \leq m \leq n$. Since $\lfloor \frac{n-1}{2}  \rfloor + 1 = \lfloor \frac{n+1}{2} \rfloor$, we have
$$\begin{array}{lll} F_{n-1}+F_{n} & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n-1}{2}  \rfloor} {n-j-2 \choose j} + \sum_{j=0}^{\lfloor \frac{n}{2}  \rfloor} {n-j-1 \choose j} \\ & = & \displaystyle {n-1 \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2}  \rfloor}\left[{n-j-1 \choose j-1} + {n-j-1 \choose j}\right] \\ & = & \displaystyle
{n \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2}  \rfloor} {n-j \choose j} \\ & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n+1}{2}  \rfloor} {n-j \choose j} = F_{n+1}, \end{array}$$ as we wanted to prove.

Mathematical Reflections 2011, Issue 6 - Problem O211

Problem:
Prove that for any positive integer $n$ the number $(2^n+4^n)^2+4(6^n+9^n+12^n)$ has at least $9$ positive divisors.

Proposed by Titu Andreescu.

Solution:
Rewriting,
$$(2^n+4^n)^2+4\cdot3^n(2^n+4^n)+4\cdot9^n = (2^n+4^n+2\cdot3^n)^2 = 2^2(2^{n-1}+2^{2n-1}+3^n)^2.$$ Since $4$ has three positive divisors and $2^{n-1}+2^{2n-1}+3^n \neq 2^k, k \in \mathbb{N}$ for every positive integer $n$, then $2^{n-1}+2^{2n-1}+3^n$ has one prime divisor $p > 2$. So, there are at least $3 \cdot 3 = 9$ positive divisors for the given number, namely $$\{1,2,4,p,2p,4p,p^2,2p^2,4p^2\}.$$

Mathematical Reflections 2011, Issue 6 - Problem U212

Problem: 
Let $G$ be a finite abelian group such that $G$ contains a subgroup $K \neq \{e\}$ with the
property that $K \subset H$ for each subgroup $H$ of $G$ such that $H \neq \{e\}$. Prove that $G$ is a
cyclic group.

Proposed by Daniel Lopez Aguayo.

Solution:

We use the following  

Lemma.
A finite abelian group is not cyclic if and only if it contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ for some prime $p$.

Proof.
Let $G$ be a finite abelian group. If $G$ contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ (which is not cyclic) then $G$ can't be cyclic since every subgroup of a cyclic group is cyclic. Conversely, if $G$ is a finite abelian group which is not cyclic then (by Fundamental Theorem of Finitely Generated Abelian Groups) $G$ contains a subgroup isomorphic to $\mathbb{Z}_{p^a} \times \mathbb{Z}_{p^b}$, because if all the components in the direct product correspond to distinct primes, then $G$ would be cyclic. So, the subgroup $(p^{a-1}) \times (p^{b-1})$ of $\mathbb{Z}_{p^a} \times \mathbb{Z}_{p^b}$ is isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$.

Now, suppose that $G$ is not a cyclic group. Then $G$ contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ and this subgroup, by Cauchy's Theorem, contains a subgroup $H$ which is isomorphic to $\mathbb{Z}_p$. If $K \neq \{e\}$ is a proper subgroup of $H$, then, by Lagrange's Theorem, $|K|$ divides $|H|$, i.e. $|K|$ divides $p$. So $K=\{e\}$ or $K=H$, contradiction.

Mathematical Reflections 2011, Issue 6 - Problem U211

Problem:
On the set $M=\mathbb{R}-\{3\}$ the following binary law is defined:
$$x \ast y = 3(xy-3x-3y)+m,$$ where $m \in \mathbb{R}$. Find all possible values of $m$ such that $(M, \ast)$ is a group.

Proposed by Bogdan Enescu.

Solution:

First we observe that $x \ast y = 3(x-3)(y-3)+m-27$.
We want that $\ast$ satisfies the group axioms.

(i) Closure: For every $x,y \in M$, $x \ast y \in M$. It must be $3(x-3)(y-3)+m-27 \neq 3$, i.e. $3(x-3)(y-3)+m \neq 30$ and this is clearly satisfied for $m=30$.

(ii) Associativity: For every $x,y,z \in M, (x \ast y) \ast z = x \ast (y \ast z)$. It must be
$$\begin{array}{lll} [3(x-3)(y-3)+m-27] \ast z = 3[(3(x-3)(y-3)+m-27)-3][z-3]+m-27 \\
= 9xyz-27(xy+yz+zx)+3(27x+27y+(m-3)z)-8m \end{array}$$
and
$$\begin{array}{lll} x \ast [3(y-3)(z-3)+m-27] = 3(x-3)[3(y-3)(z-3)+m-27-3]+m-27 \\
= 9xyz-27(xy+yz+zx)+3((m-3)x+27y+27z)-8m, \end{array}$$
so the associativity holds if and only if $m=30$.

(iii) Identity element: There exists $e \in M$ such that for every $x \in M$, $x \ast e = e \ast x = x$. It must be
$$3(x-3)(e-3)+3=x \iff 3e(x-3)=10(x-3) \iff e=\dfrac{10}{3}.$$

(iv) Inverse element: For each $x \in M$, there exists $y \in M$ such that $x \ast y = y \ast x = e$. It must be
$$3(x-3)(y-3)+3=\dfrac{10}{3} \iff (x-3)(y-3)=\dfrac{1}{9} \iff y=\dfrac{1}{9(x-3)}+3.$$
So $(M,\ast)$ is a group if and only if $m=30$.

Mathematical Reflections 2011, Issue 6 - Problem S213

Problem:
Let $a,b,c$ be positive real numbers such that $a^2 \geq b^2+bc+c^2$. Prove that
$$a > \min(b,c) + \dfrac{|b^2-c^2|}{a}.$$

Proposed by Titu Andreescu.

Solution:
Without loss of generality, suppose that $\min(b,c)=c$. If $a \geq b+c$, then
$$a^2-ac \geq ab > (b+c)(b-c)=b^2-c^2.$$ If $a<b+c$, then
$$a^2-ac > a^2-(b+c)c \geq b^2 > b^2-c^2.$$ So, for any $a,b,c$ satisfying the required conditions, we have $a > \min(b,c) + \dfrac{|b^2-c^2|}{a}$.

Mathematical Reflections 2011, Issue 6 - Problem J215

Problem:
Prove that for any prime $p>3$, $\dfrac{p^6-7}{3}+2p^2$ can be written as sum of two perfect cubes.

Proposed by Titu Andreescu.

Solution:

We have
$$\begin{array}{lll} \dfrac{p^6-7}{3}+2p^2 & = & \dfrac{p^6+6p^2-7}{3}\\ & = & \dfrac{9p^6+54p^2-63}{27}\\
 & = & \dfrac{(p^6-12p^4+48p^2-64)+(8p^6+12p^4+6p^2+1)}{27} \\ & = & \left(\dfrac{p^2-4}{3}\right)^3 + \left(\dfrac{2p^2+1}{3}\right)^3\end{array}$$ and it is clear that the two summands on the right hand side are integers, since if $p > 3$, $p^2 \equiv 1 \pmod 3$. 

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