Saudi Arabian Mathematical Competitions

See the solution in the test of level 4. $\square$

Denote $v_{p}(k)$ as the exponent of prime $p$ in the prime factorization of positive integer $k$. It is easy to see that $v_{p}(ab) = v_{p}(a) + v_{p}(b)$ for all positive integers $a, b$.

We have $2015 = 5 \cdot 13 \cdot 31$, $2016 = 2^{5} \cdot 3^{2} \cdot 7$.
Denote $M = 2015 \cdot 2016$ and
$$N = \{2, 3, 5, 7, 13, 31\}$$
Suppose there exist $n$ positive integers $x_{1}, x_{2}, x_{3}, \ldots, x_{n}$ arranged on the circle satisfying the given condition and denote $x_{n+1} \equiv x_{1}$ and $x_{n+2} \equiv x_{2}$.

Since $x_{i} x_{i+1}$ is not divisible by $M$ for $i = 1, \ldots, n$, then there exists a prime $p_{i} \in N$ such that
$$v_{p_{i}}(x_{i} x_{i+1}) < v_{p_{i}}(M) \Leftrightarrow v_{p_{i}}(x_{i}) + v_{p_{i}}(x_{i+1}) < v_{p_{i}}(M) \tag{*}$$
These primes form a sequence $p_{1}, p_{2}, \ldots, p_{n}$ and the elements can be repeated. We will prove that $p_{i} \neq p_{j}$ with $i, j$ two non-adjacent indices.

Indeed, if there are some non-adjacent indices $i, j$ such that $p_{i} = p_{j} = p$. Denote $a = v_{p}(M)$ and from (*), we have $v_{p}(x_{i}) + v_{p}(x_{i+1}) < a$ and $v_{p}(x_{j}) + v_{p}(x_{j+1}) < a$.
Hence, we have
$$v_{p}(x_{i}) + v_{p}(x_{i+1}) + v_{p}(x_{j}) + v_{p}(x_{j+1}) < 2a.$$
On the other hand, since $(i, j), (i+1, j+1)$ are pairs of non-adjacent indices then
$$v_{p}(x_{i}) + v_{p}(x_{j}) \geq a, \quad v_{p}(x_{i+1}) + v_{p}(x_{j+1}) \geq a.$$
This implies that
$$v_{p}(x_{i}) + v_{p}(x_{i+1}) + v_{p}(x_{j}) + v_{p}(x_{j+1}) \geq 2a,$$
which is a contradiction.

Continue, suppose that there exists an index $i$ such that $p_{i} = p_{i+1} = p$. If $v_{p}(M) = 1$, because $x_{i} x_{i+1}$ and $x_{i+1} x_{i+2}$ are not divisible by $M$, we can conclude that $x_{i}, x_{i+1}, x_{i+2}$ are not divisible by $p$. Hence $x_{i} x_{i+2}$ is not divisible by $M$, contradiction because $x_{i}, x_{i+2}$ are not adjacent.
So if $p_{i} = p_{i+1} = p$, then we must have $v_{p}(M) \geq 2$.

Now we can conclude that the sequence $p_{1}, p_{2}, \ldots, p_{n}$ has the following properties:
- Each prime $p_{i} \in N$ appears at most 2 times.
- If some prime $p_{i} \in N$ appears 2 times, then $p_{i}^{2} \mid M$.

Hence, we have
$$p_{1} p_{2} \ldots p_{n} \mid M.$$
Since $M = 2^{5} \cdot 3^{2} \cdot 5 \cdot 7 \cdot 13 \cdot 31$, we can see that $n \leq 8$ (in the sequence $(p_{i})$, prime $2$ appears $2$ times, prime $3$ appears $2$ times and the rest appear $1$ time). It is easy to check that if we choose 8 numbers as follows:
$$\frac{M}{2^{5}}, \frac{M}{2 \cdot 3}, \frac{M}{3^{2}}, \frac{M}{3 \cdot 5}, \frac{M}{5 \cdot 7}, \frac{M}{7 \cdot 13}, \frac{M}{13 \cdot 31}, \frac{M}{31 \cdot 2}$$
and the corresponding sequence is
$$p_{1} = 2,\ p_{2} = 3,\ p_{3} = 3,\ p_{4} = 5,\ p_{5} = 7,\ p_{6} = 13,\ p_{7} = 31,\ p_{8} = 2.$$
Therefore, the maximum value of $n$ is $8$. $\square$