72nd Czech and Slovak Mathematical Olympiad

Since all terms $a_i$ are positive integers, we have $$a_5=a_1{a}_2+a_2{a}_3+a_3{a}_4-1\ge 1+1+1-1=2,\text{ and therefore }{a}_5\ne 1.$$ The number $a_5$ is thus divisible by at least one prime number. For every $n\ge 4$, the following holds $$\begin{array}{rl}{a}_n& =(a_1{a}_2+a_2{a}_3+\cdots +a_{n-3}{a}_{n-2})+a_{n-2}{a}_{n-1}-1=\\ & =(a_{n-1}+1)+a_{n-2}{a}_{n-1}-1=\\ & =a_{n-1}(a_{n-2}+1),\end{array}$$ and therefore $a_{n-1}\mid a_n$. Let $p$ be any prime divisor of $a_5$, then the relation $a_{n-1}\mid a_n$ implies $p\mid a_6$, from where $p\mid a_7$, and so on. By mathematical induction we get $p\mid a_n$ for every $n\ge 5$. Thus, the prime $p$ divides infinitely many terms of the given sequence. This completes the proof of part a).

Let $\mathcal{P}$ denote the set of all primes that divide infinitely many terms of the sequence. Suppose that the set $\mathcal{P}$ is finite, i.e. $\mathcal{P}=\{p_1,\dots ,p_k\}$ for a suitable $k$. Obviously, for every $i\in \{1,2,\dots ,k\}$ we find such a term $a_{n_i}$ that is divisible by $p_i$ and $n_i\ge 5$. Due to the relation $a_{n-1}\mid a_n$ (proved earlier for each $n\ge 4$) we have $p_i\mid a_n$ for all $n\ge n_i$. If we now denote $N=\max (n_1,\dots ,n_k)$, then $a_N$ is divisible by all primes $p_1,\dots ,p_k$. Therefore, $a_N+1>1$ is not divisible by any primes from $\mathcal{P}$, so there must be a prime $q\notin \mathcal{P}$ satisfying $q\mid a_N+1$. This prime $q$ is then also a divisor of the number $a_{N+2}=a_{N+1}(a_N+1)$, so $q\mid a_n$ holds for each $n\ge N+2$, and therefore $q\in \mathcal{P}$. Thus, we get a contradiction, that proves the statement in part b).