## Task 4.

Let $a_{1}, a_{2}, a_{3}, \ldots$ be an infinite sequence of numbers from the set $\{1,2,3,4,5,6,7,8\}$ such that for every pair of natural numbers $(m, n)$, the conditions $a_{n} \mid n$ and $a_{m} \mid m$ are satisfied if and only if $a_{m+n}=a_{m}+a_{n}-1$.

Determine all possible values that $a_{5555}$ can take.
## Solution.

Consider a sequence $a_{1}, a_{2}, \ldots$ that satisfies the conditions of the problem. For a natural number $j$, we say that $j$ is beautiful if $a_{j}=1$.

Assume that $m$ and $n$ are beautiful. Then $a_{m} \mid m$ and $a_{n} \mid n$, so from the condition of the problem it follows that

$$
a_{m+n}=a_{m}+a_{n}-1=1
$$

Thus, the set of beautiful numbers is closed under addition. (1)

Notice that 840 is the least common multiple of $1,2, \ldots, 8$. Then for any natural number $j$, we have $a_{840 j} \mid 840 j$. Applying the condition of the problem to $840 j$ and 840, we get that for any $j$,

$$
a_{840(j+1)}=a_{840 j}+a_{840}-1
$$

From this relation, by mathematical induction, it follows that for any $j$, $a_{840 j}=j a_{840}-(j-1)$. If $a_{840}>1$, then $a_{840 \cdot 8} \geqslant 8 \cdot 2-7>8$, which is a contradiction. Therefore, 840 is beautiful, and from (1) we conclude that all multiples of 840 are beautiful. (2)

Consider all numbers of the form $a_{840 k+1}$ for $k \in \mathbb{N}$. By the Pigeonhole Principle, there are two of them that are equal. Let these be $a_{840 m+1}$ and $a_{840 n+1}$ for $m < n$. Then, similarly to the proof of statement (3), we get that necessarily $a_{840 a+515} \mid 840 a+515$, so $a_{840 a+515} \in\{1,5\}$, which is a contradiction with the assumptions.

We conclude that the only possibility is $a_{5555}=1$. Since the sequence $1,1,1, \ldots$ satisfies the conditions of the problem, we see that this is indeed possible.

## CROATIAN MATHEMATICAL OLYMPIAD  Final test for IMO team selection

Zagreb, June 4, 2022.