Olimpiade Italiana di Matematica

Solution:

We say that two numbers $i$ and $j$ are connected if one of them can be written in the form $m n$ and the other in the form $m(n+1)$ for suitable $m$ and $n$. The statement of the exercise tells us that $x_{i}$ is different from $x_{j}$ whenever $i$ and $j$ are connected. We want to prove that there are at least 2017 positive integers $i_{1} \ldots i_{2017}$ such that the 2017 terms $x_{i_{1}}, \ldots, x_{i_{2017}}$ of the sequence are all distinct from each other: this implies the assertion by the pigeonhole principle. It therefore suffices to prove that there exist 2017 positive integers $i_{1} \ldots i_{2017}$ pairwise connected to each other.
We prove by induction on $n$ that for every $n$ there exist $n$ positive integers $i_{1} \ldots i_{n}$ pairwise connected to each other. In the case $n=1$, the base of the induction, it suffices to fix $i_{1}=1$ and there is nothing to prove.
We observe that $i$ and $j$, with $i<j$, are connected if and only if $j-i$ is a divisor of $i$. Hence, if $i$ and $j$ are connected and $k$ is a multiple of $i$ then $k+i$ and $k+j$ are connected.
Coming to the inductive step, we have by hypothesis $n$ positive integers pairwise connected $i_{1}, \ldots, i_{n}$. Let $k$ be their product. By our observation the numbers $k+i_{1}, \ldots, k+i_{n}$ are pairwise connected. These numbers are also all connected to $k$. We have thus constructed $n+1$ numbers pairwise connected, as required to complete the induction.

Solution:

Assume for contradiction that $x_{i}$ is less than 2017 for every $i$. We will prove by induction on $n$ that for every $k$ there exists an interval of $k$ consecutive numbers such that the sequence $x_{i}$ takes at most $2016-n$ distinct values for $i$ ranging over the interval. From this a contradiction follows immediately by considering the case $n=2016, k=1$.
The base case of the induction, $n=0$, is an immediate consequence of the absurd hypothesis.
For the inductive step, we want to prove that there exists an interval of length $k$ such that $x_{i}$ takes at most $2016 - (n+1)$ distinct values on that interval. By the inductive hypothesis, we have an interval $I$ of length $3k!$ on which the sequence takes at most $2016-n$ distinct values. This interval must contain two consecutive multiples of $k!$, say $mk!$ and $(m+1)k!$, hence also the numbers of the form $mk!+j$ with $1 \leq j \leq k \leq k!$. Observing that $mk!$ is a multiple of $j$ for every $j=1, \ldots, k$, we see that the numbers $x_{mk!+j}$ are all different from $x_{mk!}$. The sequence $x_{i}$ therefore cannot assume $2016-n$ or more distinct values for $i$ in the interval $mk!+1, \ldots, mk!+k$, otherwise it would assume $2016-n+1$ or more values in the interval $I$, contradicting the inductive hypothesis.