Proposed by the boss of math David Arthur of Canada

For part (a) we can take $P(x) = x(x-2015)(x-4030) \cdots (x-2015n)$ and $Q(x) = P(x-1)$.

MathPanda1 wrote: Proposed by the boss of math David Arthur of Canada There are many on this forum who deserve that title more than me, but thanks! This problem is too difficult even for the IMO I think, but it was nice enough that I wanted to share it with others and I didn't know where else to send it. FYI for anyone who does try it, the result is still true if 2015 is replaced with any integer k >= 3. The argument is similar but even integers require some extra work at the end. PS: I think I know who you are from the IMO results thread. Congrats on a terrific score!

Is it possible to write us some words about how did you come up with this nice problem?

Crazy problem

silouan wrote: Is it possible to write us some words about how did you come up with this nice problem? I was on the jury of IMO 2014 and rightly or wrongly I came away feeling that algebra was stuck as a subject. That year, there were a couple easy ad hoc recurrence problems, an algorithms problem that seemed a stretch to call algebra, and three functional equations. There were no traditional inequalities, likely because the jury has given up on the subject due to all the powerful technology that has been developed around it, and the jury was also very clearly tired of standard functional equations. So I just tried to see if I could come up with something challenging in algebra that felt different. I'm a combinatorics guy at heart, and so I started with the idea of what can you figure out if you are given the set of values a function or polynomial takes on. I then tried variations of that until I found a statement I could prove . Not that exciting a story I'm afraid!

.

Let me write a solution to this problem. This problem was given at my country's TST camp two times. First without any hint, during which no one solved it, then with the exact same hint as in @darthur's post. This is the solution I gave during the second time.

Here's a solution that uses similar ideas but has different execution (kind of in reverse).

what is R'?

For the first class of MOP 2020, I worked on this problem together with the winners of USAMO 2020 and the IMO team, and the instructor pythag011. Here was the solution we came up with, typeset by me (so any errors are my fault!): We will replace $2015$ by an odd integer $\ell > 1$ for convenience. For part (a), a suitable example is to take \[ P(x) = x(x-\ell)(x-2\ell) \dots(x-(n-1)\ell) \]and $Q(x) = P(x-1)$. For part (b), assume the contrary that $P \neq Q$ are block-similar with degree $n$. We refer to each of the intervals $[1, \ell]$, $[\ell+1, 2\ell]$ as blocks. Claim: For every block $B$ there exists exactly one $t \in B$ in the block with $P(t)=Q(t)$. Proof. By hypothesis, there should be integers $x \ne x' \in B$ such that $P(x) \le Q(x)$ and $P(x') \ge Q(x')$. This shows every block has at least one $t$. Thus across the $n$ blocks, we have $n$ points $t$ already where $P(t) = Q(t)$. There can't be any more, since $\deg P = \deg Q = n$. $\blacksquare$ Now let $R = P+Q$. Claim: For every block $B$ there exists $s \in B$ such that $R'(s) = 0$. Proof. Let $x_1 < \dots < x_{\ell}$ be the integers in $B \cap {\mathbb Z}$, and consider the multiset of values $\{P(x_i)\}$ (equivalently $\{Q(x_i)\}$). We let $m$ and $M$ denote the minimum and maximum of this set. Also, let $t$ be as in the previous claim. [asy][asy] size(10cm); draw( (-1,0)--(8,0), Arrows(TeXHead)); draw( (0,-1)--(0,5), Arrows(TeXHead)); draw( (1,0)--(1,4.7), deepgreen ); draw( (7,0)--(7,4.7), deepgreen ); label("$B$", (4, -0.5), dir(-90), deepgreen); path p = (1,2.0)..(2,3.5)..(3,4.0)..(4,3.7)..(5,2.5)..(6,1.0)..(7,1.3); path q = (1,1.3)..(2,1.0)..(3,2.0)..(4,2.5)..(5,3.5)..(6,3.7)..(7,4.0); draw(p, red); draw(q, blue); pair X = intersectionpoint(p,q); dot("$t$", X, dir(90)); draw(X..(X.x,0), dashed); label("$m$", point(q,1), dir(-45), deepgreen); label("$m$", point(p,5), dir(225), deepgreen); label("$M$", point(q,6), dir(135), deepgreen); label("$M$", point(p,2), dir(90), deepgreen); label("$P$", (1.5,3), dir(90), red); label("$Q$", (1.5,1), dir(-90), blue); draw(point(q,1)--point(p,5), deepgreen); draw(point(q,6)--point(p,2), deepgreen); for (int i=0; i<7; ++i) { if (i*(i-7) != 0) { draw((i+1, max(point(p,i).y, point(q,i).y))..(i+1,0), dotted); } dot(point(p, i), red); dot(point(q, i), blue); } dot("$x_1$", (1,0), dir(-90), deepgreen); dot("$x_2$", (2,0), dir(-90), deepgreen); dot("$x_3$", (3,0), dir(-90), deepgreen); dot("$\cdots$", (5,0), dir(-90), deepgreen); dot((4,0), deepgreen); dot((6,0), deepgreen); dot("$x_\ell$", (7,0), dir(-90), deepgreen); [/asy][/asy] Let's assume that $P > Q$ before $t$ and $P < Q$ after $t$, say. Then, there should be $x_i \le t \le x_j$ with $i \ne j$ such that $P(x_i) = M$ and $P(x_j) = m$. Hence $R(x_i) \ge R(x_j)$ for this $i$ and $j$. Hence $R'$ is nonpositive at some point in the block. Similarly, there should exist $x_{i'} \le t \le x_{j'}$ with $i' \ne j'$ such that $Q(x_i) = M$ and $Q(x_j) = m$, and here $R(x_{i'}) \le R(x_{j'})$. Hence $R'$ is nonnegative at some point in the block. So $R'$ is zero at some point in the block. $\blacksquare$ However, since $R$ has degree at most $n$, we see $R'$ has degree at most $n-1$; so $R'$ must actually be identically zero (since we have found $n$ roots), and thus $R$ is a constant. By shifting then, we may assume $R = 0$, and so $P = -Q$. By scaling, assume $P$ is monic. Well, since $\ell$ is odd, $P = -Q$ should have an integer root in each block. In other words we may as well assume \[ P(x) = (x-t_1)(x-t_2) \dots (x-t_n) \]with $t_i$ in the $i$'th block, and similarly for $Q$. Actually, by counting the number of positive/negative/zero numbers, we find that $t_i$ should be the center of each block. But now $P(\ell n)$ is the largest positive number in the last block, exceeding $Q(x)$ for any $x$. This produces the desired contradiction.

Part a Let $P(x)=\prod_{i=0}^n (x-2015i)$. Then, $P(x)$ and $P(x-1)$ satisfy the given properties. Part b Assume toward a contradiction that such polynomials $P$ and $Q$ exist. Note that $Q(x)-P(x)$ has at least one root in each interval $(2015(i-1)+1, 2015i)$ for $1\le i\le n$. Since $Q(x)-P(x)$ has degree at most $n$, it has exactly one root (counting multiplicity) in each of these intervals and no other roots. In particular, $2015(i-1)+1$ and $2015i$ aren't roots. Claim: Each interval $(2015(i-1), 2015i)$ has a root of $Q(x+1)=P(x)$. Proof: Assume toward a contradiction this is false. Let $x_1\le x_2\le\dots\le x_{2015}$ be the elements of $\{P(2015(i-1)+1), P(2015(i-1)+2),\dots,P(2015i)\}$. Then, WLOG $Q(x+1)>P(x)$ for all $x$ in the interval. So, $Q(x)\neq x_1$ for all $2015(i-1)+1<x\le 2015i$, so $Q(2015(i-1)+1)=x_1$. By similar logic, $P(2015i)=x_{2015}$. However, this implies $P(2015(i-1)+1)\ge Q(2015(i-1)+1)$ and $P(2015i)\ge Q(2015i)$. Thus, $P(2015(i-1)+1)> Q(2015(i-1)+1)$ and $P(2015i)> Q(2015i)$, which is impossible. Because $Q(x)-P(x)$ has $n$ roots, $Q(x)$ and $P(x)$ have different leading terms. Thus, $Q(x+1)\not\equiv P(x)$. Because $Q(x+1)=P(x)$ has degree at most $n$, it must have exactly one root in each of the intervals. Similar logic applies to $Q(x)=P(x+1)$. Let $0\le i\le n$. Without loss of generality, for even $i$, $P(2015i)<Q(2015i)$ and for odd $i$, $P(2015i)>Q(2015i)$. Claim: For odd $0< i< n$, $P$ has a local maximum between $2015(i-1)$ and $2015(i+1)$. For even $0<i<n$, $P$ has a local minimum between $2015(i-1)$ and $2015(i+1)$. The same statement holds for $Q$ if we switch ``maximum'' and ``minimum''. Proof: We have $P(2015i)>Q(2015i)$. We know $P$ must attain the value $Q(2015i)$ in each of the intervals $(2015(i-1), 2015i)$ and $(2015i, 2015(i+1))$. Thus, somewhere between those $2$ points where $P(x)=Q(2015i)$, $P$ has a local maximum. By similar logic, for even $0<i<n$, $P$ has a local minimum between $2015(i-1)$ and $2015(i+1)$. Because $P$ and $Q$ are degree $n$, these are the only local extrema. All of the inflection points must be in the spaces between the extrema. Claim: $P(2015)>P(1)$. Proof: Assume toward a contradiction this is false. Since $P$ has no local minimum in this range, $P(2015)$ is the minimum value of $P(k)$ for integers $0<k\le 2015$. However, $Q(2015)<P(2015)$, a contradiction. Let $x_1\le x_2\le\dots\le x_{2015}$ be the values in $P(1),\dots,P(2015)$. Let $0<p\le 2015$ be the point where $P(x)$ is highest in the interval $(0, 2015]$. Note $P$ is concave on $(0, p]$ and $P$ is increasing on $(0, p)$ and decreasing on $(p, 2015)$. Assume $x_{2015}=P(k)$ for some integer $1\le k\le 2015$. Then, $k=\lfloor p\rfloor$ or $k=\lceil p\rceil$. Thus, \[x_{2015}-x_{2014}\le \max(P(\lceil p\rceil)-P(\lceil p\rceil-1), P(\lfloor p\rfloor)-P(\lfloor p\rfloor-1))\le \max(P(p)-P(p-1), P(\lfloor p\rfloor)-P(\lfloor p\rfloor-1)).\]By concavity this is less than $P(2)-P(1)$. Note $P(1)=x_1$. Either $P(2)=x_2$ or $P(2015)=x_2$. If $P(2)=x_2$, then $x_2-x_1>x_{2015}-x_{2014}$. If $Q(2)=x_{2014}$, we have $x_2-x_1<x_{2015}-x_{2014}$ by similar logic. Therefore, either $P(2015)=x_2$ or $Q(2015)=x_{2014}$. WLOG assume $P(2015)=x_2$. Then, $Q(2015)<x_2$, so $Q(2015)=x_1$. Since $Q$ has no local minima in $(0, 2015)$, $Q$ is decreasing and convex in this range. So, $x_2-x_1<x_3-x_2<\dots<x_{2015}-x_{2014}$. Consider the sequence $a_1,\dots, a_n$ such that $P(i)=x_{a_i}$ for $1,\dots, n$ and $P(n)=x_{2015}$. Then, we have $a_2-a_1>a_3-a_2>\dots > a_n-a_{n-1}$. In a decreasing sequence of positive integers that adds to $2014$, the first term must be at least $31$. Thus, $P(1)=x_1$ and $P(2)>x_{31}$. So, $P(2015)=x_2=Q(2014)$ and $P(2014)=x_3=Q(2013)$. So, $Q(x)=P(x+1)$ has 2 roots in $(0, 2015)$, which contradicts the earlier claim.