What a cool problem! Suppose $ f(x) = a_n x^n + a_{n - 1} x^{n - 1} + \ldots + a_0$. Note that if we divide $ f$ by $ x - 1$, we get $ \frac {f(x)}{x - 1} = a_n x^{n - 1} + (a_n + a_{n - 1}) x^{n - 2} + (a_n + a_{n - 1} + a_{n - 2}) x^{n - 3} + \ldots + (a_n + a_{n - 1} + \ldots + a_1) + \frac {a_n + a_{n - 1} + \ldots + a_0}{x - 1}.$ That is, the coefficients become partial sums. Then by induction, we can show that for any positive integer $ p$, $ \frac {f(x)}{(x - 1)^p} = \sum_{i = 0}^{n - p} \left( \sum_{j = i + p}^n \left( {j \choose p - 1} a_j \right) x^i \right) + \frac {R(x)}{(x - 1)^p},$ for some remainder polynomial $ R(x)$ of degree less than $ p$. If $ f(x)$ has $ 1$ as root with at least $ k$ multiplicity, $ R(x) = 0$ and $ \frac {f(x)}{(x - 1)^p}$ is a polynomial. Let $ g_p(x) = \frac {f(x)}{(x - 1)^p}$. Then as long as $ 1$ is a root of $ f$ with multiplicity at least $ p$, Hockeystick gives that $ g_p(1) = {n \choose p} a_n + {n - 1 \choose p} a_{n - 1} + \ldots + {0 \choose p} a_0 = 0. \quad (\ast )$ This equation is true for all $ 0 \leq p \leq m - 1$, since $ g_p(1) = 0$ for those values. Lemma: For positive integers $ n$, $ {n \choose 2^k - 1}$ is odd if and only if $ 2^k \mid n + 1$. Proof: The base 2 representation of $ 2^k - 1$ is $ 111\ldots1$ with $ k$ $ 1$s. Suppose $ n$ has binary representation $ d_m d_{m - 1} \ldots d_1$. By Lucas's Theorem, $ {n \choose 2^k - 1} \equiv {d_m \choose 0} {d_{m - 1} \choose 0} \cdots {d_k \choose 1} {d_{k - 1} \choose 1} \cdots {d_1 \choose 1} \pmod{2}.$ For this to be odd all the binomial coefficient factors on the right side must be $ 1$. Thus it is required $ d_k = d_{k - 1} = \ldots = d_1 = 1$, equivalent to $ n = 2^k p + 2^k - 1$ for some nonnegative integer $ p$. That's one direction. Also note $ d_m, d_{m - 1} \ldots d_{k + 1}$ can be anything for the remaining binomial coefficients to evaluate to $ 1$, so $ p$ can be arbitrary and $ n + 1$ can be any multiple of $ 2^k$. This shows the other direction. Suppose $ m \geq 2^k$. Also suppose $ n < 2^{k + 1} - 1$, so that $ 2^a \leq n < 2^{a + 1} - 1$ for some $ 0 \leq a \leq k$. Take $ p = 2^a - 1$ (which is always at most $ m$) in $ (\ast )$ and consider it mod $ 2$. Since $ a_i \equiv 1 \pmod{2}$ for all $ i$, this becomes $ g_{2^a - 1}(1) \equiv {n \choose 2^a - 1} + {n - 1 \choose 2^a - 1} + \ldots + {0 \choose 2^a - 1} \equiv 0. \pmod{2} \quad (\ast \ast ).$ By the lemma, the only odd terms in the sum are of the form $ {2^a p - 1 \choose 2^a - 1}$ for some positive integer $ p$. But since $ 2^a \leq n < 2^{a + 1} - 1$, the only term of this form is $ {2^a - 1 \choose 2^a - 1}$, since the next one would have $ 2^{a + 1} - 1$ on top which is greater than $ n$. Thus there is exactly one odd term in that summation, and so the whole thing must be odd. But we have it is equivalent to $ 0 \pmod{2}$. Contradiction! Thus $ n \geq 2^{k + 1} - 1$.

MellowMellon, your formula for $ \frac {f\left(x\right)}{\left(x - 1\right)^p}$ alone is way cooler than this trivial problem. The problem has nothing to do with $ \pm 1$'s, it is enough that all coefficients of $ f$ are odd. This yields that the reduction $ \overline{f}$ of $ f$ modulo $ 2$ equals to the polynomial $ x^n + x^{n - 1} + ... + x + 1\in\mathbb{F}_2\left[x\right]$. On the other hand, $ 1$ as an $ m$-fold root of $ f$ yields $ \left(x-1\right)^m\mid f\left(x\right)$ (as polynomials in $ \mathbb{Q}\left[x\right]$, and thus also in $ \mathbb{Z}\left[x\right]$, because $ \left(x - 1\right)^m$ is a monic polynomial), so that $ \left(x-1\right)^{2^k}\mid f\left(x\right)$ (since $ m\geq 2^k$ leads to $ \left(x-1\right)^{2^k}\mid \left(x-1\right)^m$). Thus, so that $ f\left(x\right) = \left(x - 1\right)^{2^k}g\left(x\right)$ for another polynomial $ g\left(x\right)\in\mathbb{Z}\left[x\right]$. Reducing modulo $ 2$, this yields $ x^n + x^{n - 1} + ... + x + 1 = \left(x - 1\right)^{2^k}\overline{g}\left(x\right)$ in $ \mathbb{F}_2\left[x\right]$. But $ \left(x - 1\right)^{2^k} = x^{2^k} - 1$ in $ \mathbb{F}_2\left[x\right]$, so this becomes $ x^n + x^{n - 1} + ... + x + 1 = \left(x^{2^k} - 1\right)\overline{g}\left(x\right)$. Hence, $ \deg\overline{g}\geq 2^k - 1$ by comparison of coefficients (otherwise, the left hand side would be a polynomial with coefficient $ 1$ before $ x^{2^k - 1}$, but the right hand side would be a polynomial with coefficient $ 0$ before $ x^{2^k - 1}$). Thus, $ \deg g\geq 2^k - 1$, and the rest is clear. I have no idea what is the point of such a problem as a third problem of a Chinese TST (even a quiz). darij

darij grinberg wrote: I have no idea what is the point of such a problem as a third problem of a Chinese TST (even a quiz). Dear darij, you will see the very point after seeing the previous two questions of the quiz. In fact in day 3 the students did far worse than expected (the couches' words).

In fact, I think in general you must have $ n \ge 2m-1$, so the powers of 2 are irrelevant.

Hm... Why don't you post a proof? Addendum (more than two years later!): MellowMelon's proof may be shortened by noting that 1) the hypothesis that $x-1$ divides $f^{(p)}$ is enough to derive $(*)$ and 2) the lemma may be proved using the fact that $\binom{n+1}{2^k}=\frac{n+1}{2^k}\binom{n}{2^k-1}$ (or at least the lemma's relevant implication). Second addendum: I have partially answered my own question, use darij's approach. If $(x-1)^m$ is a factor of $1+x+\ldots+x^n$, then it is also a factor of $x^{n+1}-1$. It is then easy to see, considering the algebraic closure of $\mathbb F_2$, that each root of $x^{n+1}-1$ has multiplicity at least $m$. If there are two such roots, then $n+1\geq 2m$, as we required. Else $x^{n+1}-1=(x-1)^{n+1}$, which implies $n+1$ is a power of $2$. However, this is all we can get working in $\mathbb F_2$, since $(x-1)^m$ divides $(x-1)^{n+1}$ whenever $m\leq n+1$.

The solution of this problem and some others in China TST can be found here

Attachments:
AT_2009_Mocks_Solutions.pdf (345kb)

Consider the algebraic closure $\bar{F_2}$ of the field $F_2$. We work in $F_2[X]$ and see that $f=x^n+\dots +x+1=\frac{X^{n+1}-1}{X-1}$. Moreover, by Frobenius we have $(X-1)^{2^k}=X^{2^k}-1$. Let $\alpha$ be a root of the cyclotomic polynomial $\phi_{2^k}(X)$ in $\bar{F_2}$. We see that the cyclotomic polynomial is a factor of $X^{2^k}-1$ and so $(X-1)^{2^k}$ vanishes at $\alpha$. Therefore, we have $\alpha^{n+1}=1$ and since the order of $\alpha=2^{k}$, we deduce that $2^k \mid n+1$. Now, clearly, comparing degree gives that $n \ge m \ge 2^k$. Therefore, $n+1\ge 2\cdot 2^k$ and the conclusion holds.

Comment: much more is true. https://www.komal.hu/verseny/feladat.cgi?a=feladat&f=A532&l=en

feliz wrote: Hm... Why don't you post a proof? Second addendum: I have partially answered my own question, use darij's approach. If $(x-1)^m$ is a factor of $1+x+\ldots+x^n$, then it is also a factor of $x^{n+1}-1$. It is then easy to see, considering the algebraic closure of $\mathbb F_2$, that each root of $x^{n+1}-1$ has multiplicity at least $m$. If there are two such roots, then $n+1\geq 2m$, as we required. Else $x^{n+1}-1=(x-1)^{n+1}$, which implies $n+1$ is a power of $2$. However, this is all we can get working in $\mathbb F_2$, since $(x-1)^m$ divides $(x-1)^{n+1}$ whenever $m\leq n+1$. Let me explain probability1.01's claim-for this you really need the coefficients are $\pm 1$ rather than just being odd. (With only odd coefficients, as people explained above by mod $2$ one can show $v_2(n+1)\geq\log_2{(m+1)}$ and thus $n\geq 2^{\lceil\log_2{(m+1)}\rceil}-1$. This estimate is sharp and $m=2^k\Rightarrow n\geq 2^{k+1}-1$ happens to be its most powerful case.) By MellowMelon's method or simply taking formal derivatives we can get his equations (*): \[\sum_{k=0}^n f(k)a_k=0\]for $f(x)=\binom{x}{0},\binom{x}{1},...,\binom{x}{m-1}$ and hence also for any polynomial of degree $\leq m-1$. In particular we have \[\sum_{k=0}^n k^la_k=0,0\leq l\leq m-1.\]Let $S=\{k|a_k=1\},T=\{k|a_k=-1\}$, then once $m\geq 1$ we have $|S|=|T|=\frac{n+1}{2}$ and \[\sum_{i\in S}i^l=\sum_{j\in T}j^l,1\leq l\leq m-1.\]As $S\neq T$ we must have $m\leq\frac{n+1}{2},n\geq 2m-1$. Remark: by this method we get if $f(x)\in\mathbb{Z}[x]$ is a nonzero multiple of $(x-1)^m$, then the sum of its positive coefficients $\geq m$.

Fang-jh wrote: Let $ f(x)$ be a $ n -$degree polynomial all of whose coefficients are equal to $ \pm 1$, and having $ x = 1$ as its $ m$ multiple root. If $ m\ge 2^k (k\ge 2,k\in N)$, then $ n\ge 2^{k + 1} - 1.$ The problem basicaly says that $(x-1)^{2^k} \mid f(x)$ and now we work on $\mathbb F_2$. On $\mathbb F_2$ we have that $f(x)=\frac{x^{n+1}-1}{x-1}$ and $(x-1)^{2^k}=x^{2^k}-1$ hence the divisibility condition can be re-writen as $x^{2^k}-1 \mid x^{n+1}-1 \implies 2^k \mid n+1$ but since by the first divisibility condition get $n \ge 2^k$ we have that $n \ge 2^{k+1}-1$ thus we are done

Considering the problem in $\mathbb{F}_2[x],$ we see $f(x)=x^n+x^{n-1}+\dots+1.$ Notice $(x+1)^{2^k}=x^{2^k}+1$ (induction) divides $f,$ so $$(x^{2^k}+1)g(x)=x^n+x^{n-1}+\dots+1.$$If $n<2^{k+1}-1,$ then $\deg g\le 2^k-2.$ Hence, there is no $x^{2^k-1}$ term on the LHS while there is one on the RHS since $n\ge 2^k,$ so we have a contradiction. $\square$