IMO 2016 Shortlisted Problems

We have the following observations. (i) $(P(n),P(n+1))=1$ for any $n$. We have $(P(n),P(n+1))=\left(n^2+n+1,n^2+3n+3\right)=\left(n^2+n+1,2n+2\right)$. Noting that $n^2+n+1$ is odd and $\left(n^2+n+1,n+1\right)=(1,n+1)=1$, the claim follows.

(ii) $(P(n),P(n+2))=1$ for $n\not\equiv 2(\mathrm{mod}7)$ and $(P(n),P(n+2))=7$ for $n\equiv 2(\mathrm{mod}7)$. From $(2n+7)P(n)-(2n-1)P(n+2)=14$ and the fact that $P(n)$ is odd, $(P(n),P(n+2))$ must be a divisor of $7$. The claim follows by checking $n\equiv 0,1,\dots ,6(\mathrm{mod}7)$ directly.

(iii) $(P(n),P(n+3))=1$ for $n\not\equiv 1(\mathrm{mod}3)$ and $3\mid (P(n),P(n+3))$ for $n\equiv 1(\mathrm{mod}3)$. From $(n+5)P(n)-(n-1)P(n+3)=18$ and the fact that $P(n)$ is odd, $(P(n),P(n+3))$ must be a divisor of $9$. The claim follows by checking $n\equiv 0,1,2(\mathrm{mod}3)$ directly.

Suppose there exists a fragrant set with at most $5$ elements. We may assume it contains exactly $5$ elements $P(a),P(a+1),\dots ,P(a+4)$ since the following argument also works with fewer elements. Consider $P(a+2)$. From (i), it is relatively prime to $P(a+1)$ and $P(a+3)$. Without loss of generality, assume $(P(a),P(a+2))>1$. From (ii), we have $a\equiv 2(\mathrm{mod}7)$. The same observation implies $(P(a+1),P(a+3))=1$. In order that the set is fragrant, $(P(a),P(a+3))$ and $(P(a+1),P(a+4))$ must both be greater than $1$. From (iii), this holds only when both $a$ and $a+1$ are congruent to $1(\mathrm{mod}3)$, which is a contradiction.

It now suffices to construct a fragrant set of size $6$. By the Chinese Remainder Theorem, we can take a positive integer $a$ such that $$a\equiv 7(\mathrm{mod}19),a+1\equiv 2(\mathrm{mod}7),a+2\equiv 1(\mathrm{mod}3).$$ For example, we may take $a=197$. From (ii), both $P(a+1)$ and $P(a+3)$ are divisible by $7$. From (iii), both $P(a+2)$ and $P(a+5)$ are divisible by $3$. One also checks from $19\mid P(7)=57$ and $19\mid P(11)=133$ that $P(a)$ and $P(a+4)$ are divisible by $19$. Therefore, the set $\{P(a),P(a+1),\dots ,P(a+5)\}$ is fragrant.

Therefore, the smallest size of a fragrant set is $6$.