SAUDI ARABIAN IMO Booklet, 2023

For $n = 2$, we have $P(k) \in \{r, s, t\}$ with $k = 1, 2, 3, 4, 5, 6$. Since $\deg P = 2$, there are no more than $2$ value of $k$ such that $P(k) = r$. Similarly for $P(k) = s$, $P(k) = t$. From this it follows that each of the above equations must have exactly $2$ solutions. Notice that all three equations have the same coefficients $x^2$ and $x$ so the sum of the solutions of them are equal and should be $7$. Then the $6$ solutions above will be divided in pairs $(1, 6)$, $(2, 5)$, $(3, 4)$. We can assume
$$\begin{cases} P(x) - r = (x - 1)(x - 6) \\ P(x) - s = (x - 2)(x - 5) \\ P(x) - t = (x - 3)(x - 4) \end{cases}$$
from this, it follows that
$$3P(x) - (r + s + t) = (x - 1)(x - 6) + (x - 2)(x - 5) + (x - 3)(x - 4)$$
or $3P(x) + 2023 = 3x^2 - 21x + 28$ so $P(x) = x^2 - 7x - 665$ and $r, s, t$ respectively are $-671, -675, -677$.

Next, suppose there exists $P(x)$ of degree $n \ge 3$ satisfying the given problem, without loss of generality suppose $r < s < t$. According to the argument above, each equation $P(x) - r$, $P(x) - s$, $P(x) - t$ there will be exactly $n$ distinct solutions from $\{1, 2, 3, \dots, 3n\}$. In addition, according to Viete's theorem, since each equation has at least the first three coefficients in common. First the sum of the solutions and the sum of the squares of their solutions must be equal.

Considering the function $f(x) = P(x) - r$ has $n$ distinct solutions, according to the mean-value theorem, $f'(x) = P'(x)$ must have $n-1$ distinct roots, denoted by $c_1 < c_2 < \dots < c_{n-1}$. The equation $P(x) = r$ have unique root on each interval $(-\infty; c_1), (c_1, c_2), \dots, (c_{n-1}, +\infty)$. The same for $P(x) = s$, $P(x) = t$. We have the following two cases:

Case 1. If $n$ is odd then it is easy to see in the first interval, $P(x)$ increasing so $P(x) = r$, $P(x) = s$, $P(x) = t$ will take the roots $1, 2, 3$. in that other. In the next interval, the function is decreasing so they will take the roots of $6, 5, 4$ respectively, and so on, to the end of the interval will end up with $3n - 2, 3n - 1, 3n$. Then, it is easy to see that the sum of the solutions of the three equations in the first interval $n-1$ are equal, but in the last interval, each equation has a different solution, so the sum of their solutions is different, contradiction.

Case 2. If $n$ is even, put $n = 2m$ then the three equations will have solutions of $1, 2, 3, \dots, 6m$ and similar to the above argument, $P(x) = r$ there will be solutions $\{1, 6, 7, 12, \dots, 6m - 5, 6m\}$. The sum of the squares of these numbers will be
$$\sum_{k=1}^{m} (6k-5)^2 + (6k)^2 = \sum_{k=1}^{m} (72k^2 - 60k + 25) = m(24m^2 + 6m + 7).$$
Otherwise, the sum of squares of all $6m$ numbers is
$$\frac{6m(6m+1)(12m+1)}{6} = m(6m+1)(12m+1)$$
so each equation must whose sum of squares of the solutions is $\frac{1}{3}$ of this value. Thus
$$3m(24m^2 + 6m + 7) = m(6m + 1)(12m + 1)$$
or
$$72m^2 + 18m + 21 = 72m^2 + 18m + 1,$$
contradiction. This shows that in all cases we cannot have a polynomial $P(x)$ satisfying the problem.

So the only positive integer that satisfies the problem is $n = 2$. □