Find the least positive integer \(M\) for which there exist a positive integer \(n\) and polynomials \(P_1(x)\), \(P_2(x)\), \(\ldots\), \(P_n(x)\) with integer coefficients satisfying \[Mx=P_1(x)^3+P_2(x)^3+\cdots+P_n(x)^3.\] Proposed by Karthik Vedula
Problem
Source: ELMO 2023/5
Tags: Elmo, algebra, ELMO 2023
26.06.2023 08:49
The answer is $M=6$. $M=6$ is achievable easily, take $6x=(x+1)^3+(x-1)^3+(-x)^3+(-x)^3$ I claim that $3|M$ and that $2|M$. This implies the result. The fact that $3|M$ is easy, the $x$ coefficient of $P(x)^3$ is either $0$ or $3ab^2$ where $a$ is the $x$ coefficient of $P$ and $b$ is the constant term. The hard part is showing $2|M$ always holds.
26.06.2023 08:52
We claim that the minimal value of $M$ is $6$. This is acheived by picking $P_1(x) = x+1, P_2(x) = x-1, P_3(x) = -x, P_4(x) = -x$ because then: $$(x+1)^3 + (x-1)^3 + (-x)^3 + (-x)^3 = x^3 + 3x^2 + 3x + 1 + x^3 -3x^2 + 3x -1 -x^3 -x^3 = 6x$$ Now we show that this is indeed the smallest possible. We claim that $6 \mid M$ holds always. Let $P_i(x) = \sum_{j=0}^{d} f(i,j)x^j$ $\forall 1 \leq i \leq n$ where $d$ is the maximum degree among $P_i$. The claim is that the sum of all coefficients of $x^j$ when $3 \nmid j$ is divisible by $6$ for each $P_i(x)^3$. Now $$ P_i(x)^3 = \left( \sum_{j=0}^{d} f(i,j)x^j \right)^3 = \sum_{j=0}^d f(i,j)^3x^{3j} + 3 \cdot \sum_{0 \leq a \neq b\leq d} f(i,a)^2f(i,b) x^{2a+b} $$$$+6\cdot \sum_{0 \leq a \neq b \neq c \leq d}f(i,a)f(i,b)f(i,c)x^{a+b+c}$$We don't care about the coefficients of the first summation, as all the monomials in it are cubes. The third sum is clearly divisible by $6$ (because of the $6$, the sub-sum of all the terms with $x^i$ where $3 \nmid i$ is also divisible by $6$, which is what we want) and the second sum is divisible by $3$. Thus it suffices to show that $$\sum_{0 \leq a \neq b\leq d \text{ and } 3 \nmid 2a+b} f(i,a)^2f(i,b)$$is even. Firstly observe that, as $(2a+b) + (a+2b) = 3(a+b)$, $3 \nmid 2a+b \iff 3 \nmid a+2b$. Thus if $f(i,a)^2f(i,b)$ occurs in the summation then so does $f(i,b)^2f(i,a)$ . Note that we have thus created a pairing among all the summands in the summation. Now as $y^2z + yz^2 = yz(y+z)$ is always even for any positive integers $y,z$ (As if one of $y,z$ is even it is clearly even and if $y,z$ are both odd then $(y+z)$ is even) we get that $f(i,a)^2f(i,b) + f(i,b)^2f(i,a)$ is even. Thus the whole summation is even. Now summing the coefficients of $x^j$ when $3 \nmid j$ over all polynomials $P_i(x)^3$ we get that that this sum is divisible by $6$ by the argument above. On the other hand its equal to $M$. Thus $M$ is divisible by $6$ and thus $M =6$ is the minimum possible value for $M$, which we have shown that it is attainable. We are done $\square$. Here is an interesting construction for $M=6$ that I found during the test, while trying to find one for $M=3$: $$(2x^2+x+1)^3 + (2x^2+x-1)^3 - (x^2+4x)^3 + (x^2-4x)^3 + 150x^3 - (x^2+x+2)^3 + (x^2+x-2)^3 -2(-2)^3 - 16(x^2)^3$$
26.06.2023 08:56
The answer is $M = 6$. This works since $6x = (x+1)^3 + (x-1)^3 + (-x)^3 + (-x)^3$. To show that no smaller $M$ work, we note that By taking derivatives, we get $\textstyle M = 3\sum_i P_i'(x) P_i(x)^2$, so $3 \mid M$. By viewing the identity in $\mathbb{F}_4$ and plugging in $x \in \mathbb{F}_4 \setminus \mathbb{F}_2$, we get $\textstyle Mx = \sum_i P_i(x)^3 = \sum_i (0\text{ or }1) \in \mathbb{F}_2$, so $2 \mid M$.
26.06.2023 09:39
We will prove that the answer is $M_{\min}=6$. If $M=6$, we may note that $(x+1)^3+(x-1)^3+(-x)^3+(-x)^3=6x,$ and so $M=6$ works. Now, we have the following Claim, which finishes the problem. Claim: If $M$ works, then $M$ is a multiple of $6$. Proof: Firstly we prove that $M$ must be a multiple of $3$. Indeed, let $x_i,y_i$ be the coefficient of $x$ and the constant term of polynomial $P_i$, for all $i$. Then, the coefficient of $x$ of the polynomial $P_1^3(x)+\ldots+P_n^3(x)$ is equal to $3(x_1^2y_1+\ldots+x_n^2y_n),$ which is equal to $M$, and so $3 \mid M$. Now, we prove that $M$ must be a multiple of $2$, which finishes. Let $P_i(x)=a_tx^t+\ldots+a_1x+a_0$ for some $i$, with $a_j$ reals, not all necessarily non-zero. We will prove that the sum of the coefficients of powers of the form $x^{3k+1}$ and $x^{3k+2}$ at the polynomial $P_i^3(x)$ is an even number. Let $\mathcal{A}$ be the set of all triples of the form $(x,x,y)$ with $x \neq y$, such that $2x+y$ is not a multiple of $3$. Note that the coefficient of $x^j$, with $j$ not a multiple of $3$, is equal to $3$ times the number of triples in $\mathcal{A}$ such that $2x+y=j$, plus the number of triples of the form $(x,y,z)$ such that $x+y+z=j$ and $x,y,z$ are pairwise distinct (note that triples of the form $(x,x,x)$ do not yield acceptable coefficients, as $x+x+x=3x$ is a multiple of $3$). However, note that the number of those triples is a multiple of $6$, and in particular an even number, by taking cyclic shifts of $(x,y,z)$. Hence, by reducing $\pmod 2$, we may focus only on triples in $\mathcal{A}$. Now, the crucial observation is that $(x,x,y) \in \mathcal{A}$ is a triple coresponding to a coefficient of $x^j$ with $j$ not a multiple of $3$ if and only if $(y,y,x)$ is, too. Indeed, $3 \mid 3x+3y=(2x+y)+(2y+x),$ and so $3 \nmid 2y+x$. Hence, we may pair up the remaining coefficients of those powers, hence we conclude that their sum is indeed a multiple of $2$. However, note that since $P_1^3(x)+\ldots+P_n^3(x)=Mx,$ this in turn implies that the sum of the coefficients of powers of the form $x^{3k+1}$ or $x^{3k+2}$ at $Mx$ must be even, which in turn implies that $M$ must be even, as desired. To sum up, since $2 \mid M$ and $3 \mid M$, we infer that $6 \mid M$, as desired $\blacksquare$
26.06.2023 09:42
We claim the answer is 6. For a polynomial $A$; we define $f(A)$ as the sum of coefficients of terms in $A$, which have degree not divisible by $3$. The proof lies on the following claim: Claim : For $A \in \mathbb{Z}[X]$, $6 \mid f(A^3)$. Proof : Note that $f(A)=A(1)-\frac{A(1)+A(\omega)+A(\omega^2)}{3}$ where $\omega^2+\omega+1=0$. Let $A(x)=\sum c_ix^i$. Then define $k=\sum_{i \equiv 1 \text{ mod }3} c_{i}$, $l=\sum_{i \equiv 2 \text{ mod }3} c_{i}$ and $m=\sum_{i \equiv 0 \text{ mod }3} c_{i}$. Hence $A(\omega)=l\omega^2+k\omega+m$ and $A(\omega^2)=k\omega^2+l\omega+m$ and $A(\omega)=k+l+m$. Hence, \begin{align*} f(A^3)&=A(1)^3-\frac{A(1)^3+A(\omega)^3+A(\omega^2)^3}{3} \\ &= (k+l+m)^3 - \frac{(k+l+m)^3+(l\omega^2+k\omega+m)^3+(k\omega^2+lx\omega+m)^3}{3} \\ &=3(k^2l+l^2k+l^2m+m^2l+k^2m+m^2k) \end{align*}Clearly $6 \mid f(A^3)$, proving the claim. $\square$ Note that $f(A+B)=f(A)+f(B)$. To finish, by the claim $6 \mid f(P_i^3)$. Hence $$6 \mid \sum_{i=1}^{n} f(P_i^3) = f\left( \sum_{i=1}^{n} P_i^3 \right) = f \left( Mx\right) = M$$Hence, $6 \mid M \implies M \geqslant 6$. And indeed the following construction works for $M=6$ : $$(x+1)^3 + (x-1)^3 +(-x)^3 + (-x)^3 = 6x$$Hence we get the claimed answer, and we are done!
26.06.2023 09:43
I liked this problem a lot, Here's what I submitted It seems like my approach is different from all the solutions above
Attachments:
ELMO_2023_P5_math_comb01_compressed.pdf (242kb)
26.06.2023 10:02
Let $P(x)_i=a_{(m,i)}x^m+a_{(m-1,i)}x^{m-1}+...+a_{(1,i)}x+a_{(0,i)}$ where $m=max (degP_i)$ so some $a_{(m,i)}$ may be equal to $0$ then by the condiction we have: $Mx=\sum_{j=1} ^{j=n}\sum _{i=0}^{i=m}a_{(j,i)}x^{3i}+3\sum_{j=1} ^{j=n}\sum _{0\leqslant b\neq c\leqslant m}a_{(j,b)}^2a_{(j,c)}x^{2b+c}+6\sum_{j=1} ^{j=n}\sum _{0\leqslant b\neq c\neq d\neq b\leqslant m}a_{(j,b)}a_{(j,c)}a_{(j,d)}x^{b+c+d}$ (1) Claim (1): $3|M$ Proof: obviously since its coefficient of $x$ in the $RHS$ is $3\sum _{j=1}^n a_{(j,0)}^2a_{(j,1)}$ Claim (2): $2|M$ Proof: Suppose that $M=odd$ we wil lead to contradition. From here on we will write $[x,y]=\sum _{j=1}^na_{(j,x)}^2a_{(j,y)}$ for convenience now we compare the coefficients of (1) in powers of the form $x^z$ with $z\not\equiv 0(mod 3)$ obviously $6\sum_{j=1} ^{j=n}\sum _{0\leqslant b\neq c\neq d\neq b\leqslant m}a_{(j,b)}a_{(j,c)}a_{(j,d)}x^{b+c+d}$ has no participation since because we work $mod2$ For $z=1$ we have:$[0,1]=1$ For $z=2$ we have:$[0,2]+[1,0]=0$ For $z=4$ we have:$[0,4]+[1,2]+[2,0]=0$ . . . For $z=3m-1$ we have:$[m,m-1]=0$ Sub-Claim (1): If $[x,y]$ exist then $[y,x]$ exist Proof: We see that $[x,y]$ appear at most once when $z=2x+y\not\equiv 0(mod 3)$ So it is enough to prove that if $2x+y\not\equiv 0(mod 3)$ then $x+2y\not\equiv 0(mod 3)$ But this is obviously because $3|3(x+y)=(2x+y)+(2y+x)$ Also we are going to work $mod2$ so we can say that $[x,y]=[y,x]$ because $[x,y]=\sum _{j=1}^na_{(j,x)}^2a_{(j,y)}\equiv \sum _{j=1}^na_{(j,x)}a_{(j,y)}\equiv \sum _{j=1}^na_{(j,x)}a_{(j,y)}^2=[y,x] (mod 2)$ So if we add all of them we will get that: $1\equiv \sum [x,y]+[y,x]\equiv 2\sum [x,y]\equiv 0(mod2)$ contradiction Claim (3): Τhe smallest $M$ is $M=6$ Proof: For claim (1),(2) we have $6|M\Rightarrow M\geqslant 6$ and $6x=(x-1)^3+(x+1)^3-x^3-x^3$
26.06.2023 12:44
The answer is $M=6$, achieved by $6x = (x+1)^3 + (x-1)^3 + (-x)^3 + (-x)^3$. For the other direction, we claim that $6\mid M$. The proof goes in two parts: In modulo $3$, we have $P_j(x)^3 = P_j(x^3)$. Thus, the coefficient in front of $x$ in $P_1(x)^3 + P_2(x)^3 + \dots +P_n(x)^3$ is always divisible by $3$, implying that $3\mid M$. Work in $\mathbb F_4 = \mathbb F_2[\omega]$ and plug in $x=\omega$. Then, we have $$M\omega = P_1(\omega)^3 + P_2(\omega)^3 + \dots + P_n(\omega)^3.$$However, in $\mathbb F_4$, we have $\alpha^3 \in\{0,1\}$, so $P_j(\omega)^3\in\{0,1\}$, and thus, $M\omega \in\{0,1\}$. This forces $2\mid M$.
26.06.2023 15:30
oh The answer is $\boxed{M = 6}$, achieved by \[ 6x = (x)^3 + (-x)^3 + (x + 1)^3 + (x - 1)^3. \]It suffices to prove $3 \mid M$ and $2 \mid M$. Claim 1.$ $ $3 \mid M$. Differentiate with respect to $x$: \[ M = \sum_{i = 1}^n 3P_i'(x)P_i(x)^2. \]Each term in the RHS summation is $3$ times an integer polynomial, hence $3 \mid M$. $ ~ \square$ Claim 2.$ $ $2 \mid M$. Take $x = \alpha = -\frac{1}{2} + \frac{i\sqrt{3}}{2}$ and $x = \beta = -\frac{1}{2} - \frac{i\sqrt{3}}{2}$ (roots of $x^2 + x + 1$) and sum the results: \[ -M = M\alpha + M\beta = \sum_{i = 1}^n P_i(\alpha)^3 + P_i(\beta)^3. \]Reduce $P_i(\alpha)$ to the linear integer polynomial $r_i\alpha + s_i$ via repeated applications of the identity $\alpha^2 = -\alpha - 1$. Since $\alpha$ and $\beta$ are conjugates, it follows that $P_i(\beta) = r_i\beta + s_i$ as well. Thus, \[ -M = \sum_{i = 1}^n P_i(\alpha)^3 + P_i(\beta)^3 = \sum_{i = 1}^n (r_i\alpha + s_i)^3 + (r_i\beta + s_i)^3 = \sum_{i = 1}^n 2r_i^3 + 2s_i^3 - 3r_is_i(r_i + s_i). \]Observe that $r_is_i(r_i + s_i)$ is always even, so every term in the RHS summation is even, hence $2 \mid M$. $ ~ \blacksquare$ Remark.$ $ Taking $x = \alpha$ and $x = \beta$ is motivated by the following conjecture (motivated by observation): For all (expanded) polynomials $P_i(x)^3$, the sum of the coefficients corresponding to terms with degree not divisible by $3$ is always even. Attempting to prove this introduces $\alpha$ and $\beta$ via the Root of Unity Filter trick.
26.06.2023 19:04
27.06.2023 06:38
$$2+2-1=3.$$
27.06.2023 06:41
The answer is $M=6$, achieved by $(x+1)^3+(x-1)^3+(-x)^3+(-x)^3$. Let $d$ be the maximum degree of the polynomials and write $$P_i(x)=a_idx^d+\cdots+a_i0$$where $a_d$ can be zero. The expansion of $P_m^3$ is then $$\sum_{0\leq i \leq d} a_{mi}^3x^{3i}+3\sum_{0\leq i\neq j\leq d} a_{mi}^2a_{mj}x^{2i+j}+6\sum_{0\leq i<j<k\leq d} a_{mi}a_{mj}a_{mk}x^{i+j+k}.$$Any $x$ coefficient cannot come from the first sum, so it must be divisible by $3$. Hence $3 \mid M$. Now we show that $2 \mid M$ as well. Work modulo $2$, so the third sum above vanishes and we have $$\sum_{m=1}^n \left(\sum_{0 \leq i \leq d} a_{mi}x^{3i}+\sum_{0 \leq i \neq j \leq d} a_{mi}a_{mj}x^{2i+j}\right)\equiv Mx.$$Now we double count the sum of the coefficients of the $x^k$ terms where $3 \nmid k$, with the goal of proving that $2 \mid M$. On one hand, counting by the RHS, this is just $M$. On the other hand, for the LHS we only care about the sum of $a_{mi}a_{mj}$ (this product is ORDERED, so $a_{mi}a_{mj}$ and $a_{mj}a_{mi}$ are counted separately), over all $(m,i,j)$ such that $i \neq j$ and $3 \nmid 2i+j$. However, if $3 \nmid 2i+j$, then it doesn't divide $4i+2j$ either and thus doesn't divide $2j+i$, so if $(m,i,j)$ is counted in the LHS, then $(m,j,i)$ must be as well, and these triplets clearly produce the same parity coefficient. Therefore, we can pair each $(m,i,j)$ with $(m,j,i)$ and get that the sum counting by the LHS is even. Thus $2 \mid M$, so $6 \mid M$ and we are done. $\blacksquare$ Remark: Because you can add linear combinations of any $M$ you find that work to get more $M$, I am told that a number of people at MOP came up with absurd constructions involving linear combinations of numbers. I recall someone combining 234 and something else to get 6.
27.06.2023 06:44
Also, it's interesting to note that the original version of the problem used three-variable polynomials $P_i(x,y,z)$, and the LHS was equal to $Mxyz$ instead. What's funny is that this is actually just the same problem: plug in $y=z=1$ and solve the 1-variable version to get that $6 \mid M$, and for a construction take anything that works for the 1-variable version and replace every $x$ with $xyz$. Although three variables also gives you the possibly more natural construction of $(x+y+z)^3+(-x-y)^3+(-y-z)^3+(-z-x)^3+x^3+y^3+z^3$, motivated by the fact that $6xyz$ occurs directly in the expansion of $(x+y+z)^3$. (Hopefully I am allowed to share this? I was not actually involved in the creation of the ELMO this year)
28.06.2023 23:33
bissue wrote: oh The answer is $\boxed{M = 6}$, achieved by \[ 6x = (x)^3 + (-x)^3 + (x + 1)^3 + (x - 1)^3. \]It suffices to prove $3 \mid M$ and $2 \mid M$. Claim 1.$ $ $3 \mid M$. Differentiate with respect to $x$: \[ M = \sum_{i = 1}^n 3P_i'(x)P_i(x)^2. \]Each term in the RHS summation is $3$ times an integer polynomial, hence $3 \mid M$. $ ~ \square$ Claim 2.$ $ $2 \mid M$. Take $x = \alpha = -\frac{1}{2} + \frac{i\sqrt{3}}{2}$ and $x = \beta = -\frac{1}{2} - \frac{i\sqrt{3}}{2}$ (roots of $x^2 + x + 1$) and sum the results: \[ -M = M\alpha + M\beta = \sum_{i = 1}^n P_i(\alpha)^3 + P_i(\beta)^3. \]Reduce $P_i(\alpha)$ to the linear integer polynomial $r_i\alpha + s_i$ via repeated applications of the identity $\alpha^2 = -\alpha - 1$. Since $\alpha$ and $\beta$ are conjugates, it follows that $P_i(\beta) = r_i\beta + s_i$ as well. Thus, \[ -M = \sum_{i = 1}^n P_i(\alpha)^3 + P_i(\beta)^3 = \sum_{i = 1}^n (r_i\alpha + s_i)^3 + (r_i\beta + s_i)^3 = \sum_{i = 1}^n 2r_i^3 + 2s_i^3 - 3r_is_i(r_i + s_i). \]Observe that $r_is_i(r_i + s_i)$ is always even, so every term in the RHS summation is even, hence $2 \mid M$. $ ~ \blacksquare$ Remark.$ $ Taking $x = \alpha$ and $x = \beta$ is motivated by the following conjecture (motivated by observation): For all (expanded) polynomials $P_i(x)^3$, the sum of the coefficients corresponding to terms with degree not divisible by $3$ is always even. Attempting to prove this introduces $\alpha$ and $\beta$ via the Root of Unity Filter trick.
30.06.2023 17:44
The answer is $M=6$ achieved by $6x=(x+1)^3+(x-1)^3+(-x)^3+(-x)^3$
, Claim: $3 \mid M$ If $b_i$ is the linear coefficient of $P_i$ and $c_i$ is it's constant term, then the linear term of $P_i(x)^3$ is $3b_ic_i^2 \equiv 0 \pmod 3$
If $P(x) = a_d x^d + \cdots a_1 x + a_0$, It's cube will contain coefficients of the form $(1,3,6)\cdot a_ia_ja_k$ Now look at all the terms with degrees that are not divisible by $3$ and look at everything mod $2$ So we do not care about any terms with $6$ (so we do not cared about $i,j,k$ distinct) also the $1$ stuff would only come from cubes, and since we are looking at degrees not divisible by $3$, we do not care about $i=j=k$ case either. So we only care about terms of form $3a_x^2a_y$ ($x \neq y$ which mod $2$ is just $a_xa_y$ Now I will prove that each such term occurs exactly twice. Note that this terms comes for degree $l$ iff $l=2x+y$ or $l=2y+x$, and $2x+y \equiv 0 \pmod 3 \iff 2y+x \equiv 0 \pmod 3$ and also $1 = 2(0)+(1) \le 2x+y \le 2(d)+(d-1) = 3d-1$ so we're done here. So now when we sum this stuff over all the polynomials, on one side we $M$ and on the other we have a bunch of $2a_xa_y$ terms, so that is clearly divisible by $2$ so we are done... Really happy with this solve, probably one of my first $P2$ level algebra solves, and the great thing is I solved this during my vacation
Attachments:
p5.pdf (176kb)
01.07.2023 00:57
The minimum value of \(M\) is 6, achieved by \[6x=(x+1)^3+(x-1)^3+(-x)^3+(-x)^3.\]For the lower bound, write \[Mx=\sum_{k=1}^n P_k(x)^3.\]We will show \(6\mid M\), which suffices. In \(\mathbb Z[x]/(x^2+x+1)\), there are integers \(a_k\) and \(b_k\) for each \(k\) such that \(P_k(x)=a_kx+b_k\). Then \begin{align*} Mx&=\sum_{k=1}^n(a_kx+b_k)^3\\ &=\sum_{k=1}^n\left[ a_k^3+b_k^3+3a_k^2b_kx+3a_kb_k^2(-x-1) \right]\\ &=\sum_{k=1}^n\left[ a_k^3+b_k^3-3a_kb_k^2+3a_kb_k(a_k-b_k)x \right], \end{align*}so we must have \[M=\sum_{k=1}^n3a_kb_k(a_k-b_k).\]But \(3a_kb_k(a_k-b_k)\) is a multiple of 6 for all integers \(a_k\) and \(b_k\), so \(6\mid M\). Remark: Equivalently, one may substitute a primitive third root of unity for \(x\).
02.07.2023 01:55
Solved with Qingzhou_Xu at 5 AM in Japanese time because I woke him up by taking a fat sh*t. Here is a pretty clean way to prove that $2 \mid M$, the crux of the problem. We have the following claim which finishes by $\pmod{2}$ consideration on both sides. $\textbf{Claim:}$ Given any $P(x) \in \mathbb{Z}$, the sum of the coefficients of $P(x)^3$ excluding monomials of $0 \pmod{3}$ power is even. $\textbf{Proof)}$ To prove this, write $P(x) = Q_0(x)+Q_1(x)+Q_2(x)$ where the three polynomials are of the form $Q_i(x) = \sum_{k \geq 0} a_ix^{3k+i}$. Then, we can extract the coefficients we wish as: $$3\left[Q_0(1)^2Q_2(1)+Q_0(1)^2Q_2(1)+Q_1(1)^2Q_0(1)+Q_1^2(1)Q_2(1)+Q_2(0)^2Q_0(1)+Q_2(0)^2Q_1(0)\right]$$ Defining $a = Q_0(1), b = Q_1(1), c = Q_2(1)$, we can see that the above expression is $$3(a^2b+a^2c+b^2a+b^2c+c^2a+c^2b) = 3((a+b)(b+c)(c+a)-2abc) \equiv 0 \pmod{2}$$because by the pigeonhole principle at least one of $a+b, b+c, c+a$ is divisible by $2$! $\blacksquare$ $\blacksquare$
03.04.2024 23:42
The answer is $M=6$ achieved with $6x=(x-1)^3+(x+1)^3+(-x)^3+(-x)^3$. Claim: $3\mid M$. Proof. Take derivatives. $\blacksquare$ Now, we show that $M=3$ fails. Let $P_i(x)=\sum_{k=0}^mx^ka_{i,k}$ for some $N$ that's the same over all $P_i$ which is possible by taking $N\geq \max(\deg P_i)$. Now, we look at the coefficient of $x^k$ on the RHS for $3 \nmid k$ taken modulo $2$. This sum will include terms of the form $3\sum a_{i,j}a_{i,l}^2$ and terms of the form $\sum 6a_{i,j}a_{i,k}a_{i,l}$. We can throw away all of the terms of the latter form when taken modulo $2$, leaving us with the sum $\sum_{i=1}^N\sum_{m+2p=k}a_{i,m}a_{i,p}^2$ as the $x^k$ coefficient on the RHS for each $3 \nmid k$. Now, sum this over all such $k$. Claim: $a_{i,m}a_{i.p}^2$ is in this sum iff $a_{i,p}a_{i.m}^2$ also it Proof. It will be in the sum iff $m+2n \not \equiv 0 \pmod 3$ and the result follows as $(2m+p)+(2p+m) \equiv 0 \pmod 3$. $\blacksquare$ Thus we an pair the sum as \[\sum_{i=1}^N \sum_{\overset{ 3 \mid m+2p}{m>p}}a_{i,m}a_{i,p}^2+a_{i,p}a_{i,m}^2 \equiv \sum_{i=1}^N \sum_{\overset{3 \mid m+2p}{m>p}}a_{i,m}a_{i,p}+a_{i,p}a_{i,m} \equiv \sum_{i=1}^N \sum_{\overset{ 3 \mid m+2p}{m>p}}0 \equiv 0 \pmod 2\]so the sum is even. However, this sum of the $x^k$ coefficients for $3 \nmid k$ on the left hand side just sums $2$, so it's odd. This produces the desired contradiction. Remark. In contest (or taking it from home) I got a 3 on this problem. This is since i did the solution for $N=1,2$ or something and said "continue a similar process for all $N$". I just didn't realize that the terms being summed were the non multiple of $3$ terms but in hindsight this is motivated since we really don't want any coefficients cubes as they are harder to deal with mod 2
15.04.2024 00:02
Solved with megarnie. The answer is $M = 6$. It's easy to see that this works since $6x = (x+1)^3 + (x-1)^3 + (-x)^3 + (-x)^3$. We'll now show that no smaller $M$ work. First, note that in $\mathbb{F}_3[x]$ we have \[M = \frac{d}{dx}\sum_{k =1}^nP_k(x)^3 = \sum_{k = 1}^n 3P_k(x)^2P_k'(x) = \sum_{k =1}^n 0 = 0,\]so $M\equiv 0\pmod{3}$. Hence, if an $M$ smaller than $6$ worked, it would have to be $3$. Assume for contradiction $M =3$ worked then. Letting $\omega = \text{exp}(\tfrac{2}{3}i\pi)$ be a cube root of unity, we then have \[3\omega = \sum_{k = 1}^nP_k(\omega)^3.\]But note that $P_k(\omega)\in\mathbb{Z}[\omega]$, so we can write $P_k(\omega) = a_k\omega + b_k$ for some integers $a_k,b_k$. Hence, \[ 3\omega = \sum_{k =1}^n(a_k\omega + b_k)^3 = \sum_{k = 1}^n\left(a_k^3 + b_k^3-3a_k^2b_k + \omega(3a_kb_k^2-3a_k^2b_k)\right).\]Note that $3\equiv 1\pmod{2}$ and $3a_kb_k^2 - 3a_k^2b_k \equiv a_kb_k - a_kb_k \equiv 0\pmod{2}$. Hence, in $\mathbb{F}_2[\omega]$, the above becomes \[ \omega = \sum_{k =1}^n (a_k^3 + b_k^3 - 3a_k^2b_k),\]which is absurd as the $a_k,b_k$ are integers. Hence $M = 3$ is impossible, as needed.