# Spring 2018, problem 69

It is known that $k$ and $n$ are positive integers and $k + 1\leq\sqrt {\frac {n + 1}{\ln(n + 1)}}.$ Prove that there exists a polynomial $P(x)$ of degree $n$ with coefficients in the set $\{0,1, - 1\}$ such that $(x - 1)^{k}$ divides $P(x)$.

lucianosantos
3 years ago

$n$ is greater than $k$ such that we can choose a set $S$ of $k$ positive integers, $p_{{i}}$, so that:

i) $\displaystyle\sum_{i=1}^{k} p_i=n$.

ii) Given any two subsets $A$ and $B$ of $S$, the sum of the elements of $A$ is different from the sum of the elements of $B$. If $A$ or $B$ have a single element consider the "sum" as being this element.

Then the polynomial $P(x)=\displaystyle\prod_{i=1}^{k} (x^{p_{i}}-1)=(x-1)^{k}\times Q(x)$ is one of the requested polynomials.

Note:Condition (ii) is a sufficient condition but not necessary for the polynomial to have coefficients in the set $\{0,-1,1\}$. Example: Consider $k=3$, $n=70$ and $S=\{1,34,35\}$.

We have $1+34=35$, and the polynomial $p(x)=(x-1)(x^{34}-1)(x^{35}-1)=(x-1)^{3}Q(x)=x^{70}-x^{69}-x^{36}+x^{34}+x-1$ has coefficients in the set $\{1,-1,0\}.$

There may not be a set of numbers satisfying your two conditions. That any pair of distinct subsets have different sums is a stringent condition. i dont think you can do it with say k=30 and n=10000.

JiazhenTan 3 years ago

Thank you, you're right, the proof is wrong.

If the problem were this: "For every $k$ there is at least one $n$ such that ,,," but outside the context of inequality, I think the arguments I presented were correct.

lucianosantos 3 years ago
chorgeshashank007
3 years ago

Can anybody re write the problem? Latex thing is not showing properly

I think the problem is :

It is known that $k$ and $n$ are positive integers and $k + 1\leq\sqrt {\frac {n + 1}{\ln(n + 1)}}$.Prove that there exists a polynomial $P(x)$ of degree $n$ with coefficients in the set $\{0,1,−1\}$ such that $(x−1)^{k }$ divides $P(x)$.

lucianosantos 3 years ago