56th International Mathematical Olympiad Shortlisted Problems

For convenience, we set $k=2015=2\ell +1$.

a. Consider the following polynomials of degree $n+1$ : $$P(x)=\prod _{i=0}^n(x-ik)\text{ and }Q(x)=\prod _{i=0}^n(x-ik-1).$$ Since $Q(x)=P(x-1)$ and $P(0)=P(k)=P(2k)=\cdots =P(nk)$, these polynomials are block-similar (and distinct).

b. For every polynomial $F(x)$ and every nonnegative integer $m$, define ${\Sigma }_F(m)={\sum }_{i=1}^{m}F(i)$; in particular, ${\Sigma }_F(0)=0$. It is well-known that for every nonnegative integer $d$ the sum ${\sum }_{i=1}^m{i}^d$ is a polynomial in $m$ of degree $d+1$. Thus ${\Sigma }_F$ may also be regarded as a real polynomial of degree $\mathrm{deg}F+1$ (with the exception that if $F=0$, then ${\Sigma }_F=0$ as well). This allows us to consider the values of ${\Sigma }_F$ at all real points (where the initial definition does not apply).

Assume for the sake of contradiction that there exist two distinct block-similar polynomials $P(x)$ and $Q(x)$ of degree $n$. Then both polynomials ${\Sigma }_{P-Q}(x)$ and ${\Sigma }_{P^2-Q^2}(x)$ have roots at the points $0,k,2k,\dots ,nk$. This motivates the following lemma, where we use the special polynomial $$T(x)=\prod _{i=0}^n(x-ik)$$

Lemma. Assume that $F(x)$ is a nonzero polynomial such that $0,k,2k,\dots ,nk$ are among the roots of the polynomial ${\Sigma }_F(x)$. Then $\mathrm{deg}F⩾n$, and there exists a polynomial $G(x)$ such that $\mathrm{deg}G=\mathrm{deg}F-n$ and $F(x)=T(x)G(x)-T(x-1)G(x-1)$.

Proof. If $\mathrm{deg}F<n$, then ${\Sigma }_F(x)$ has at least $n+1$ roots, while its degree is less than $n+1$. Therefore, ${\Sigma }_F(x)=0$ and hence $F(x)=0$, which is impossible. Thus $\mathrm{deg}F⩾n$.

The lemma condition yields that ${\Sigma }_F(x)=T(x)G(x)$ for some polynomial $G(x)$ such that $\mathrm{deg}G=\mathrm{deg}{\Sigma }_F-(n+1)=\mathrm{deg}F-n$.

Now, let us define $F_1(x)=T(x)G(x)-T(x-1)G(x-1)$. Then for every positive integer $n$ we have $${\Sigma }_{F_1}(n)=\sum _{i=1}^n(T(x)G(x)-T(x-1)G(x-1))=T(n)G(n)-T(0)G(0)=T(n)G(n)={\Sigma }_F(n)$$ so the polynomial ${\Sigma }_{F-F_1}(x)={\Sigma }_F(x)-{\Sigma }_{F_1}(x)$ has infinitely many roots. This means that this polynomial is zero, which in turn yields $F(x)=F_1(x)$, as required.

First, we apply the lemma to the nonzero polynomial $R_1(x)=P(x)-Q(x)$. Since the degree of $R_1(x)$ is at most $n$, we conclude that it is exactly $n$. Moreover, $R_1(x)=\alpha \cdot (T(x)-T(x-1))$ for some nonzero constant $\alpha$.

Our next aim is to prove that the polynomial $S(x)=P(x)+Q(x)$ is constant. Assume the contrary. Then, notice that the polynomial $R_2(x)=P(x{)}^2-Q(x{)}^2=R_1(x)S(x)$ is also nonzero and satisfies the lemma condition. Since $n<\mathrm{deg}{R}_1+\mathrm{deg}S=\mathrm{deg}{R}_2⩽2n$, the lemma yields $$R_2(x)=T(x)G(x)-T(x-1)G(x-1)$$ with some polynomial $G(x)$ with $0<\mathrm{deg}G⩽n$.

Since the polynomial $R_1(x)=\alpha (T(x)-T(x-1))$ divides the polynomial $$R_2(x)=T(x)(G(x)-G(x-1))+G(x-1)(T(x)-T(x-1)),$$ we get $R_1(x)\mid T(x)(G(x)-G(x-1))$. On the other hand, $$\gcd \left(T(x),R_1(x)\right)=\gcd (T(x),T(x)-T(x-1))=\gcd (T(x),T(x-1))=1$$ since both $T(x)$ and $T(x-1)$ are the products of linear polynomials, and their roots are distinct. Thus $R_1(x)\mid G(x)-G(x-1)$. However, this is impossible since $G(x)-G(x-1)$ is a nonzero polynomial of degree less than $n=\mathrm{deg}{R}_1$.

Thus, our assumption is wrong, and $S(x)$ is a constant polynomial, say $S(x)=\beta$. Notice that the polynomials $(2P(x)-\beta )/\alpha$ and $(2Q(x)-\beta )/\alpha$ are also block-similar and distinct. So we may replace the initial polynomials by these ones, thus obtaining two block-similar polynomials $P(x)$ and $Q(x)$ with $P(x)=-Q(x)=T(x)-T(x-1)$. It remains to show that this is impossible.

For every $i=1,2\dots ,n$, the values $T(ik-k+1)$ and $T(ik-1)$ have the same sign. This means that the values $P(ik-k+1)=T(ik-k+1)$ and $P(ik)=-T(ik-1)$ have opposite signs, so $P(x)$ has a root in each of the $n$ segments $[ik-k+1,ik]$. Since $\mathrm{deg}P=n$, it must have exactly one root in each of them.

Thus, the sequence $P(1),P(2),\dots ,P(k)$ should change sign exactly once. On the other hand, since $P(x)$ and $-P(x)$ are block-similar, this sequence must have as many positive terms as negative ones. Since $k=2\ell +1$ is odd, this shows that the middle term of the sequence above must be zero, so $P(\ell +1)=0$, or $T(\ell +1)=T(\ell )$. However, this is not true since $$|T(\ell +1)|=|\ell +1|\cdot |\ell |\cdot \prod _{i=2}^n|\ell +1-ik|<|\ell |\cdot |\ell +1|\cdot \prod _{i=2}^n|\ell -ik|=|T(\ell )|,$$ where the strict inequality holds because $n⩾2$. We come to the final contradiction.

---

Alternative solution.

We provide an alternative argument for part (b).

Assume again that there exist two distinct block-similar polynomials $P(x)$ and $Q(x)$ of degree $n$. Let $R(x)=P(x)-Q(x)$ and $S(x)=P(x)+Q(x)$. For brevity, we also denote the segment $[(i-1)k+1,ik]$ by $I_i$, and the set $\{(i-1)k+1,(i-1)k+2,\dots ,ik\}$ of all integer points in $I_i$ by $Z_i$.

Step 1. We prove that $R(x)$ has exactly one root in each segment $I_i,i=1,2,\dots ,n$, and all these roots are simple.

Indeed, take any $i\in \{1,2,\dots ,n\}$ and choose some points $p^{-},p^{+}\in Z_i$ so that $$P\left(p^{-}\right)=\underset{x\in Z_i}{\min }P(x)\text{ and }P\left(p^{+}\right)=\underset{x\in Z_i}{\max }P(x)$$ Since the sequences of values of $P$ and $Q$ in $Z_i$ are permutations of each other, we have $R\left(p^{-}\right)=P\left(p^{-}\right)-Q\left(p^{-}\right)⩽0$ and $R\left(p^{+}\right)=P\left(p^{+}\right)-Q\left(p^{+}\right)⩾0$. Since $R(x)$ is continuous, there exists at least one root of $R(x)$ between $p^{-}$ and $p^{+}$ - thus in $I_i$.

So, $R(x)$ has at least one root in each of the $n$ disjoint segments $I_i$ with $i=1,2,\dots ,n$. Since $R(x)$ is nonzero and its degree does not exceed $n$, it should have exactly one root in each of these segments, and all these roots are simple, as required.

Step 2. We prove that $S(x)$ is constant.

We start with the following claim.

Claim. For every $i=1,2,\dots ,n$, the sequence of values $S((i-1)k+1),S((i-1)k+2),\dots$, $S(ik)$ cannot be strictly increasing.

Proof. Fix any $i\in \{1,2,\dots ,n\}$. Due to the symmetry, we may assume that $P(ik)⩽Q(ik)$. Choose now $p^{-}$ and $p^{+}$ as in Step 1. If we had $P\left(p^{+}\right)=P\left(p^{-}\right)$, then $P$ would be constant on $Z_i$, so all the elements of $Z_i$ would be the roots of $R(x)$, which is not the case. In particular, we have $p^{+}\ne p^{-}$. If $p^{-}>p^{+}$, then $S\left(p^{-}\right)=P\left(p^{-}\right)+Q\left(p^{-}\right)⩽Q\left(p^{+}\right)+P\left(p^{+}\right)=S\left(p^{+}\right)$, so our claim holds.

We now show that the remaining case $p^{-}<p^{+}$ is impossible. Assume first that $P\left(p^{+}\right)>Q\left(p^{+}\right)$. Then, like in Step 1, we have $R\left(p^{-}\right)⩽0,R\left(p^{+}\right)>0$, and $R(ik)⩽0$, so $R(x)$ has a root in each of the intervals $\left[p^{-},p^{+}\right)$ and $\left(p^{+},ik\right]$. This contradicts the result of Step 1.

We are left only with the case $p^{-}<p^{+}$ and $P\left(p^{+}\right)=Q\left(p^{+}\right)$ (thus $p^{+}$ is the unique root of $R(x)$ in $I_i$ ). If $p^{+}=ik$, then the values of $R(x)$ on $Z_i\backslash \{ik\}$ are all of the same sign, which is absurd since their sum is zero. Finally, if $p^{-}<p^{+}<ik$, then $R\left(p^{-}\right)$ and $R(ik)$ are both negative. This means that $R(x)$ should have an even number of roots in $\left[p^{-},ik\right]$, counted with multiplicity. This also contradicts the result of Step 1.

In a similar way, one may prove that for every $i=1,2,\dots ,n$, the sequence $S((i-1)k+1)$, $S((i-1)k+2),\dots ,S(ik)$ cannot be strictly decreasing. This means that the polynomial $\Delta S(x)=S(x)-S(x-1)$ attains at least one nonnegative value, as well as at least one nonpositive value, on the set $Z_i$ (and even on $Z_i\backslash \{(i-1)k+1\}$ ); so $\Delta S$ has a root in $I_i$.

Thus $\Delta S$ has at least $n$ roots; however, its degree is less than $n$, so $\Delta S$ should be identically zero. This shows that $S(x)$ is a constant, say $S(x)\equiv \beta$.

Step 3. Notice that the polynomials $P(x)-\beta /2$ and $Q(x)-\beta /2$ are also block-similar and distinct. So we may replace the initial polynomials by these ones, thus reaching $P(x)=-Q(x)$.

Then $R(x)=2P(x)$, so $P(x)$ has exactly one root in each of the segments $I_i,i=1,2,\dots ,n$. On the other hand, $P(x)$ and $-P(x)$ should attain the same number of positive values on $Z_i$. Since $k$ is odd, this means that $Z_i$ contains exactly one root of $P(x)$; moreover, this root should be at the center of $Z_i$, because $P(x)$ has the same number of positive and negative values on $Z_i$.

Thus we have found all $n$ roots of $P(x)$, so $$P(x)=c\prod _{i=1}^n(x-ik+\ell )\text{ for some }c\in \mathbb{R}\backslash \{0\}$$ where $\ell =(k-1)/2$. It remains to notice that for every $t\in Z_1\backslash \{1\}$ we have $$|P(t)|=|c|\cdot |t-\ell -1|\cdot \prod _{i=2}^n|t-ik+\ell |<|c|\cdot \ell \cdot \prod _{i=2}^n|1-ik+\ell |=|P(1)|$$ so $P(1)\ne -P(t)$ for all $t\in Z_1$. This shows that $P(x)$ is not block-similar to $-P(x)$. The final contradiction.