Same idea as this

$0$ is $P-representable$.

My problem a bit surprising to see it making the Iberoamerican (I considered it myself too technical to the contest). There are some interesting variants, for example finding all P such that every integer is P-representable. I might (or not :p) come back here eventually to talk more about the problem and post my rather lengthy solution.

bruckner wrote: My problem a bit surprising to see it making the Iberoamerican (I considered it myself too technical to the contest). On the contrary, I think it was an amazing P6! Congrats, personally I found it the best problem by far in this year's exam! Overall an unusually good year for Olympiad algebra (with this problem and the beautiful IMO P3).

For contestants who haven't seen this density/counting idea, this is a beautiful problem! For those who have, this is a boring problem. For those who have studied solutions to IZHO 22/5 in depth, this is free marks.

CANBANKAN wrote: For contestants who haven't seen this density/counting idea, this is a beautiful problem! For those who have, this is a boring problem. For those who have studied solutions to IZHO 22/5 in depth, this is free marks. For me this problem is way more difficult to formalize than the IZHO 22/5 that you mentioned. Both have a density idea but they are substantially different, this one is longer, more tedious, and way more technical, so not solving the Ibero p6 but solving the IZHO 22/5 is definitely a possibility. If you really think they are both the same I encourage you to try and write up a full solution worth 7 points. My friends and I will make sure to point out the flaws in your solution.

Ok I think I see my flaw. IZHO 22/5 only allows such $a,b$ to be positive while here my argument may fail if one of them is positive and one of them is negative (say $P(x)=x^4+x$) But by IZHO 22/5 again, the most of the analysis of the problem comes from this. One can show the positive one + negative one is bounded, and we just need to consider a polynomial $Q(x)=P(x)-P(-x+c)$ or something. A sketch would to be show that there is only one $c$ that gives $O(N)$ terms and the others collectively give $o(N)$. Then it should still not be hard…….: I will writeup a full solution tonight.

Tell me if this has any flaws. The key claim is that there exists a constant $c$ such that $P(x) - P(c-x)$ is linear. Proof: Assume not. WLOG $P$ has positive leading coefficient. Fix a sufficiently large $N$. Note there exists at most one $c$ such that $P(x)-P(c-x)$ is linear; for all but one $c$, the degree of that polynomial is at least 3. Let $S_c$ be the number of integers in $\{1,\cdots,N\}$ representable as $P(x)-P(c-x)$. We will show that $$\sum_{c\colon P(x)-P(c-x) \text{ have degree 0 or at least 2}} S_c = o(N)$$, which proves our claim. We will handle the "special" $c$ (the $c$ such that $\deg P(x)-P(c-x) < 3$) separately. Note $c$ is bounded, and $N$ can be arbitrarily large) Note for $|c|<N^{1/2}$, $S_c = O(N^{1/3})$, while for $c>N^{1/2}$ we consider $y=x+c/2$ and consider $T(y)=P(c/2+y) - P(c/2-y)$ when $y>0$; this is always nonnegative (can show this has all positive coefficients). The behavior of $P$ is monotone when $y>c/10$, and we can check $T(y)$ is increasing, so $T(y)>T(1)=P(c/2+1)-P(c/2-1) \approx c^{\deg P-1} >> N$. The case where $c<-N^{1/2}$ can be handled similarly. Therefore, the non-special $c$ contribute to $o(N)$ representable terms. Thus, for the special $c$ to contribute to $(1/2-o(1))N$ representable terms, $P(x)-P(c-x)$ must be linear; furthermore, since it has integer coefficients, it follows that it must be of the form $\pm x+d$ or $\pm 2x + d$; the conclusion readily follows

I loved this problem. At first it seems trivial when you don't realize that a,b can have different signs. Then it becomes the greatest density problem I've seen. Because it's not just the basic density tricks, you still need to have some original ideas to solve it. I couldn't get this problem during the contest, I got a 5/7, there was still a key idea missing. But I will write down the solution later. And congrats to Marcelo (IMO 2022 gold medalist from Brazil) for creating this amazing problem!

I will try to write down this solution as detailed as possible, so people that are not familiar with density problems can fully understand this. First and Second claims are just technical, not too many ideas, just the basics of density problems. The third and fourth claims on the other hand I find to be very cool and original. The fourth claim was named "The Naughty Lemma" by the official solution. And given the first $4$ claims, it's very easy to conclude the problem. \par First Claim (2 points): The degree of $P$ is even. \par Proof: Suppose not: $degP = n$, with $n$ odd. Then there are real numbers $u,v$ such that if $x>v$, then $P(x) > P(v)$, and if $x<u$, then $P(x) < P(u)$. This is possible by taking $u,v$ such that $P(v)$ is strictly greater than all local maximums and $P(u)$ is strictly smaller than all local minimums. \par Before we continue, we should state that there is a constant $C$ such that, if $Q(x) = |P(x+1) - P(x)|$, then $Q(x) > C|x|^{n-1}$ for all $|x| > C_0 > 0$, where all the roots of $Q$ belong to $(-C_0/2, C_0/2)$. \par Now take a big $M$ such that $M > |u| + |v| + C + 1$. Fix a large integer $N$. For each pair of integers $(x,y)$, with $x \neq y$, such that $|P(x) - P(y)| \leq N$ ($\star$), we call it: \par Good: if $|x|,|y| \geq M$ \par Bad: if exactly one of $|x|, |y|$ is less than $M$ \par Whatever: if both have sizes smaller than $M$. \par Clearly, the amount of $Whatever$ pairs is finite (for all $N$). So we shall not worry about them. \par Now take a $bad$ pair. Suppose WLOG that $|x| \geq M$. Then $$ N > |P(x) - P(y)| \geq |P(x) - P(x+\epsilon)| > C|x|^{n-1},$$where $\epsilon \in \{-1,1\}$, and it's $1$ if $x<0$ and it's $-1$ if $x>0$. \par Now take a good pair. WLOG $|x| > |y|$. So we know that $$N > |P(x)-P(y)| \geq |P(x) - P(x+\epsilon) > C|x|^{n-1}.$$($\epsilon$ defined the same way as before). \par So we must conclude that if $(x,y)$ are a solution to ($\star$), then both $|x|$ and $|y|$ are smaller than $C_1.N^{\frac{1}{n-1}}$. ($C_1^{1-n} = C$). So the total number of solutions must be. at most, $4C_1^2N^{\frac{2}{n-1}}$. \par But we know that the number of solutions is, at least, $N/2$. So sending $N$ to infinity, we must have that $\frac{2}{n-1} \geq 1 \iff n \leq 3$, which is a contradiction. \par Second Claim (Not worth any points). Given that the degree of $P$ is even, the majority of the solutions $(x,y)$ for $(\star)$ have $xy<0$, meaning that the number of solutions where $xy \geq 0$ grows smaller than $N$, in fact, we can prove just as we did in Claim 1 that it grows with degree $\frac{2}{n-1}$. I will not prove this claim here, given that its proof uses the exact same arguments as the ones used in Claim 1. You basically prove that if their signs are the same, then you lower their difference by bringing one of them close to the other, and then you use the lower bound of degree $n-1$. \par Third Claim (2 points): There exists an unique rational number $L$ such that the polynomial $P(x) - P(L-x)$ has degree, at most, $n-2$. The proof for this claim is very easy, but it was rewarded $2$ points because it's a key step for the solution. It's very easy to bound the difference $|P(x)-P(y)|$ when $xy>0$, but when this is not the case, this rational $L$ will help you a lot as you will see on the fourth Claim. And it also gives you the intuition that, if the problem statement is true, then whenever $P$ satisfies the problem, this $L$ must be an integer, and the polynomial $P(x) - P(L-x)$ must be linear, so it can cover $N/2$ integers up to $N$. \par Proof: Let $P(x) = a_nx^n + \dots + a_0$. You can write the polynomial $P(x) - P(A-x)$ explicitly as $$\sum_{k=0}^{n} a_k.x^k - \sum_{k=0}^n a_k \sum_{i=0}^k x^iA^{k-i}\binom{k}{i},$$which can be rewritten as $$\sum_{k=0}^n x^k (a_k - \sum_{i=0}^{n-k} a_{i+k} A^i \binom{i+k}{k}).$$ Then $P(x) - P(A-x)$ has always degree at most $n-1$, as the coefficient of $x^n$ is $1-(-1)^n = 0$, as $n$ is even. \par And the coefficient of $x^{n-1}$ is $2a_{n-1} + An$, which is $0$ if and only if $A = -\frac{2a_{n-1}}{n}$. And this is our desired rational $L$. \par So we conclude that the polynomial $P(x) - P(L-x)$ has degree, at most, $n-2$. In other words, we can say that there is a constant $C$ such that $|P(x)-P(L-x)| \leq C|x|^{n-2}$ for every $|x| > 0.1$. \par Fourth Claim (Naughty Lemma) (2 points): We say that a pair $(x,y)$ is $naughty$ if it satisfies ($\star$), $|x|,|y| > M$, $xy<0$ and $x+y \neq L$. \par So if $(x,y)$ is naughty, then $|P(x)-P(y)| > C|x|^{n-1}$. \par Proof: suppose WLOG $|x| \geq |y|$. The intuition for proving this Claim is basically the fact that you can't directly come up with a bound for this difference, and as $xy<0$, you use the fact that $P(L-y)$ is somehow close to $P(y)$, to, then, be able to compare their sizes. In other words, we will use the triangular inequality to say that: $$|P(x)-P(y)| \geq |P(x) - P(L-y)| - |P(y) - P(L-y)|.$$We already have an upper bound for $|P(y)-P(L-y)|$, so we're left with finding a bound for $|P(x) - P(L-y)|$. Let $t = 1$ if $L$ is an integer, and let $t = min\{\{L\}, 1-\{L\}\}$ if $L$ is not an integer. So we can say that if $L-y < x$, then $|P(x) - P(L-y)| \leq |P(x) - P(x-t)|$. If $L-y > x$, then $|P(x) - P(L-y)| \leq |P(x) - P(x+t)|$. In other words, since $|x|,|L-y| > M$, we know that bringing them together will decrease the difference, as $x(L-y)>0$. And, as $x,y$ are integers, we know that the difference between $x$ and $L-y$ is, at least, $t$. Since $t>0$, we can find a constant $C_2$ such that both $|P(x) - P(x+t)|$ and $|P(x) - P(x-t)|$ are smaller than $C_2|x|^{n-1}$. So we find that $$N > |P(x) - P(y)| \geq |P(x) - P(L-y)| - |P(y) - P(L-y)| \geq C_2|x|^{n-1} - C|y|^{n-2} \geq C_3x^{n-1}$$for some constant $C_3$ and large $|x|>M_0$. (The choice of $M$ does not interfere with $M_0$, so we may suppose as well that $M > M_0$). So this means that if a pair is naughty, then both $(x,y)$ have to be smaller than $C_4N^{\frac{1}{n-1}}$ for some constant $C_4$, meaning that there are, at most, $4C_4^2N^{\frac{2}{n-1}}$ naughty pairs. \par Conclusion (1 point): combining everything we proved so far, we must conclude that there is a constant $C_5$ such that the number of solutions $(x,y)$ for ($\star$) with $x+y \neq L$ is, at most, $C_5N^{\frac{2}{n-1}}$. \par Then take $N$ sufficiently large such that $N/2.5 < N/2 - C_5N^{\frac{2}{n-1}}$. \par So for $N$ this large, the number of solutions for $(x,y)$ with $x+y = L$ must be at least $N/2.5$. Now let $Q(x) = P(x) - P(L-x)$. So this directly implies that $L$ must be an integer, and it also means that the polynomial $Q$ covers $N/2.5$ integers up to $N$. Let $d$ be the degree of $Q$. Clearly $d>0$. We know that there is a constant $C_6$ such that $|Q(x)| > C_6|x|^d$ for every non-zero $x$. This means that if $Q(x) < N$, then $x < C_7N^{\frac{1}{d}}$ for some constant $C_7$. Sending $N$ to infinity, we conclude that $d \leq 1$, so $d=1$. \par Then $Q(x) = ax+b$ for some integers $a,b$. (we may suppose WLOG $a>0$. If not, we may switch $P$ by $-P$). But we know that if $0 < ax+b < N$, then $-b/a < x < N/a - b/a$. So there are at most $N/a + 1$ solutions for ($\star$), which implies $a \leq 2.5 \implies a \leq 2$. If $a=1$, then $Q$ covers all integers. If $a=2$, then $Q$ must cover all even or all odd integers, concluding the problem.

A few thoughts on this problem. Iberoamerican problems are usually not that technical. Algebra people would most likely love this problem being there though As far as I know, no student got full marks on the problem, including IMO gold medalists (who for sure were more than aware of IZhO 2022). A previous version of the statement asked (ISL Proposed Version 1) For which polynomials $P$ is it true that every integer $m$ is $P$-representable?

I encourage you to try this if you already know the ideas of Ibero 2023/6, but here

are the solutions for completeness.

However, there are overkill solutions

to such a clean version of the problem. If some positive density of integers could be let unrepresented, PNT would no longer be an obvious approach. So... (ISL Proposed Version "cute anti-PNT" 3) Ibero 2023/6. I haven't thought much about the following, but it is interesting. If $50\%$ is replaced by $34\%$, verbatim solution works. Can it be replaced by $26\%$?

CANBANKAN wrote: Tell me if this has any flaws. The key claim is that there exists a constant $c$ such that $P(x) - P(c-x)$ is linear. Proof: Assume not. WLOG $P$ has positive leading coefficient. Fix a sufficiently large $N$. Note there exists at most one $c$ such that $P(x)-P(c-x)$ is linear; for all but one $c$, the degree of that polynomial is at least 3. Let $S_c$ be the number of integers in $\{1,\cdots,N\}$ representable as $P(x)-P(c-x)$. We will show that $$\sum_{c\colon P(x)-P(c-x) \text{ have degree 0 or at least 2}} S_c = o(N)$$, which proves our claim. We will handle the "special" $c$ (the $c$ such that $\deg P(x)-P(c-x) < 3$) separately. Note $c$ is bounded, and $N$ can be arbitrarily large) Note for $|c|<N^{1/2}$, $S_c = O(N^{1/3})$, while for $c>N^{1/2}$ we consider $y=x+c/2$ and consider $T(y)=P(c/2+y) - P(c/2-y)$ when $y>0$; this is always nonnegative (can show this has all positive coefficients). The behavior of $P$ is monotone when $y>c/10$, and we can check $T(y)$ is increasing, so $T(y)>T(1)=P(c/2+1)-P(c/2-1) \approx c^{\deg P-1} >> N$. The case where $c<-N^{1/2}$ can be handled similarly. Therefore, the non-special $c$ contribute to $o(N)$ representable terms. Thus, for the special $c$ to contribute to $(1/2-o(1))N$ representable terms, $P(x)-P(c-x)$ must be linear; furthermore, since it has integer coefficients, it follows that it must be of the form $\pm x+d$ or $\pm 2x + d$; the conclusion readily follows Excellent solution! You made it way more concise than the other ones I've seen. The issue for me is that when you solve the problem you do extra work, like the special case of $degP$ being odd, and once you write your solution you believe its necessary. Turns out it's not, as the argument with $P(x)-P(-x+c)$ also takes care of this case. Even though, I believe there's a major flaw in your solution. For the case $\vert c \vert <N^{1/2}$ you say that $S_c=\mathcal{O}(N^{1/3})$. I understand this would be true if the coefficients of $P(x)-P(-x+c)$ were independent of $N$, but it turns out that their terms are of the order of $\binom{c}{i} x^i\approx c^ix^i$. Thus, for some $c>>N^{1/3}$ (for instance some $c\approx N^{1/2}$), I don't see how when evaluating $P(x)-P(-x+c)$ for some $x\approx N^{1/3}$ we should have that this is greater than $N$. Actually this is true, as it follows from the Naughtly Lemma mentioned in the official solution. Still, this Lemma only works for $degP$ even, and is worth $4$ points, which would almost completely invalidate your solution, Fortunately, thinking of your solution, I realized that this can be fixed without the usage of this Lemma. This is because for $c>>N^{1/3}$, then $P(x)-P(-x+c)>N$ for some $x\approx c$, follows from the fact that the coefficients are asymptotically $\binom{c}{i}x^i\approx c^ix^i$, so there will be some $x\approx c$ such that from that point on, our polynomial is greater than $N$. If you don't mind, I'll post your solution with this change in the next post.

Solution by CANBANKAN: The key claim is that there exists a constant $c$ such that $P(x) - P(c-x)$ is linear. Proof: Assume not. WLOG $P$ has positive leading coefficient. Fix a sufficiently large $N$. Note there exists at most one $c$ such that $P(x)-P(c-x)$ is linear; for all but one $c$, the degree of that polynomial is at least 3. Let $S_c$ be the number of integers in $\{1,\cdots,N\}$ representable as $P(x)-P(c-x)$. We will show that$$\sum_{c\colon P(x)-P(c-x) \text{ have degree 0 or at least 2}} S_c = o(N),$$which proves our claim. We will handle the "special" $c$ (the $c$ such that $\deg P(x)-P(c-x) < 3$) separately. We'll now work on two cases: Case 1. $\vert c \vert <N^{2/5}$. Note that the coefficients of $P(x)-P(c-x)$ have some $\binom{c}{i}\approx c^i$ for $c$ sufficiently big. Thus, we obtain that there will be some $x\approx c$, such that for all $x'>x$ then $\vert P(x')-P(c-x')\vert >N$. This tells us that $S_c\leq \max(\mathcal{O}(N^{1/degP-1}), \mathcal{O}(c))$. We have that $\mathcal{O}(N^{1/degP-1})\leq \mathcal{O}(N^{1/3})$, and $\mathcal{O}(c))\leq \mathcal{O}(N^{2/5})$, which gives us the following bound: $$\sum_{c\in\{\lfloor -N^{2/5} \rfloor, \dots, \lfloor N^{2/5}\rfloor\}}S_c\leq \mathcal{O}(N^{2/5}\cdot N^{2/5})=\mathcal{O}(N^{4/5})<<\mathcal{O}(N)$$. Case 2. $ c \geq N^{2/5}$. Consider $y=x+c/2$ and consider $T(y)=P(c/2+y) - P(c/2-y)$ when $y>0$; (this is always nonnegative and monotone as we trivially get that this has nonnegative coefficients). So $T(y)>T(1)=P(c/2+1)-P(c/2-1) \approx c^{\deg P-1} \geq N^{6/5}>> N$. The case where $c\leq -N^{2/5}$ can be handled similarly. Therefore, the non-special $c$ contribute to $o(N)$ representable terms. Thus, for the special $c$ to contribute to $(1/2-o(1))N$ representable terms, $P(x)-P(c-x)$ must be linear; furthermore, since it has integer coefficients, it follows that it must be of the form $\pm x+d$ or $\pm 2x + d$; the conclusion readily follows. Remark: The $N^{2/5}$ can be replaced by some $N^{a}$ for $\frac{1}{3}<a<\frac{1}{2}$. Fixing $a=\frac{2}{5}$ has been chosen for the sake of simplicity.

Thank you for taking your valuable time to read my work. Bigtaitus wrote: Even though, I believe there's a major flaw in your solution. For the case $\vert c \vert <N^{1/2}$ you say that $S_c=\mathcal{O}(N^{1/3})$. I understand this would be true if the coefficients of $P(x)-P(-x+c)$ were independent of $N$, but it turns out that their terms are of the order of $\binom{c}{i} x^i\approx c^ix^i$. Thus, for some $c>>N^{1/3}$ (for instance some $c\approx N^{1/2}$), I don't see how when evaluating $P(x)-P(-x+c)$ for some $x\approx N^{1/3}$ we should have that this is greater than $N$. Actually this is true, as it follows from the Naughtly Lemma mentioned in the official solution. Still, this Lemma only works for $degP$ even, and is worth $4$ points, which would almost completely invalidate your solution, Fortunately, thinking of your solution, I realized that this can be fixed without the usage of this Lemma. This is because for $c>>N^{1/3}$, then $P(x)-P(-x+c)>N$ for some $x\approx c$, follows from the fact that the coefficients are asymptotically $\binom{c}{i}x^i\approx c^ix^i$, so there will be some $x\approx c$ such that from that point on, our polynomial is greater than $N$. If you don't mind, I'll post your solution with this change in the next post. (1) Yeah, I shouldn't be saying problems are trivial before writing a complete solution. Sorry And thanks for fixing my solution

Canbankan absolutamente domado 17/09/2023