Indian National Mathematical Olympiad

Solution:

If some number $M + k$, $1 \leq k \leq n$, has at least $n$ distinct prime factors, then we can associate a prime factor of $M + k$ with the number $M + k$ which is not associated with any of the remaining $n - 1$ numbers.

Suppose $M + j$ has less than $n$ distinct prime factors. Write
$$M + j = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{r}^{\alpha_{r}}, \quad r < n$$
But $M + j > n^{n-1}$. Hence there exist $t$, $1 \leq t \leq r$ such that $p_{t}^{\alpha_{t}} > n$. Associate $p_{t}$ with this $M + j$. Suppose $p_{t}$ is associated with some $M + l$. Let $p_{t}^{\beta_{t}}$ be the largest power of $p_{t}$ dividing $M + l$. Then $p_{t}^{\beta_{t}} > n$. Let $T = \operatorname{gcd}\left(p_{t}^{\alpha_{t}}, p_{t}^{\beta_{t}}\right)$. Then $T > n$. Since $T \mid (M + j)$ and $T \mid (M + l)$, it follows that $T \mid (|j - l|)$. But $|j - l| < n$ and $T > n$, and we get a contradiction. This shows that $p_{t}$ cannot be associated with any other $M + l$. Thus each $M + j$ is associated with different primes.