Problem 1164

SOLUTION: Let's say that two numbers $i$ and $j$ are connected if they can be written one in the form $m n$ and the other in the form $m(n+1)$ for suitable $m$ and $n$. The problem statement 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 different from each other: this implies the statement by the pigeonhole principle. It is therefore enough to prove that there are 2017 positive integers $i_{1} \ldots i_{2017}$ that are pairwise connected.

We prove by induction on $n$ that for every $n$ there exist $n$ positive integers $i_{1} \ldots i_{n}$ that are pairwise connected. In the case $n=1$, the base of the induction, it is enough 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$. Therefore, if $i$ and $j$ are connected and $k$ is a multiple of $i$ then $k+i$ and $k+j$ are connected.

For the inductive step, we have by hypothesis $n$ positive integers that are 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 therefore constructed $n+1$ numbers that are pairwise connected, as required to complete the induction.

Alternative 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$ different values for $i$ varying in the interval. This immediately leads to a contradiction by considering the case $n=2016, k=1$.

The base 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)$ different values in that interval. By the inductive hypothesis, we have an interval $I$ of length $3 k$ ! on which the sequence takes at most 2016 - $n$ different values. This interval must contain two consecutive multiples of $k$ !, say $m k$ ! and $(m+1) k$ !, and therefore also the numbers of the form $m k !+j$ with $1 \leq j \leq k \leq k$ !. Observing that $m k$ ! is a multiple of $j$ for every $j=1, \ldots, k$, we see that the numbers $x_{m k !+j}$ are all different from $x_{m k !}$. The sequence $x_{i}$ cannot therefore assume 2016-n or more different values for $i$ in the interval $m k !+$ $1, \ldots, m k !+k$, otherwise it would assume 2016-n+1 or more different values in the interval $I$, contradicting the inductive hypothesis.