Let $1<t<2$ be a real number. Prove that for all sufficiently large positive integers like $d$, there is a monic polynomial $P(x)$ of degree $d$, such that all of its coefficients are either $+1$ or $-1$ and $$\left|P(t)-2019\right| <1.$$Proposed by Navid Safaei
Problem
Source: Iranian TST 2019, second exam day 2, problem 4
Tags: algebra, polynomial
24.06.2019 18:20
Let $P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots +a_1x+ a_0$. Consider the sequence $(a_n,a_{n-1},\dots a_0)$ where $a_i\in \{-1,1\}$ and arrange all possible such $n+1$-tupples in lexicographical order. Then put $x=t$ and calculate each value. We obtain a sequence of real numbers starting from $-M$ and ending with $M$ where $M:=t^n+t^{n-1}+\dots +t+1$. Clearly $M>2019$ for sufficiently large $n$. Every next number is either larger than the previous one but with step at most $2$ or is less than the previous number. Thus, there is a moment when $|P(t)-2019|\leq 1$. But, the cases when the sequence jumps with $2$ are very special, and it can be seen we actually can arrange $|P(t)-2019|< 1$.
25.06.2019 05:49
dgrozev wrote: Let $P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots +a_1x+ a_0$. Consider the sequence $(a_n,a_{n-1},\dots a_0)$ where $a_i\in \{-1,1\}$ and arrange all possible such $n+1$-tupples in lexicographical order. Then put $x=t$ and calculate each value. We obtain a sequence of real numbers starting from $-M$ and ending with $M$ where $M:=t^n+t^{n-1}+\dots +t+1$. Clearly $M>2019$ for sufficiently large $n$. Every next number is either larger than the previous one but with step at most $2$ or is less than the previous number. Thus, there is a moment when $|P(t)-2019|\leq 1$. But, the cases when the sequence jumps with $2$ are very special, and it can be seen we actually can arrange $|P(t)-2019|< 1$. Why "Every next number is either larger than the previous one but with step at most $2$ or is less than the previous number"?
25.06.2019 12:03
In case $(a_n,a_{n-1},\dots,a_0)=(\dots,-1)$ , the next $n+1$-tuple is $(\dots,1)$ so we jump with step $2$ and it's the only case the step is $2$. Suppose $(a_n,a_{n-1},\dots,a_0)=(\dots,-1,1,\dots,1)$ , where the last $-1$ is at the $k$-th position from right to left (the rightmost position is $0$). The next tuple is $(\dots,1,-1,\dots,-1)$. Thus the difference between the two values when put $t$ in the corresponding polynomials equals $\displaystyle(t^k-t^{k-1}-\dots-1)-(-t^k+t^{k-1}+\dots+1)=2t^k-2\frac{t^k-1}{t-1}=2\cdot\frac{1-t^k(2-t)}{t-1}$. Denote $A=t^k$ (obviously $A>1$) and consider $\displaystyle f(x):=2\cdot\frac{1-A(2-x)}{x-1}, x\in(1,2)$. An easy calculation shows $f'(x)=2\frac{A-1}{(x-1)^2}>0$. It means $f(x)$ is increasing in the interval $(1,2)$. Since $\displaystyle \lim_{x\to 1,x>1}f(x)=-\infty$ and $f(2)=2$ it follows $f(x)<2,\forall x\in(1,2)$. Hence, the step is at most $2$ and it equals $2$ only when $a_0$ jumps from $-1$ to $1$.
19.07.2019 12:15
dgrozev wrote: Let $P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots +a_1x+ a_0$. Consider the sequence $(a_n,a_{n-1},\dots a_0)$ where $a_i\in \{-1,1\}$ and arrange all possible such $n+1$-tupples in lexicographical order. Then put $x=t$ and calculate each value. We obtain a sequence of real numbers starting from $-M$ and ending with $M$ where $M:=t^n+t^{n-1}+\dots +t+1$. Clearly $M>2019$ for sufficiently large $n$. Every next number is either larger than the previous one but with step at most $2$ or is less than the previous number. Thus, there is a moment when $|P(t)-2019|\leq 1$. But, the cases when the sequence jumps with $2$ are very special, and it can be seen we actually can arrange $|P(t)-2019|< 1$. Can you write the detail of how “we actually can arrange $|P(t)-2019|< 1$.[/quote]”, I can do $|P(t)-2019|\leq 1$, but less than 1 is not very easy.
16.08.2019 16:13
Or simply, $2(t^k - t^{k-1} - ... - 1) = 2+2(t-2)(t^{k-1} + ... +1) \le 2$.
20.10.2019 17:35
As L.Bill commented, dgrozev's proof cannot exclude the case where $|P(t)-2019|=1$. But this can be improved by simple modification. When using dgrozev's Lexicographic idea, discard constant term for $Q$. Then we will find $Q$ such that $|Q(t)-2019|\le t$. Then we can appropriately add constant term $\pm1$ and make $P$ so that $|P(t)-2019|<1$. Again we only need $d$ to be natural number so that $t^d + ... + t>2019$, so the problem is solved.
21.10.2019 06:12
bumjoooon wrote: Then we can appropriately add constant term $\pm1$ and make $P$ so that $|P(t)-2019|<1$. What if $|Q(t)-2019|=0$ ?
21.10.2019 15:52
liekkas wrote: bumjoooon wrote: Then we can appropriately add constant term $\pm1$ and make $P$ so that $|P(t)-2019|<1$. What if $|Q(t)-2019|=0$ ? OMG.. I need to fix once more.
13.03.2020 11:06
bumjoooon wrote: Or simply, $2(t^k - t^{k-1} - ... - 1) = 2+2(t-2)(t^{k-1} + ... +1) \le 2$. I think that if $k$ gets bigger, $2(t^k - t^{k-1} - ... - 1)$ will be a negative number. This can be a problem because its absolute value can be bigger that 2.
01.04.2020 09:57
Mathhunter1 wrote: bumjoooon wrote: Or simply, $2(t^k - t^{k-1} - ... - 1) = 2+2(t-2)(t^{k-1} + ... +1) \le 2$. I think that if $k$ gets bigger, $2(t^k - t^{k-1} - ... - 1)$ will be a negative number. This can be a problem because its absolute value can be bigger that 2. Nope. It's not the problem. We only need to prove that the maximal decreasing amount is $2$, not the difference.
01.04.2020 16:57
Wow! I tried to proof $\left|P(t)-2019\right| <1$. But as you said, proofing $\left|P(t)-2019\right| <1$ is very hard. Then, is this question wrong?