We call a positive integer $q$ a $convenient \quad denominator$ for a real number $\alpha$ if $\displaystyle |\alpha - \dfrac{p}{q}|<\dfrac{1}{10q}$ for some integer $p$. Prove that if two irrational numbers $\alpha$ and $\beta$ have the same set of convenient denominators then either $\alpha+\beta$ or $\alpha- \beta$ is an integer.
Problem
Source: IZhO 2016 Day 2 P6
Tags: number theory, irrational number
16.01.2016 11:59
By Farey series property there exist single convenient denominator $q$ such that $q\leq 9$.
17.01.2016 07:22
By Dirichlet's approximation formula There are infinitely many convinient denominator $q$ , such that $q\ge 10$
18.03.2016 12:09
A sketch: Rewrite the condition into distance of $q\alpha$ to the nearest integer is at most $\frac{1}{10}$. Now it is easy to see that we can add such numbers together and if the distance is still at most $\frac{1}{10}$, it remains convenient. First, note that if $| q\alpha - p | < \frac{1}{10k}$ then $kq$ is still convenient. So we must have $| q\beta - r| < \frac{1}{10k}$ else $kq\beta$ will be more than $\frac{1}{10}$ away from the nearest integer. This will give us that $\frac{1}{m+10} < q\alpha, q\beta, < \frac{1}{m}$ for some natural $m$. For convenience we will denote $||x||$ as the distance to the nearest integer. Now by Dirichlet approximation theorem, there are infinitely many $q$ such that $||q\alpha|| < \frac{1}{q}$ and hence $||q\beta|| < \frac{1}{q-10}$ too. Now WLOG let there be infinitely many such that both $q\alpha$ and $q\beta$ are greater than its nearest integer. (The other cases are similar). Now take one of these $q$, say $q_1$ and consider another large $q_2$. We have that $(q_1 + kq_2)$ is convenient for $\alpha$ for $k$ in some interval and thus will be for $\beta$. However if $q_1\alpha$ is different from $q_1\beta$, say if it was larger, it is then easy to check that if we choose $q_2$ sufficiently large, there is some $k$ that will make $||(q_1 + kq_2)\alpha|| > \frac{1}{10}$ but $||(q_1 + kq_2)\beta|| < \frac{1}{10}$ - a contradiction. This is possible as the worst case will be when $||q_2\alpha|| = \frac{1}{c+10}, ||q_2\beta|| = \frac{1}{c}$ and hence to keep $(q_1 + kq_2)$ convenient for $\beta$, we need $c(\frac{1}{10} - ||q_1\beta||) > k$ while to make it not convenient for $\alpha$, we need $(c+10)(\frac{1}{10} - ||q_2\alpha||) < k$. So we just need $c(\frac{1}{10} - ||q_1\beta||) > (c+10)(\frac{1}{10} - ||q_1\alpha||) + 1$ which reduces to $c(||q_1\alpha|| - ||q_1\beta||) > 2 - 10||q_1\alpha||$, clearly possible for $c$ large enough. Hence we must have $q_1\alpha = p_1 + r$, $q_1\beta = p_2 + r$ where $p_1,p_2$ are naturals. This gives us $\alpha - \beta = \frac{p_1 - p_2}{q_1}$ which is rational. Other cases such as there are infinitely many such that $q\alpha$ is less while $q\beta$ is more than their nearest integers will give us $\alpha + \beta$ rational instead. To get from rational to integer, note that it suffices to find two convenient coprime $q_1,q_2$ since then we will have $\frac{a}{q_1} = \frac{b}{q_2}$ where $a,b$ are naturals, implying that $q_1|a$ and $q_2|b$. To do this, choose a large $q$ which gives us $||q\alpha|| < \frac{1}{q}$. Now take some $r$ coprime to $q$ and consider $||(r+kq)\alpha||$ where we vary $k$. For some $k$, this must be less than $\frac{1}{10}$ since it increases by less than $\frac{1}{q}$ each time we increase $k$. Finally just note that $r+kq$ and $q$ are coprime.
27.01.2017 07:41
Is there a more easier solution? Well i solved this with a easier solution using elementary algebra
04.05.2017 04:40
ISHO95 wrote: By Dirichlet's approximation formula There are infinitely many convinient denominator $q$ , such that $q\ge 10$ Sorry for this bump, but can you tell more further about how to use this ?
05.05.2017 05:29
He didn't say that the problem can be completed using that. Most likely he posted it as a fact that could potentially be useful to the problem. (but it isn't actually )
06.05.2017 11:06
fattypiggy123 wrote: He didn't say that the problem can be completed using that. Most likely he posted it as a fact that could potentially be useful to the problem. (but it isn't actually ) Hello, my teacher when i tell about this about problem, he say that we can both use this lemma and the Farey sequence
06.01.2019 15:07
fattypiggy123 wrote: First, note that if $| q\alpha - p | < \frac{1}{10k}$ then $kq$ is still convenient. So we must have $| q\beta - r| < \frac{1}{10k}$ else $kq\beta$ will be more than $\frac{1}{10}$ away from the nearest integer. Why must we have this? The condition $| q\beta - r| < \frac{1}{10k}$ is equivalent to $| kq\beta - kr| < \frac{1}{10}$, but here we have a distance not to the nearest integer, but to the nearest integer divisible by $k$.
20.12.2020 12:40
When the only info on $\alpha$ and $\beta$ is given in $``q"$s, then ... work in $``q"$s! (The official Solution doesn't, though.) Obviously, we can WLOG assume that $0 < \alpha,\beta < 1$. Call a convenient denominator $q \in \mathbb{N}$ to be $\textit{right-winged}$ with respect to $r$ if $0 < \{qr\} < \dfrac{1}{10}$ and call it $\textit{left-winged}$ if $\dfrac{9}{10} < \{qr\} < 1.$ It is easy (by multiplying $q$ to the given expression) to verify that a convenient denominator is either $\textit{left-winged}$ or $\textit{right-winged}$. $\color{green} \rule{25cm}{3pt}$ $\color{green} \textbf{\text{Problem Shrinking: Part 1.}}$ There cannot be two convenient denominators $q_1$ and $q_2$ so that $q_1$ is $\textit{left-winged}$ and $q_2$ is $\textit{right-winged}$ with respect to $\alpha$, and $q_1$ and $q_2$ are similarly-winged with respect to $\beta$ $\color{green} \textbf{\text{Proof 1.}}$ WLOG $q_1$ and $q_2$ are both right-winged w.r.t. $\beta$. For an easier notation, let $ 1-\{q_1 \alpha \}$ be $\alpha_1$ and $ \{q_2 \alpha \}$ be $\alpha_2$. This whole proof will establish contradictions by using $q_1$ and $q_2$ as additive bases, of which its fractional part behaves nicely when added. Firstly, we will construct an infinite sequence $\{a_i\}$ and $\{b_i\}$, $i\geq 1$, so that $a_1 = 1$ and $b_1 = 0$, $(a_{i+1},b_{i+1})$ is equal to either $(a_i+1,b_i)$ or $(a_i,b_i+1)$, and finally $a_i \cdot q_1 + b_i \cdot q_2$ is a convenient denominator. This is not hard to verify inductively; when \[0 < \{a_k \cdot q_1 + b_k \cdot q_2\} < \dfrac{1}{10}\]just pick $a_{k+1} = a_k+1$ and $b_{k+1} = b_k$, and when the value of $\{a_k \cdot q_1 + b_k \cdot q_2\}$ is greater than $\dfrac{9}{10}$, just pick $(a_{k+1},b_{k+1})$ to be the other possibility. However, following that construction, we know that $a_N \cdot q_1+b_N \cdot q_2$ is also a convenient denominator of $\beta$, which implies that \[ \{ a_N \cdot q_1 \beta + b_N \cdot q_2 \beta \} \]to be less than $\dfrac{1}{10}$ or more than $\dfrac{9}{10}$ at all times. However, easy analysis shows that once that value is greater than $\dfrac{1}{10}$, which must inevitably happen, that value will be less than $\dfrac{1}{5}$. $\blacksquare$ $\color{blue} \rule{25cm}{1pt}$ $\color{blue} \textbf{\text{Problem Shrinking: Part 2.}}$ Here we eliminate the case $\alpha+\beta = 1$, and we further claim that for each $N$, \[ \dfrac{1}{10(N+1)} < \{q \alpha \} < \dfrac{1}{10N} \ \Leftrightarrow \ \dfrac{1}{10(N+1)} < \{q \beta \} < \dfrac{1}{10N} \]$\color{blue} \textbf{\text{Explanation.}}$ By $\color{green} \textbf{\text{Part 1}}$, if the set of right-winged denominators of $\alpha$ is $S_R(\alpha) = \{q_1,q_2,\ldots \}$, then all of those must be similarly-winged denominators of $\beta$, or else some $q_i$ belongs to $S_R(\beta)$ and some $q_j$ belongs to $S_L(\beta)$ --- which is impossible. If $S_R(\alpha) = S_L(\beta)$, then $S_R(\alpha) = S_R(1-\beta)$. So, if we can prove that $S_R(a) = S_R(b)$ implies $a = b$ (assuming $0< a,b <1$, of course) then we are done, since we can get either $\alpha = \beta$ or $\alpha = 1 - \beta$. $\color{blue} \rule{25cm}{0.5pt}$ Divide the convenient denominators to be of type-$N$ when it satisfies the first inequality above. Now note that since $\{ q\alpha \} \not\in \mathbb{Q}$, its type is uniquely defined. Now we will prove that it also satisfies the second inequality, which ensures that its type is consistently defined whether we base it off $\alpha$ or $\beta$. FTSOC let $q$ to be type-$M$ on $\beta$, and WLOG $M>N$. Then, $(N+1)q$ is not a convenient denominator of $\alpha$, while it is a convenient denominator of $\beta$, as \[ \dfrac{N+1}{10(N+1)}< \{(N+1)q \alpha\} < \dfrac{N+1}{10N} < \dfrac{1}{5}, \, \text{and} \, \{ (N+1)q \beta \} < \dfrac{N+1}{10M} \]$\blacksquare$ $\color{red} \rule{25cm}{2pt}$ $\color{red} \textbf{\text{HD-fying the definitions.}}$ Note that since $\{ q\alpha\}$ is dense, then there is a type-$N$ denominator for each $N$. Now let there be a convenient denominator $q$ which makes $\{q \alpha\} \ne \{q \beta \}$ --- if there isn't, then $\alpha - \beta = \dfrac{a}{b}$, and then we can just pick $q = k \cdot b+1$ so that $\{ k \cdot b\beta + \beta\} < \dfrac{1}{10}$. Let $\dfrac{1}{10} - \{q\alpha\} = r$ and $\dfrac{1}{10} - \{ q\beta\} = s$; here we can WLOG assume that $s > r$. Select $N$ large so that \[ \dfrac{s}{r} > \dfrac{N+1+\frac{1}{r}}{N} \]In turn, this implies that $r(10(N+1)) + 1 < s(10N)$. Again, staying loyal to the $``\text{adding bases}"$ idea, we select another base $D$ of type-$N$. Now consider the number $C = q+ D \cdot \left\lceil r(10(N+1)) \right\rceil$, which is less than $q + D \cdot s(10N)$. We will prove that $C$ is not a convenient denominator of $\alpha$, while being a convenient denominator of $\beta$. Simple bounding yields \begin{align*} \{(q+ D \cdot \left\lceil r(10(N+1)) \right\rceil) \alpha\} &= \{q \alpha\} + \{ D \cdot \left\lceil r(10(N+1)) \right\rceil) \alpha\} \\ &= \dfrac{1}{10} - r + \left\lceil r(10(N+1)) \right\rceil \{ D\alpha \} \\ &> \dfrac{1}{10}-r+r \\ \end{align*}as $\{N\alpha\} = N \cdot \{\alpha \}$ when $N \cdot \{ \alpha \} < 1, N \in \mathbb{N}.$ Analogously, it would take minimal $s(10N)$ additions of $D$ to boost $\{ q \beta \}$ above $\dfrac{1}{10}$. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$