Spring 2018, problem 69
Comments
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.
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.
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)$.
$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\}.$