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