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}^*$.

Italian Mathematical Olympiad 1992 - Problem 6

Problem:
Let $a$ and $b$ be integers. Prove that if $\sqrt[3]{a}+\sqrt[3]{b}$ is a non-zero rational number, then both $a$ and $b$ are perfect cubes.

Solution:
Let $\sqrt[3]{a}+\sqrt[3]{b}=q \in \mathbb{Q}^*$. From the hypotheses, $a$ and $b$ can't be both zero: without loss of generality we can suppose that $a \neq 0$. Seeking a contradiction, assume that $a$ is not a perfect cube. By Gauss' Lemma, the polynomial $x^3-a$ is irreducible over $\mathbb{Q}$ since it is irreducible over $\mathbb{Z}$: in fact if it was reducible over $\mathbb{Q}$, there would exist $\alpha \in \mathbb{Z}$ such that $\alpha^3 - a = 0$, which contradicts our assumption. Therefore $x^3-a$ is the minimum polynomial of $\sqrt[3]{a}$ over $\mathbb{Q}$ and $[\mathbb{Q}(\sqrt[3]{a}):\mathbb{Q}]=3$. Then, from the initial equation we obtain
$$\sqrt[3]{b}=q-\sqrt[3]{a} \iff (a+b-q^3)+3q^2\sqrt[3]{a} -3q\sqrt[3]{a^2} = 0$$ and since
$\{1,\sqrt[3]{a}, \sqrt[3]{a^2}\}$ is a basis over $\mathbb{Q}$, it must be $a+b=q=0$, which contradicts the hypotheses.  

Italian Mathematical Olympiad 1994 - Problem 2

Problem:
Find all integer solutions of the equation $y^2=x^3+16$.

Solution:
We immediately see that $(0,-4)$ and $(0,4)$ are solutions of the given equation. We show that there are no other solutions. Rewriting the equation, we have $$(y-4)(y+4)=x^3.$$ Since the difference of the two factors on the left hand side is $8$, then $\gcd(y-4,y+4) \in \{1,2,4,8\}$ and we have $$y-4=2^n a, \qquad y+4=2^n b$$ with $n \in \{0,1,2,3\}, a,b \in \mathbb{Z}^*$, $\gcd(a,b)=1$. If $n=1,2$, from $2^n(b-a)=8$, we must have $a,b$ odd, but since $2^{2n}ab=x^3$, this is impossible by Unique-Prime-Factorization Theorem. If $n=3$, then $b-a=1$, and from $2^6a(a+1)=x^3$, we have that $a(a+1)$ is a perfect cube, and since $\gcd(a,a+1)=1$, $a$ and $a+1$ must be both perfect cubes, clearly impossible. At last $n=0$, i.e. $\gcd(y-4,y+4)=1$ and both $y-4$ and $y+4$ are perfect cubes whose difference is $8$. But this is impossible: in fact if there exist $k,m \in \mathbb{Z}$ such that $y-4=k^3$ and $y+4=m^3$, then $k^3$ and $m^3$ have the same parity and they are relatively primes, so they must be odd, and also $k$ and $m$ must be odd. Therefore, $$(m-k)(m^2+mk+k^2)=8$$ and by parity we force $$\begin{array}{ccc} m^2+mk+k^2 & = & 1 \\ m-k & = & 8, \end{array}$$ which implies $m^2+k^2=22 \equiv 6 \pmod{8}$, contradiction.

Italian IMO Team Selection Test 1994 - Problem 2

Problem:
Find all prime numbers $p$ for which $\dfrac{2^{p-1}-1}{p}$ is a perfect square.

Solution:
Since $2^{p-1}-1$ is odd for all primes $p$, it's easy to see that $p \neq 2$. Moreover, by Fermat's Little Theorem we have $2^{p-1} \equiv 1 \pmod{p}$ for all primes $p \neq 2$, so $\dfrac{2^{p-1}-1}{p}$ is an integer and we want this integer to be a perfect square. Then, $$pn^2 = 2^{p-1} - 1, \quad n \in \mathbb{N}.$$ Since $p > 2$, $p-1$ is even and so we can write $$pn^2=(2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1).$$ Both factor on the right hand side are odd and are relatively primes since their difference is $2$. This means that $p$ divides exactly one between the two factors and the other is a perfect square. If $p$ divides the first factor, we have $$2^{\frac{p-1}{2}}-1=pa^2, \qquad 2^{\frac{p-1}{2}}+1=b^2$$ where $a,b \in \mathbb{N}^*$. From the second equation we find $2^{\frac{p-1}{2}}=(b-1)(b+1)$ and these two factors are both powers of $2$ whose difference is $2$, so $b=3$ and $p=7$. If $p$ divides the second factor, we have $$2^{\frac{p-1}{2}}-1=a^2, \qquad 2^{\frac{p-1}{2}}+1=pb^2$$ and from the first equation,  if $p>3$ then $2^{\frac{p-1}{2}}-1=a^2 \equiv 3 \pmod{4}$, contradiction. So, it must be $p=3$ and for such value, $\dfrac{2^{3-1}-1}{3}=1$ which is a perfect square. In conclusion, the only prime numbers $p$ which satisfy the given condition are $p=3$ and $p=7$.