Let $\lambda$ be a positive real number satisfying $\lambda=\lambda^{2/3}+1$. Show that there exists a positive integer $M$ such that $|M-\lambda^{300}|<4^{-100}$. Proposed by Evan Chen
Problem
Source: 2016 Taiwan TST Round 3
Tags: number theory
26.07.2016 01:41
This really looks like Dirichlet's approximation theorem
07.08.2016 11:33
weak dirichlet
07.08.2016 12:08
Dirichlet's approximation theorem ?
25.02.2017 17:23
Let $\alpha,\beta,\gamma$ be 3 complex roots of $t^3-t^2-1=0$. And $\alpha$ is real, the other two is conjugate complex numbers. Then $\lambda=\alpha^{3}$. So $\lambda^{300}=\alpha^{900}$. Note that $\alpha^{900}+\beta^{900}+\gamma^{900}$ is an integer. The original problem is equivalent to $|\beta^{900}+\gamma^{900}|<4^{-100}$ $\iff 2 \Re \beta^{900}<4^{-100}$ But we can prove $|\beta^9|<5^{-1}$. See here So we are done.
19.02.2019 10:26
Cute Problem: Note that $\lambda$ is a root of $P(X)=(X-1)^3-X^2=X^3-4X^2+3X-1$. It is easy to check that $P(X)$ has exactly one real root $\lambda$, and it is between $3$ and $4$. Let $\alpha,\bar{\alpha}$ be the other (complex) roots. We see that $|\alpha|^2\lambda=1$, so $|\alpha|=1/\sqrt{\lambda}$, so $1/2<|\alpha|<1/\sqrt{3}$. Let $x_n=\lambda^n+\alpha^n+\bar{\alpha}^n$. Note by Newton sums or whatever that $x_n$ is always an integer. Now, let $M=x_{300}$. We see that \[|M-\lambda^{300}|=|2\Re(\alpha^{300})|<2/3^{150}<4^{-100},\]as desired. $\blacksquare$
02.01.2021 21:00
How to do this without a calculator help Let $y = \lambda^{\frac{1}{3}}$, we have the equation $y^{3} - y^{2} - 1 = 0$. If $y$ was a real number, observe that $1.4^{3} - 1.4^{2} - 1 < 0$ but $1.5^{3} - 1.5^{2} - 1 > 0$, so $1.4 < y < 1.5$. I claim there are no other real solutions; for $y > 1.5$ then $y^{3} - y^{2} > 1$, for $-1 < y < 1.4$ we have $y^{3} - y^{2} < 1$, and for $y < -1$ we have $y^{3} - y^{2} < 1$. Thus, the $1.4<y<1.5$ is our only real solution. Let the two complex solutions be $z$ and $\overline{z}$. Since $z\overline{z} = |z|^{2}$, and the product of the roots is $1$, we have $|z|^{2} < \frac{1}{1.4} = \frac{5}{7}$. Consider the sum \[y^{900} + z^{900} + \overline{z}^{900}\]This is an integer since we can write it as the sum of symmmetric polynomials. Furthermore, observe that for any complex number $w$, we have $w + \overline{w} < 2|w|$, so \[z^{900} + \overline{z}^{900} < 2|z^{900}| < 2\cdot (\frac{5}{7})^{450} < 4^{-100}\]Thus, subtracting $z^{900} + \overline{z}^{900}$ from an integer results in $y^{900}$, which has a fractional part greater than $1 - 4^{-100}$, which proves the problem.
27.05.2022 09:33
Let $\lambda^{\frac 13}, r_1, r_2$ be the roots of $P(x)=x^3-x^2-1=0$. Note $P(x)$ has a unique real root because $P(x)>0$ for all $x<1$. We can see for $x\ge 1, P'(x)=3x^2-2x>0$. Therefore, $r_1, r_2$ are conjugates. We have $|r_1|^2=r_1r_2=\frac{1}{\lambda^{\frac 13}}$. We estimate $\lambda^{\frac 13}$. Note $P(\sqrt{2})=2\sqrt{2}-2-1<0$. Since $P$ is strictly increasing in $[1, \infty)$ it follows that $\lambda^{\frac 13}>\sqrt{2}$ Let $S_j=\lambda^{j/3}+r_1^j+r_2^j$. Observe $S_j-S_{j-1}-S_{j-3}=0$ and $S_0=3, S_1=0, S_2=-1, S_3\in \mathbb{Z}$. I claim $M=S_{900}$ works. We have $|M-\lambda^{300}|=|r_1^{900}+r_2^{900}|\le 2(|r_1|^{2})^{450} \le 2 (\frac{1}{\sqrt{2}})^{450} \le 2^{1-225} \le 4^{-100}$, as desired.
28.05.2022 22:21
At first place the $\lambda$ constant seems non-sense but to find a sense into it, u need to analyse the polynomial $P(x)=x^3-x^2-1$, the problem gives us that $\lambda^{\frac{1}{3}}$ is a root of $P$, now clearly $P(x)<0$ if $x<1$ so $\lambda>1$, now $P'(x)=3x^2-2x$ which means that $P$ is strictly increasing if $x>\frac{2}{3}$ and strictly decreasing if $x<\frac{2}{3}$ ,hence if $P$ had all of its roots real then all of these roots will be greater than $1$ but $P$ is strictly increasing so we cant have $3$ different values of $P$ being the same. Which means that $P$ has $1$ real root and $2$ complex roots. So let $P(\omega)=0$ and $P(\overline{\omega})=0$ be the complex roots of $P$ and now by Newton Sums we have that $\lambda^{300}+\omega^{900}+\overline{\omega}^{900}$ is an positive integer, now it remains to show that this is the $M$ we are looking for, so the problem is equivalent to showing that $|2 \cdot \text{Re}(\omega^{900})|<4^{-100}$, now let $\omega=a+bi$ then we need $2a^{900}<4^{-100}$, but by vieta's formulas we have that $a^2<a^2+b^2=\frac{1}{\lambda^{\frac{1}{3}}}$ so we need to bound $\lambda$, first lets try with the value $\sqrt{2}$, $P(\sqrt{2})=2^{\frac{3}{2}}-3<0$ becuase $8<9$ so $\lambda>2^{\frac{3}{2}}$ since $P$ is strictly increasing for all $x>\frac{2}{3}$ which means that $a^2<\frac{1}{\lambda}<4^{-\frac{3}{4}}$ and now taking the $450$-th power in both sides we get $a^{900}<4^{-\frac{1350}{4}}$ so $2a^{900}<4^{-\frac{1348}{4}}<4^{-100}$ and we are done
08.09.2023 17:38
Note that $\lambda^{1/3}$ is a real root of $x^3-x^2-1=0$. By Descartes' rule of signs, this root is unique and positive, and we can check that it is greater than $1.44$. Then by Vieta's this quadratic has two other complex roots $z,\overline{z}$ that are conjugates of each other, whose product is $1/\lambda^{1/3}$, hence the magnitude of these roots (which is the same for both) is at most $1/\sqrt{1.44}=1/1.2$. Then $1.2^9>5$, so the magnitudes of $z^{900}$ and $\overline{z}^{900}$ are at most $5^{-100}$, so their sum has magnitude less than $4^{-100}$. On the other hand, $\lambda^{300}+z^{900}+\overline{z}^{900}$ is an integer, hence $\lambda^{300}$ is within $4^{-100}$ of some integer. $\blacksquare$