After trying serveral cases, I believe it should be (n-1)/3 for both parts, not (n+1)/3.

Sketch: Part a) If n satisfies, then 3n+4 also satisfies. Part b) Induction. We have f(3n+1,3m+2)=3f(n-1,m)+2, f(3n+2,3m+3)=3f(n,m+1) and f(3m+3,3n+1)=f(n+1,m+1)+2f(n,m), then we will prove a stronger statement: There exists a number m such that both f(n,m)<=(n-1)/3 and f(n+1,m+1)<=n/3, this is just induct, and we are done. Motivation for b): When n is divisible by 3, we have no choices but to prove the stronger statement.

Justanaccount wrote: After trying serveral cases, I believe it should be (n-1)/3 for both parts, not (n+1)/3. You are right!

Let $g(n,a)$ be the number of coefficients in the expansion of $(x+1)^a (x-1)^{n-a}$ that are NOT divisible by 3, and let $G(n)=\max\limits_{a=0}^n g(n,a)$. We know $g(n,a)=(n+1)-f(n,a)$ Part a) I will show there exists $a$ such that $f(n,a)=\frac{n-1}{3}$ $n=4,7$ both work. Rephrasing the problem, $G(n)=\frac{2n+4}{3}$ works, then $G(3n+4)=2n+4$, which solves the problem. If $a\equiv 2(\bmod\; 3)$, then we can compute $g(3n+4,a)$ as follows: $(x+1)^a (x-1)^{3n+4-a} = (x^2-1)^2 (x^3+1)^{\frac{a-2}{3}} (x^3-1)^{n-\frac{a-2}{3}}$ Note $(x^2-1)^2$ multiplies nicely with polynomial in $x^3$, so $g(3n+4,a)=3g(n,\frac{a-2}{3})$. Since $g(4,1)=4$, it follows that $g(16,5)=12, g(52,17)=36$,..., et cetera. Part b) We need to show $G(n)\ge \frac{2n+4}{3}$ We proceed by strong induction. The base cases can be verified by hand. We establish a recursion in g. Call $(n,k)$ good if $g(n,k)\ge \frac{2n+4}{3}$ Case 1: $n\equiv 2(\bmod\; 3)$. Pick $k$ such that $g(n,k)\ge \frac{2n+4}{3}$, which exists by our inductive hypothesis. $g(3n+2,3k)$: $(x+1)^{3k} (x-1)^{3(n-k)} (x-1)^{2} = (x-1)^{2} (x^3+1)^k (x^3-1)^{n-k}$ so $g(3n+2,3k)= 3g(n,k)=2n+4 > \frac{6n+8}{3}$ Similarly, $g(3n+2,3k+2)=3g(n,k)$ as well. Case 2: $n\equiv 1(\bmod\; 3)$, which is discussed in part a). Case 3: $3\mid n$. This case actually depends on the previous two cases. While doing induction for the previous two cases, there is an inner induction for this particular case. Replace $n$ with $3m+3$. $g(3m+3,3k+1)$: $(x+1)^{3k+1}(x-1)^{3(m-k)+2} \equiv (x+1)(x-1)^2 (x^3+1)^k (x^3-1)^{m-k} = (x^3-x^2-x+1)(x^3+1)^k (x^3-1)^{m-k} = (x^3+1)^{k+1}(x^3-1)^{m-k} - (x^2+x)(x^3+1)^k (x^3-1)^{m-k}$ Therefore, $g(3m+3,3k+1)=g(m+1,k+1)+2g(m,k)$. Here is the inner induction for this particular case. Similarly, $g(3m+3,3k+2)=g(3m+3, 3(m-k)+1)=g(m+1,m-k+1)+2g(m,m-k)=g(m+1,k)+2g(m,k)$ We need to show there exists $k$ such that $(m+1,k), (m,k)$ are both good. Subcase 1: $m$ is 1 mod 3. Let $m=3l+1$ Then we have $g(3l+1,3k'+2)=3g(l-1,k')$ and $g(3l+2,3k'+2)=3g(l,k')$, so this becomes the same subproblem. Subcase 2: $m$ is 0 mod 3. Let $m=3l$. Then we note $g(3l+1,3k'+2)=3g(l-1,k')$ and $g(3l,3k'+2)=g(l,k')+2g(l-1,k')$, reducing to a smaller subproblem. Subcase 3: $m$ is 2 mod $3$. Let $m=3l+2$ Then note $g(3l+2,3k'+2)=3g(l,k')$ and $g(3l+3,3k'+2)=g(l,k')+2g(l-1,k')$, reducing to a smaller subproblem. So this subproblem can be solved recursively as well. The end. Note: This writeup can be improved to showing the following claim: for any $n$ there exists $k$ st $(n,k), (n+1,k)$ is good. I will fix this tomorrow.

After a while, I decided to write my complete solution, here it is:

Attachments:
CHINA MO 2022 P6.docx (17kb)