The general idea of my solution is to take $10^a + k \cdot 10^b$, where $b$ is initially very large and $a>>bn$ is even larger, and consider the number of carries between two terms. This must be even. I can then gradually make $a$ closer to $bn$. Constructing $k$ such that this is odd proves that no polynomial exists.

Just note that $P(x+10^t)-P(x)$ is a polynomial of degree less than $degP$and for arbitrary fix $x$ and large $t$ , we'll have a polynomial $Q$ st the condition still holds for some integer polynomial $Q$ with degree less than $deg P$. Continuing this we'll get the condition for $ax+b$ ; that is : $s(ax+b)+s(x)$ is even. But for $x=y.10^s$ , it's gonna be $s(ay)+s(b)+s(y)$ but $s(ay)+s(y)$ can be either odd or even , since $s(ka)(mod2)$ is achievable where $k$ is any positive integer and clealry it can be either even or odd. So the final answer is no.

alinazarboland wrote: Just note that $P(x+10^t)-P(x)$ is a polynomial of degree less than $degP$and for arbitrary fix $x$ and large $t$ , we'll have a polynomial $Q$ st the condition still holds for some integer polynomial $Q$ with degree less than $deg P$. Differencing (and hence reducing the degree) is exactly the idea in my solution in #2, but I do not see how your idea works. Could you make it more precise?

The answer is no. We claim: Claim: There are large positive integers \(C\) and \(D\) such \(C\gg D\gg0\) such that if \[Q(x)=Cx^4+Cx^3-Dx^2+Cx+C,\]then the polynomial \(P(Q(x))\) has all coefficients positive. Proof. Note that \((x^4+x^3+x+1)^n\) has terms of all degrees 0, 1, \ldots, \(x^{4n}\) with coefficients at least 1. Then the modification \((x^4+x^3-\varepsilon x^2+x+1)^n\) decreases coefficients by a polynomial amount in \(\varepsilon\) which tends to 0 as \(\varepsilon\to0^+\), so there is a sufficiently small choice of \(\varepsilon\) for which the signs of the coefficients of \((x^4+x^3+x+1)^n\) are not affected. Then for large \(C\) and \(D\approx C\varepsilon\), we may set \(Q(x)=Cx^4+Cx^3-Dx^2+Cx+1\), and the \(Q(x)^n\) term dominates. \(\blacksquare\) Then for \(r\) greater than the number of digits in all the coefficients of \(Q\) and \(P\circ Q\), we may find constants \(a\) and \(b\) such that \[s(Q(10^r))=9r+a\quad\text{and}\quad s(P(Q(10^r)))=b\]since incrementing \(r\) creates an additional digit of 9 in \(Q(10^r)\) generated by the \(x^2\) term and no additional nonzero digits in \(P(Q(10^r))\). Then one of \(k=10^r\) and \(k=10^{r+1}\) must fail.

Tintarn wrote:

where can I find the official solutions?imo website hasn't published 2022 isl at all despite the fact that the 2023 competition ended 4 days ago That's a bit wierd (brilliant solution btw)

blackmetalmusic wrote: Tintarn wrote:

where can I find the official solutions?imo website hasn't published 2022 isl at all despite the fact that the 2023 competition ended 4 days ago That's a bit wierd (brilliant solution btw) They are still compiling the solutions document, I believe, so the document will probably be released within the next few weeks.

LOL the $10$-adic derivative coming in clutch???? Notice that for large $r$, $s(P(k + 10^r)) = \sum s(P_i(k))$ where $P_i(k)$ is the sum of the terms of order $10^{ri}$. Notice each $P_i(k)$ is polynomial in $k$, and $\det P_i(k) = \deg P - i$. In particular, we can remove the top term since $P$ is monic and replace it with a constant in the summation. Thus the remaining terms have maximal degree $\deg P - 1$ with exactly one summand achieving this degree. We call this taking the $10$-adic derivative of $P$. Now suppose $s(k) \equiv s(P(k)) \pmod 2$. Then, we can take repeated $10$-adic derivatives on a summation form of $P(k)$ until it is written as a degree $1$ summation, meaning that every summand is constant in $k$ except a single summand, which is linear in $k$. The left hand side must be constant in $k$ as well, but $s(ak+b) \pmod 2$ cannot be constant in $k$, so we are done.

huge revenge arc. every polynomial digits problem is the same? The answer is no. In fact, we only need that $P$ has positive leading coefficient (rephrasing the problem to ask about sufficiently large $k$). The key claim is the following: Claim: There exist positive integers $C \gg D \gg 0$ such that if $$Q(x)=Cx^7-Dx^6+Cx^5+Cx^4+Cx^3-Dx^2+Cx+C,$$then all the coefficients of $P(Q(x))$ are positive except for that of $x^{7n-1}$ (which is negative). Proof: Note that $(x^7+x^5+x^4+x^3+x+1)^2$ has positive coefficients of $x^{14}$ and $x^{12}$ through $x^0$, and a coefficient of zero for $x^{13}$. Then by induction on $m\geq 2$, $(x^7+x^5+x^4+x^3+x+1)^m$ will have positive coefficients of $x^{7m}$ and $x^{7m-2}$ through $x^0$, and a coefficient of zero for $x^{7m-1}$, because The coefficient of $x^{7m}$ is clearly $1$ and the coefficient of $x^{7m-1}$ is clearly $0$. If the coefficient of $x^i$ in $(x^7+x^5+x^4+x^3+x+1)^{m-1}$ is positive, then so is the coefficient of $x^{i+7}$ in $(x^7+x^5+x^4+x^3+x+1)^m$, which implies that $x^{7m-2}$ through $x^7$ have positive coefficients. Likewise, if $i$ is chosen as above, then the coefficient of $x^i$ is also positive in $(x^7+x^5+x^4+x^3+x+1)^m$, which implies that $x^{7m-9}$ through $x^0$ have positive coefficients. Since $7m-9\geq 7$ for $m \geq 3$, it follows that $(x^7+x^5+x^4+x^3+x+1)^n$ has positive coefficients for $x^{7n}$ and $x^{7n-2}$ through $x^0$. Then for some extremely small $\varepsilon>0$, the polynomial $(x^7-\varepsilon x^6+x^5+x^4+x^3-\varepsilon x^2+x+1)^n$ should still have positive coefficients for $x^{7n}$ and $x^{7n-2}$ through $x^0$, since as $\varepsilon \to 0^+$ the "perturbance" of each of the positive coefficients of $(x^7+x^5+x^4+x^3+x+1)^n$ goes to $0$ as well. On the other hand, the coefficient of $x^{7n-1}$ is now clearly negative. Finally, pick $D$ massive and set $C \approx D/\varepsilon$, so $C$ is massive as well. Then the $a_nQ(x)^n$ term dominates in the expansion of $P(Q(x))$, which implies the desired result. $\blacksquare$ For all integer $k$ sufficiently large relative to the coefficients in $Q(x)$ and $P(Q(x))$, the parity of $s(Q(10^m))$ will be the same, since incrementing $k$ by $1$ will result in the insertion of $5$ digits equal to $0$ and $2$ digits equal to $9$ in its decimal expansion. On the other hand, incrementing $k$ by $1$ results in the parity of $s(P(Q(10^m))$ changing, since we insert $7n-1$ digits equal to $0$ and $1$ digit equal to $9$ in its decimal expansion. Hence either $k=Q(10^m)$ or $k=Q(10^{m+1})$ will make $s(k)+s(P(k))$ odd. $\blacksquare$ Remark: $Q(x)$ was found through trial and error (with the goal of making the second-highest coefficient in $P(Q(x))$ negative)

The answer is negative. Here is my proof, very much inspired by https://artofproblemsolving.com/community/c5h1823555p12189457. For all positive integer $k$, we have $$s(x)\equiv s(P(x))=s(x^n+\dots+a_1x+a_0) \pmod 2 \quad (\spadesuit)$$Replace $x$ with $10^h\cdot x$ in $(\spadesuit)$, where $h$ is an integer sufficiently large, we have $$s(x)\equiv s(x^n)+\dots+s(a_1x)+s(a_0) \pmod 2 \quad (\heartsuit)$$holds for every positive integer $k$. Lemma: For any given integers $n\geq 1$, $a\neq 0$, $a_{i,j}$, and $\epsilon_{i,j}$ $(0\leq j\leq n-1, i>0)$, the following can not happen: $$s(ax^n)+\sum\limits_{j=0}^{n-1}\sum\limits_{i}\epsilon_{i,j}s(a_{i,j}x^j) \equiv 0 \pmod 2 \quad (\clubsuit)$$for all positive integer $x$. Proof of the lemma: We apply induction on $n$. First let us consider the case $n=1$. $(\clubsuit)$ is equivalent to proving $$s(ax)\equiv b \pmod 2$$can not happen for all positive integer $x$. Suppose otherwise. We may assume that $\gcd(a,10)=1$, otherwise if $a=2^\alpha 5^\beta a'$ with $a'$ coprime to $10$, consider $x'=2^\beta 5^\alpha x$ and $b\equiv s(ax')=s(a'x) \pmod 2$. Take $x=10^{\text{large}}+1$ shows that $b$ is even. Take $x=(1+10^l+10^{2l}+\dots+10^{(x-1)l})/a$ with $l=\phi(a)$ shows that $b\equiv x\equiv 1 \pmod 2$, contradiction! Hence $(\clubsuit)$ is true when $n=1$. Suppose that $(\clubsuit)$ holds for $n-1$, $n>1$. For the sake of contradiction assume it is untrue for $n$. Replace $x$ with $10^{\text{very large}}+x$ in $(\clubsuit)$ to get $(\clubsuit')$, then consider $(\clubsuit')-(\clubsuit)$ shows that another assertion similar to $(\clubsuit)$ but in degree $n-1$ holds, contradiction! Thus the lemma holds. $\qquad \blacksquare$ Obviously $\clubsuit$ contradicts $\heartsuit$, and we are done.

Hmmm here's something which is hopefully unique (and hopefully correct too, whoops) Will add more tomorrow in school The answer is no. At the end of the proof, we omit the construction (I'm pretty sure it's trivial). Sketch: Step 1: Notice that we can plug in numbers of the form \[k=10^A\cdot a+10^B\cdot b+\dots\]to get quite a bit of information. In fact, it's not hard to prove that we can essentially decompose; if $k=10^A\cdot a+10^B\cdot b+10^C\cdot c$, then something like \[s(a)+s(b)+s(c)=\text{some really big expression which is a sum of function }s\text{ applied to a bunch of monomials}.\] Step 2: Use PIE, this allows us to show that in the case with $n-1$ variables the sum \[\sum_{i=1}^{n-1} s\left(\frac{n!}{2}c_i\cdot c_1c_2\dots c_{n-1}\right)+s(a_{n-1}c_1c_2\dots c_{n-1})\]has constant parity. Then fix the product of all variables and you can easily find a counterexample. (I think setting $n$ variables might work too.) This feels too good to be true, I don't know. It took a lot of hard thinking though, hopefully it's correct!

Literally TSTST 2019/6 Lemma: There exists a polynomial $Q(x)$ that has only one negative coefficient, and $P(Q(x))$ has all positive coefficients. We choose the polynomial $$Q(x) = Ax^4 + Ax^3 - x^2 + Ax + A$$for sufficiently large $A \neq 0 \pmod{10}$ and prove the following claim which proves the lemma. Claim: $Q(x)^k$ has only positive coefficients Essentially, we can treat $Q(x)$ like a generating function. Take the sum of elements in a $k$-tuple that takes values from $\{1, 2, 3, 4\}$ and contains $2$. Define such a tuple to be "bad", and all other tuples to be "good". This sum can always be achieved by another $k$-tuple that does not contain $2$ because the $x^2$ term is in the "middle" of the polynomial. Now, we can just take sufficiently large $A$ to completely nullify the effects that the $x^2$ term has because there will always be another $k$-tuple to remove the influence of any bad tuples. Therefore the claim is proved. Now clearly $$P(Q(x)) = \sum_{i=0}^{k} a_i \cdot Q(x)^i$$which obviously has all positive coefficients because all $a_i$ are positive. Now we just take sufficiently large $i$ such that the coefficients in $P(Q(10^i))$ and $Q(10^i)$ are "separated" out. Simply note that by going from $i \to i+1$, $Q(10^i)$ is incremented by $9$ because $10 \nmid A$ so there is no carrying issues. Now, $P(Q(10^i))$ will not change because all coefficients are positive, so obviously the condition must fail for one of $\{i, i+1\}$