Ok so 1 combo in the whole egmo @below fixed @2below P1 didn't feel combo Although idk,I'm not qualified enough to comment.

HoRI_DA_GRe8 wrote: Find all positive integers $d$ for which there exists a degree $d$ polynomial $P$ with real coefficients such that there are at most $d$ different values among $P(0),P(1),P(2),\ldots,P(d^2-d).$ You made an error, fixed it for you.

HoRI_DA_GRe8 wrote: I don't see any proper combo in the whole egmo Is P1 not combinatorics, is P4 not combinatorics?

P4 is definitely combinatorics (due to the required clever argument to be solved), P1 is more like algebra.

Here is the official fields of the problems; P1: algebra P2: geometry P3: number theory P4: combinatorics P5: number theory P6: algebra (Even though it felt like there were 3 algebra and 3 number theory problems in the exam..)

redacted until fixed

Plot twist: $d=3$ is also a solution.

Assassino9931 wrote: Plot twist: $d=3$ is also a solution. I guess I did some calculation mistake, but the idea of solution is clear.

@above, hi it is not very clear to me, can you show me the calculations please

math_comb01 wrote: and hence there will be exactly $d-1$ distinct values each appearing $d-1$ times while one value appearing $d$ times Sorry, can you please explain why this is the case? Why can't it be that more than one value appears $d$ times?

atdaotlohbh wrote: math_comb01 wrote: and hence there will be exactly $d-1$ distinct values each appearing $d-1$ times while one value appearing $d$ times Sorry, can you please explain why this is the case? Why can't it be that more than one value appears $d$ times? I'll add a proof of this later, we need to prove that for polynomials of degree greater than 3, if their difference is integer then both can not have all natural roots, the proof is by contradiction, the idea is to plug in the roots of the other polynomial into the first polynomial. EDIT: I think I made a mistake in my proof.

Womp womp rewrite again. Construction For $d = 1, 2, 3$, the constructions $P \equiv 1, (x-0.5)^2, (x-1)(x-2)(x-6)$ work. Bounding We now show that no $d \ge 4$ work. FTSOC take a polynomial with degree $d$ that works. Based off the real roots of the derivative, split the sequence $0, 1, 2, \dots, d^2 - d$ into $k$ maximal intervals, call them branches, on which $P$ is strictly monotonic. If there are integral local maximums/minimums, assign them arbitrarily for now. [asy][asy] import graph; real f(real x) { return x*x*x - 2*x + 5; } path g1 = graph(f,-1.5,-sqrt(2/3)); draw(g1,red); path g2 = graph(f,-sqrt(2/3),sqrt(2/3)); draw(g2,blue); path g3 = graph(f,sqrt(2/3),1.3); draw(g3,green); for (real i = -15; i <= 13; ++i) { dot((i/10, f(i/10))); } draw((-sqrt(2/3),3.5)--(-sqrt(2/3), f(-sqrt(2/3))), dotted); draw((sqrt(2/3),3.5)--(sqrt(2/3), f(sqrt(2/3))), dotted); draw((-1.5,3.5)--(1.3,3.5)); [/asy][/asy] Note that adjacent branches have opposite directions. Let the image of $P$ on $0, \dots, d^2 - d$ be $A = \{a_1, a_2, \dots, a_n\}$ when sorted. Claim: We have that $k = n = d$. Proof. $k \le d$ follows by the derivative bound. $k \ge d$ must also hold because each branch can have at most $d$ elements (as each value in a branch is distinct). Similarily, we must have $n = d$, because each value can appear at most $d$ times in the polynomial. $\blacksquare$ Define an evenness point $\alpha$ as a point such that $P(\alpha + x) = P(\alpha - x)$ for each $x$. Let's now classify what causes evenness points. Suppose that we have two branches of the opposite montonicity, and they are the same on a run of consecutive integers of length at least $\frac{d}{2}$. Then this gives $2 \cdot \frac{d}{2} + 1 = d + 1$ solutions to a polynomial identity around the average of the two runs. This polynomial identity has either degree $d-1$ or $d+1$ depending on the parity of $d$, and thus is satisfied. Call these pairs of branches which cause evenness points hazardous. Notably, consider the case where one branch has length $d$ and the other has length $d-1$. Note that the length $d-1$ branch "skips" an element when looking at $A$. As such, a hazardous pair occurs when $d$ is even automatically (take the larger run of the branch). If $d$ is odd, it cocurs when the skipped element isn't $a_{\frac{d+1}{2}}$ Claim: $P$ must be even about some point of the form $\frac{n}{2}$ for integral $n$. Proof. FTSOC suppose not. Note that by size there must be branch of size $d$. If there are two branches of size $d$ with the same monotonicity, considering $P(\alpha + x) - P(x)$ gives a contradiction by being an identity. Else, they have different monotonicities, in which case this gives us evenness due to being satisfied for $2d + 1$ elements. As such, all other branches must have size at most $d - 1$, which forces this to be strict by size. In the even case, this immediately finishes by giving us a hazardous pair. Now, consider the odd case. For $d \ge 5$, consider the branches of the other monotonicity to the branch with size $d$. If one of them doesn't skip $a_{\frac{d+1}{2}}$, we are done as before. For $d = 5$, this forces the branches to contain one of the runs of \[ \{a_5, a_4, a_3, a_2\}, \{a_1, a_2, a_4, a_5\}, \{a_5, a_4, a_3, a_2, a_1\}, \{a_1, a_2, a_4, a_5\} \]or \[ \{a_5, a_4, a_3, a_2, a_1\}, \{a_1, a_2, a_4, a_5\}, \{a_5, a_4, a_3, a_2\}, \{a_1, a_2, a_4, a_5\} \]The first one has at least $5$ solutions to $P(x) = P(x + 8)$, a contradiction. The second one has at least $6$ solutions about the evenness point between the second and third branch, which finishes. Note that the conditions means that this is forced once we have runs of branches length $4, 4, 5, 4$ or $5, 4, 4, 4$. By flipping, this gives $4, 5, 4, 4$ and $4, 4, 4, 5$. This generalizes nicely (and by flipping) to all occurences of $4$ consecutive branches of $d-1, d-1, d, d-1$ and so forth. $\blacksquare$ Claim: $P$ has even degree, aka $d$ is even. Proof. Shift $P$ to be symmetric about $0$. Then its a polynomial in $x^2$, and must have even coefficients. $\blacksquare$ We can now redefine how to assign integral local maximums / minimums to branches: If it is integral, the local minimum/maximum at the evenness point is not assigned to any branch. Any other local minimum or maximum goes to the branch closer to the evenness point. Claim: We can assume that $P$ is even about the middle of some interval $\{0, 1, \dots, d^2 - d + \varepsilon\}$ where $\varepsilon$ is $0$ or $1$. Proof. If the evenness point is an integer, then by flipping around it when necessary and shifting, we can get the case of $\varepsilon = 0$. If the evenness point is not an integer, then this is the case of $\varepsilon = 1$ by the same argument. $\blacksquare$ Now, suppose that there exists a branch $b$ of size $d$. Then its copy $b'$ flipped around $\frac{d^2 - d + \varepsilon}{2}$ also has size $d$. Then if any other branch has size $d-1$, since $d$ is even, we then we get a hazardous pair $p$ with one of $b, b'$. Since $(b, b')$ already form a hazardous pair with center $\frac{d^2 - d}{2}$, $p$ must force a new evenness point, contradiction. This then must force that then all branches have size $d-1$, so we need $\varepsilon = 0$ to handle the $d^2 - d + 1 - d(d-1) = 1$ element not in any branch. Claim: We are done for $d \ge 6$. Proof. Pair these branches into hazardous pairs $(b, b')$ by flipping as above. Dissect $A = A_1 \sqcup A_2$ where $A_1 = \{a_1, \dots, a_{\frac{d}{2}}\}$ and $A_2 = \{a_{\frac{d}{2} + 1}, \dots, a_d\}$. Now, represent each pair by the element of $A$ that they skip. If two pairs have a representative element in the same $A_i$, then we get a run of length $\frac{d}{2}$ in the other $A_{2-i}$, which gives a new hazardous pair and evenness point, contradiction. This holds when there are more than $3$ pairs or $d \ge 6$. $\blacksquare$ Claim: $d = 4$ also just doesn't work. Proof. Shift $P$ to be symmetric about $0$, so we are considering the integers $-6, -5, \dots, 5, 6$. Since $P$ is even we can assume that $P = x^4 + cx^2$ for some $c$. (Scaling and the constant term don't matter). We take the branches $b_{-2}, b_{-1}, b_1, b_2$ in order, where $b_{-i}$ is the flipped copy of $b_i$. Each branch has size $3$. Note that $P(0) = 0$, so $A = \{0, a_2, a_3, a_4\}$. Now, if the branches $b_{-2}$ and $b_2$ contain $0$, then this implies that $P(-6) = P(6) = 0$, so $P = x^4 - 36x^2$, which doesn't work. Else, this implies that $b_{-2}, b_2$ skip $0$ and contain $a_2, a_3, a_4$. However, then $(b_{-2}, b_{-1})$ is a hazardous pair, contradiction. $\blacksquare$

Wrong solution

@above Why can you replace k with $d^2-d-1$ ?You have the restriction that $P(y_1)=P(y_2)=\cdots=P(y_{k})=c_2$

Note that $d=1,2,3$ work. For $d=1$, simply take $P\left(x\right)=x$. For $d=2$, take $P\left(x\right)=x\left(x-1\right)$. For $d=3$, take $P\left(x\right)=\left(x-1\right)\left(x-2\right)\left(x-6\right)$. Suppose $d>3$. We claim that no polynomial works. Lemma 1: (Fundamental Theorem of Algebra) If $P$ is a polynomial with degree $d$, then there are at most $d$ solutions to $P\left(x\right)=c$ for any constant $c$. Lemma 2: If $P$ is a polynomial with degree $d$ and has roots $x_1,x_2,\ldots,x_d$, then considering the intervals \[\left(-\infty,x_1\right),\left(x_1,x_2\right),\ldots,\left(x_d,+\infty\right)\]the sign of $P$ alternates. By PHP, there exist $0\le x_1<x_2<\cdots<x_d\le d^2-d$ such that $P\left(x_1\right)=P\left(x_2\right)=\cdots=P\left(x_d\right)=c$. Replace $P$ with $P-c$ for convenience. Consider the intervals \[\left[0,x_1\right),\left(x_1,x_2\right),\ldots,\left(x_d,d^2-d\right]\]Call the first and the last intervals as boundary intervals. If two numbers belong to same boundary interval, then they can’t agree on the polynomial. We first show that it is not possible to find $x_1^\prime<x_2^\prime<\cdots<x_d^\prime$ such that $P\left(x_1^\prime\right)=P\left(x_2^\prime\right)=\cdots=P\left(x_d^\prime\right)$ Suppose it was possible. If $d$ was odd, then at most one boundary interval might contain a number $x_i^\prime$. WLOG suppose no number is in $\left(x_d,d^2-d\right]$. The first boundary interval can have at most $1$ element, and any non-boundary interval (we may choose at most $\frac{d-1}{2}$ such intervals to ensure sign) can have at most $2$ elements. In total, we get at most $2\left(\frac{d-1}{2}\right)+1=d$ elements. But since we have exactly $d$ elements, it means that $0\le x_1^\prime<x_1<x_2<x_2^\prime<x_3^\prime<x_3<\cdots<x_d^\prime<x_d$. Taking similar intervals $\left[0,x_1^\prime\right),\left(x_1^\prime,x_2^\prime\right),\ldots,\left(x_d^\prime,d^2-d\right]$, we get a contradiction. A similar method follows for $d$ being even, just that either both boundary intervals are chosen or both are not containing any element. In either case, we get at most d elements. So, we have one of the two: 1. $0\le x_1^\prime<x_1<\cdots<x_2<\cdots<x_d<x_d^\prime<d^2-d$. 2. $x_1<x_1^\prime<x_2^\prime<x_2<x_3<x_3^\prime\cdots<x_d^\prime<x_d$. In either case, we get a contradiction by considering intervals \[\left[0,x_1^\prime\right),\left(x_1^\prime,x_2^\prime\right),\ldots,\left(x_d^\prime,d^2-d\right]\]. It follows that for any $P\left(y^\prime\right)\neq0$, the number of solutions to $P\left(x\right)=P\left(y^\prime\right)$ is exactly $d-1$. Consider numbers $y_1<y_2<\cdots<y_{d-1}$ such that $P\left(y_1\right)=P\left(y_2\right)=\cdots=P\left(y_{d-1}\right)$. Note that out of the intervals $\left[0,x_1\right),\left(x_1,x_2\right),\ldots,\left(x_d,d^2-d\right]$, since there are only $d-1$ elements to consider, one interval (say interval $I$) has a “vacancy”. Define $y_d=\left(x_1+x_2+\cdots+x_d\right)-\left(y_1+y_2+\cdots+y_{d-1}\right)$. Clearly, $y_d$ is an integer as well. Consider the polynomial $P_1\left(x\right)=\left(x-y_1\right)\left(x-y_2\right)\cdots\left(x-y_{d-1}\right)$. Since $P\left(y_1\right)=P\left(y_2\right)=\cdots=P\left(y_{d-1}\right)$ we may write by Remainder Theorem: \[\left(x-x_1\right)\left(x-x_2\right)\cdots\left(x-x_d\right)=\left(x-y_1\right)\cdots\left(x-y_{d-1}\right)Q\left(x\right)+c^\prime\]Here, $c^\prime$ is some nonzero constant. Note that $Q\left(x\right)$ is a linear monic polynomial, which means $Q\left(x\right)=x-s$ for some $s$. Comparing the degree of $x^{d-1}$ on both sides, we get $s=\left(x_1+x_2+\cdots+x_d\right)-\left(y_1+y_2+\cdots+y_{d-1}\right)$, which means $s=y_d$. So, $y_d$ is actually the “vacancy” in the interval $I$. However, since we cannot have set $\{y_1,y_2,\ldots,y_{d-1},y_d\}$ to have size $d$ or more, it means $y_d=y_j$ if $y_j\in I$. So, $y_j$ is like a “double root” and hence $\frac{d\left(P-c^\prime\right)}{dx}\left(y_j\right)=\frac{dP}{dx}\left(y_j\right)=0$. Note that we get such an element in all $d-1$ tuples $(y_1,y_2,\ldots,y_{d-1})$. So, we get the $d-1$ roots to the equation $\frac{dP}{dx}=0$. Let $z_1<z_2<\ldots<z_{d-1}$ be the $d-1$ roots to the equation $\frac{dP}{dx}=0$. Note that \[x_1<z_1<x_2<z_2<\cdots<z_{d-1}<x_d\]Since every set of $d-1$ fixed sets give one root $z_i$, it means that $P\left(z_1\right)\neq P\left(z_2\right)\neq\cdots\neq P\left(z_{d-1}\right)$. Let $P\left(z_t\right)=\min{\{}P\left(z_1\right),P\left(z_2\right),\ldots,P\left(z_{d-1}\right)\}$. So, $z_t$ is the local minima which swoops down the lowest in range $\left(x_1,x_d\right)$. Hence, all solutions to $P\left(x\right)=P\left(z_t\right)$ lie in $\left[0,x_1\right)$ and/or $\left(x_d,d^2-d\right]$, which is a clear contradiction to the established fact that there must be at least two roots in each of the non-boundary intervals except for the one interval with $z_t$ in it. The proof is complete. $\blacksquare$

The construction for $d=3$ (I'm told naming this, along with $d=1,2$, as the correct answer was worth a point! I also did not realize this was true until it was strongly suggested by a friend) appears in AIME I 2015/10 Also I do not believe there are any correct solutions on this thread yet

IAmTheHazard wrote: The construction for $d=3$ (I'm told naming this, along with $d=1,2$, as the correct answer was worth a point! I also did not realize this was true until it was strongly suggested by a friend) appears in AIME I 2015/10 Also I do not believe there are any correct solutions on this thread yet I am also pretty sure all solutions here are wrong.

Sorry this is wrong

internationalnick123456 wrote: Note that no $y_i,y_j$ belong to the same interval, Wrong.

Please remove posts #3-#14 as they are irrelevant. This was the hardest write-up I had to write on aops, ever. I believe I have left some vague details as a result. Answer: $d=1, 2$, and $3$. The constructions $P(x)=x$, $P(x)=x(x-1)$, and $P(x)=(x-1)(x-2)(x-6)$ work for $d=1, 2$, and $3$ respectively. Bound: We show that $d \leq 6$ with the $d=4, 5, 6$ cases being left to the reader. (Solved on the post below.) Since the derivative of $P$ is a $d-1$ degree polynomial, we may dissect the interval $(0, d^2-d)$ into $d$ strictly monotonic intervals $(0, x_1), (x_1, x_2), \dots, (x_{d-1}, d^2-d)$. For the sake of brevity, let $x_0=0$ and $x_d=d^2-d$. Note that for each $x, y$ in the same interval, we must have $P(x) \neq P(y)$ which implies that each interval must contain at most $d$ integers. Claim 1: There are at most two intervals among $(x_0, x_1), (x_1, x_2), \dots, (x_{d-1}, d^2-d)$ which contain at least $d$ integers. Suppose for contradiction that there exist $3$ intervals containing at least $d$ integers. By the pigeonhole principle there are two intervals $(x_i, x_{i+1}), (x_j, x_{j+1})$ containing no less than $d$ integers that are both either monotonically increasing or monotonically decreasing. By symmetry, we may assume that they are both monotonically increasing. Let $a+1$ and $b+1$ be the smallest integers in the intervals $(x_i, x_{i+1})$ and $(x_j, x_{j+1})$ respectively. Since $P(a+1)<P(a+2)< \dots < P(a+d)$, $P(b+1) < P(b+2) < \dots < P(b+d)$ and among these there are at most $d$ distinct numbers, we may conclude that $P(a+i) = P(b+i)$ for all $1 \leq i \leq d$. Now consider the $d-1$ degree polynomial $P(x)-P(x+b-a)$. Observe that for each $1 \leq i \leq d$, $a+i$ is a root of this polynomial. Hence, it must be the zero polynomial. In other words, we must have $P(x)=P(x+b-a)$ for all $x \in \mathbb{R}$. It is easy to conclude that $P$ must be linear in this case. $\square$ Claim 2: There can't be exactly two intervals among $(x_0, x_1), (x_1, x_2), \dots, (x_{d-1}, x_d)$ that contains at least $d$ integers. Suppose for contradiction that we can have two intervals $(x_i, x_{i+1})$ and $(x_j, x_{j+1})$ containing at least $d$ integers. Recall that, in Claim 1, we have shown that the intervals $(x_i, x_{i+1})$ and $(x_j, x_{j+1})$ must have opposite monotonicity. By symmetry, we may assume that $x_i < x_j$ and that the interval $(x_i, x_{i+1})$ is increasing. Let $a-1$ be the largest integer in $(x_i, x_{i+1})$ and let $b+1$ be the smallest integer in $(x_j, x_{j+1})$. Then we have $P(a-1) > P(a-2) > \dots > P(a-d)$ and $P(b+1) > P(b+2) > \dots > P(b+d)$. Since there are at most $d$ district numbers among these, we may conclude that $P(a-i)=P(b+i)$ for all $1 \leq i \leq d$. Consider the polynomial $P(x)-P(a+b-x)$. Observe that for each $1 \leq i \leq d$, the numbers $a-1$ and $b+1$ have to be roots of this polynomial. This implies that the polynomial $P(x)-P(a+b-x)$ is the zero polynomial. In other words, $P(x)=P(a+b-x)$ for all $x \in \mathbb{R}$. Therefore, $P$ is even about $\frac{a+b}{2}$. Now, notice that all of our intervals besides $(x_i, x_{i+1})$ and $(x_j, x_{j+1})$ combined must contain exactly $d^2-3d+1$ integers. Since each of these intervals contain no more than $d-1$ integers, we conclude that either: There are $d-3$ intervals which contain $d-1$ integers and $1$ interval which contains $d-2$ integers. There are $d-2$ intervals which contain $d-1$ integers and in particular, a single pair of intervals $(x_i, x_{i+1}), (x_{i+1}, x_{i+2})$ such that $x_{i+1}$ is an integer. In other words, they share an integer. We show that none of these can be true. If there is a single interval with $d-2$ integers, the interval we get when reflecting about $\frac{a+b}{2}$, must also have $d-2$ integers. This contradicts the uniqueness of the $d-2$ integer interval. On the other hand, if there is a single pair of intervals $(x_i, x_{i+1}), (x_{i+1}, x_{i+2})$ such that $x_{i+1}$ is an integer, we get contradiction in the same fashion. $\square$ By the pigeonhole principle, there is an interval $(x_i, x_{i+1})$ among $(x_0, x_1), (x_1, x_2), \dots, (x_{d-1}, x_d)$ that contains at least $d$ integers. Since any interval cannot contain more than $d$ integers, $(x_i,x_{i+1})$ must contain exactly $d$ integers. Let $a_1 < a_2 < \dots < a_d$ be our possible values. Then the rest of the intervals conbined must contain exactly $d^2-d+1$ integers. Since each interval alone must contain at most $d-1$ integers, we conclude that each interval among $(x_0, x_1), (x_1, x_2), \dots, (x_{d-1}, x_d)$ besides $(x_i, x_{i+1})$ must contain exactly $d-1$ integers. This also implies that none of the numbers $x_1, x_2, \dots, x_{d-1}$ are integers. Consider pairs of intervals such that $(x_k, x_{k+1})$ and $(x_{k+2}, x_{k+3})$. I claim that if $x, y \in \mathbb{Z}$ satisfy $x \in (x_{k+2}, x_{k+3})$, $y \in (x_k, x_{k+1})$ and $P(x)=P(y)$, we must have $x-y \in \{2d-3, 2d-2, 2d-1\}$ unless $k=i-1$. I suggest you draw a graph and visualize what this might look like. By symmetry we may assume that the intervals $(x_k, x_{k+1})$ and $(x_{k+2}, x_{k+3})$ are monotonically increasing. Let $P(x)=P(y)=a_n$. Since $(x_k, x_{k+1})$ contains at least $d-1$ integers, there can be only one $a_p$ such that there doesn't exist an integer $q$ in $(x_k, x_{k+1})$ satisfying $P(q)=a_p$. And since for each $n < m$, if there exists an $s$ such that $P(s)=a_m$ in $(x_k, x_{k+1})$ we have $x<s$, there must be at least $d-n$ integers in the interval $(y, x_{k+1})$. For the same reason, there must be at least $n-1$ integers in the interval $(x_{k}, y)$. Hence, there are either $d-n$ or $d-n+1$ integers in the interval $(y, x_{k+1})$. Similarly, there are either $n-1$ or $n$ integers in the interval $(x_{k+2}, x)$. Combined with the fact that there are exactly $d-1$ integers in the interval $(x_{k+1}, x_{k+2})$, we conclude that $x-y \in \{2d-3, 2d-2, 2d-1\}$. $\square$ Since the intervals $(x_k, x_{k+1})$ and $(x_{k+2}, x_{k+3})$ contain at least $d-1$ integers each and for each one of these integers $x$ the value of $P(x)$ has $d$ different options, there must exist at least $d-2$ different pairs $(x, y)$ such that $P(x)=P(y)$ and $x \in (x_{k+2}, x_{k+3})$, $y \in (x_k, x_{k+1})$. There are at least $d-3$ pairs of intervals $(x_k, x_{k+1})$ and $(x_{k+2}, x_{k+3})$ such that $k \neq i-1$. Hence, there are at least $(d-2)(d-3)$ different pairs $x, y$ satisfying our condition. By PHP, there are at least $\frac{(d-2)(d-3)}{3}$ distinct pairs $(x, y)$ such that the value of $(x-y)=a$ is the same. If $d>6$, we have $\frac{(d-2)(d-3)}{3}>d-1$ which implies that the polynomial $P(x)-P(x+a)$ is the zero polynomial similarly as in Claim 1. Hence, $P$ is linear. $\blacksquare$ Thank you @below!

I have the same proof, but your last inequality doesn't work for $d=6$. I had written an almost complete fix, but inadvertently erased it, so here I go again. You have to take into account the special interval $(x_i, x_{i+1})$. Remark 1 : When $k=i$ or $k+2=i$, you get $d-1$ solutions instead of $d-2$. Remark 2 : Look at the last integer of $(x_{i+1}, x_{i+2})$, it must have the same value as the first or second of $(x_i, x_{i+1})$, and their difference is $2d-3$ or $2d-2$. Same thing in the other direction (on the left instead of the right). You look at all possible scenarios for where the "special interval" is. When it is on the boundaries, we get $d-2$ "admissible" pairs of intervals instead of $d-3$, which gives us $(d-2)^2 + 2$ equations, using the remarks above for 2 extra equations. This is enough to rule out $d=6$. When $1<i<d-1$ (so the special interval is "in the middle"), we get $(d-2)(d-3)+4$ with the 4 extra equations from above, which is again enough for the PHP. Now if $i=1$ ($i=d-1$ is symmetric), we only have $(d-2)(d-3)+3$ equations so far. Remark 3: If we look at the first integer $f$ of $(x_{i+3}, x_{i+4})$, it must have the same value as the last or penultimate of $(x_i, x_{i+1})$. The difference is either $2d-1$, and we have our extra equation, or it is $2d$, and in that case, assuming by symmetry that $P$ is decreasing on $(x_i, x_{i+1})$, we have $P(f)= a_2$, and the values on $(x_{i+3}, x_{i+4})$ must be $a_2<a_3 \cdots< a_d$. Let us now examine the sandwich situation $k=i-1$. The distances between "matching" integers are $2d-2, 2d-1, 2d$. So either we do get an extra useful equation from the case $k=i-1$, or all matching integers differ by $2d$. This can only happen if the values on $(x_{i-1}, x_{i+1})$ are $a_2<a_3 \cdots< a_d$, and those on $(x_{i+1}, x_{i+2})$ are $a_1<a_2 \cdots< a_{d-1}$. Combining the latter fact with the values on $(x_{i+3}, x_{i+4})$ , we get $d-2$ matching values at distance $2d-3$. In the situation at hand, remark 2 actually gives two other values at distance $2d-3$, therefore we get $d$ matching values at distance $2d-3$, therefore a polynomial of degree $d-1$ with $d$ roots, QED. To solve for $d=4$ or $d=5$, it seems that you need to get into the details of when the distance between matching values is $2d-3$, $2d-2$ or $2d-1$, similarly to what we've just done in the last case. It won't work to count all matching values for all three distances (only two distances should be involved at the same time).

There was a contestant who had (from what I heard) a reasonably quick clever solution with Vieta's formulae, can anyone maybe show something like this here?