For every positive integer $k>1$ prove that there exist a real number $x$ so that for every positive integer $n<1398$: $$\left\{x^n\right\}<\left\{x^{n-1}\right\} \Longleftrightarrow k\mid n.$$ Proposed by Mohammad Amin Sharifi
Problem
Source: Iranian TST 2020, second exam day 2, problem 5
Tags: fractional part, algebra, Divisibility
14.03.2020 06:19
Tough to perfectly formulate it. Note that $k=1$ is also possible for general $n$. (just take $x=0.5$.)
03.11.2020 05:06
Solved with nukelauncher and Th3Numb3rThr33. Let \(N\) be a very large (odd) prime, and vary an integer \(m\): select \[x=m+\frac1N.\]I claim that for any sequence \(a_2\), \(a_3\), \ldots, \(a_t\) of nonnegative integers less than \(N\), it is possible to choose \(m\pmod{N^{t-1}}\) so that \(\{x^n\}\in\left(\frac{a_n}N,\frac{a_n+1}N\right]\) for \(n\le t\). We prove this by iterating through \(t\), with initial condition \(t=1\) trivial. Now observe that \[x^t\equiv\left[\frac1{N^t}\right]+\frac{\binom t1m}{N^{t-1}}+\left[\frac{\binom t2m^2}{N^{t-2}}+\cdots+\frac{\binom ttm^t}{N^0}\right]\pmod1.\]Since \(m\) is fixed modulo \(N^{t-2}\), the values of the boxed terms have all been determined already; the only variable term is \(\frac{tm}{N^{t-1}}\). Every time we increase \(m\) by \(N^{t-2}\), we increase \(\frac{tm}{N^{t-1}}\) by \(\frac1N\), so we can select \(\{x^t\}\) accurately to the nearest \(\frac1N\). The claim readily follows. The conclusion follows from here by taking \(a_n=(n-1)\bmod k\) for \(n\le1398\).
10.04.2021 04:37
Let $1-\{a_p\}>\epsilon>0$. Consider a sequence $a_1,a_2,...,a_p$. We say that an interval $[b,c]$ is good if there for all $d\in [b,c]$ we have $$0<\{d^k\}-\{a_k\}<\epsilon \hspace{20pt}(1)$$for all $1\leq k\leq p$ and $$\{b^k\}=a_p,\{c^k\}=a_p+0.99\epsilon \hspace{20pt}(2)$$Claim. For every sequence there exists arbitrarily large good interval. Proof. We proceed by induction on $p$. The case $p=1$ is obvious. Now suppose all smaller cases hold let's consider the case $p$. We will show that every sufficiently large good interval for the sequence $a_1,a_2,...,a_{p-1}$ will contain a good subinterval for the sequence $a_1,...,a_p$. Indeed, suppose $[b,c]$ is a good interval for the sequence $a_1,a_2,...,a_{p-1}$. consider the interval $I=[b^{k+1},c^{k+1}]$. Notice that $c^k-b^k>0.99\epsilon$, hence $$c^{k+1}-b^{k+1}>(a+0.99\epsilon)^{\frac{k+1}{k}}-a^{\frac{k+1}{k}}$$where $a=b^k$. Notice that as $b$ tends to infinity $a$ tends to infintiy as well, and hence this expression tends to infinity. Now obviously any subinterval of $[b,c]$ also satisfy $(1)$, so it suffices to find an subinterval which also satisfies $(2)$. We pick $b,c$ sufficiently large such that the length of $I$ exceeds $2$. Then both the number $$b'=\lceil b \rceil +\{a_p\}\text{ and } c'=\lceil c\rceil+\{a_p\}+\epsilon$$will be in $b,c$. Hence $[b',c']$ will be a good interval for $a_1,...,a_p$ as desired. $\blacksquare$ We return to the original problem. Applying the lemma with $n=1398$, $a_k=\frac{k}{n}$, and a small $\epsilon$, we will have a good interval $[b,c]$. Using this, we can see that given $d\in[b,c]$, the sequence $d_n=\{d^n\}$ satisfies $$\{d^n\}-\{\frac{k}{n}\}<\epsilon$$hence we can just take $x=d$ as desired.
29.08.2022 11:41
can't really understand these solutions
22.02.2023 05:24
TheUltimate123 wrote: Solved with nukelauncher and Th3Numb3rThr33. Let \(N\) be a very large (odd) prime, and vary an integer \(m\): select \[x=m+\frac1N.\]I claim that for any sequence \(a_2\), \(a_3\), \ldots, \(a_t\) of nonnegative integers less than \(N\), it is possible to choose \(m\pmod{N^{t-1}}\) so that \(\{x^n\}\in\left(\frac{a_n}N,\frac{a_n+1}N\right]\) for \(n\le t\). We prove this by iterating through \(t\), with initial condition \(t=1\) trivial. Now observe that \[x^t\equiv\left[\frac1{N^t}\right]+\frac{\binom t1m}{N^{t-1}}+\left[\frac{\binom t2m^2}{N^{t-2}}+\cdots+\frac{\binom ttm^t}{N^0}\right]\pmod1.\]Since \(m\) is fixed modulo \(N^{t-2}\), the values of the boxed terms have all been determined already; the only variable term is \(\frac{tm}{N^{t-1}}\). Every time we increase \(m\) by \(N^{t-2}\), we increase \(\frac{tm}{N^{t-1}}\) by \(\frac1N\), so we can select \(\{x^t\}\) accurately to the nearest \(\frac1N\). The claim readily follows. The conclusion follows from here by taking \(a_n=(n-1)\bmod k\) for \(n\le1398\). It's a really nice solution as I first try m=1 and it turned out that we need to change m in order to keep the second one quite small~