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)$.

Comments

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