Two positive real numbers $\alpha, \beta$ satisfies that for any positive integers $k_1,k_2$, it holds that $\lfloor k_1 \alpha \rfloor \neq \lfloor k_2 \beta \rfloor$, where $\lfloor x \rfloor$ denotes the largest integer less than or equal to $x$. Prove that there exist positive integers $m_1,m_2$ such that $\frac{m_1}{\alpha}+\frac{m_2}{\beta}=1$.
Problem
Source: 2022 China TST, Test 3 P2
Tags: floor function, number theory, algebra
22.05.2022 20:13
UPD: See solns at PM #4, #7 Some ideas: assume $\alpha,\beta \notin \mathbb{Q}$ Note the number of $k_1$ satisfying $\lfloor k_1 \alpha \rfloor < X$ is precisely $\lfloor \frac{X}{\alpha} \rfloor$. Let $a=\frac{1}{\alpha}$ and $b=\frac{1}{\beta}$. From $\lfloor k_1\alpha \rfloor \ne \lfloor k_2\beta\rfloor$ we can see if $\lfloor Xa \rfloor > \lfloor (X-1)a \rfloor$ then $\lfloor Xb \rfloor = \lfloor (X-1)b \rfloor$, for otherwise there exists a solution $(k_1,k_2)$ to $\lfloor k_1\alpha \rfloor = \lfloor k_2\beta \rfloor = X$ In other words, if $\{xa\} > 1-a$ then $\{xb\} < 1-b$. Since $a\notin \mathbb{Q}$ we know there exists $t$ such that $\{at\} = 1-\epsilon$. For all $m\epsilon<a$, $\{a(mt)\}=1-m\epsilon$. We can see $\{bt\} < \frac{1-b}{\lfloor \frac{a}{\epsilon} \rfloor}$, or otherwise, $\{btk\} \ge 1-b$ for some $1\le k\le \frac{a}{\epsilon}$.
22.05.2022 20:19
Idea: prove a, b, and 1 are linearly dependent. If 1,a,b are linearly dependent, wlog we deal with the hard case: ua+vb=n for some integer n. We need to choose X such that {Xa}<a and {Xb}<b, or {X(n-ua)/v}<(n-ua)/v, now we need v{X(n-ua)/v}={X(n-ua)}=1-{uXa}<n-ua. Thus, we need the following: uXa ∈ (uT; uT+min(1,au)) for some integer T (1) Xua∈(-vM+Xn-1; -vM+XN) for some integer M (2) {uXa}>1-vb. (3) If n>2 then WLOG 1<vb therefore condition (3) is trivially satisfied. From (2) and (1) we need -vM+xN-1=uT or xN=vM+1 (mod u) Consider such X and M (they are fixed variables now !!). Next, consider X2=X+uK, and M2=M+uL Now we only need to choose an integer K such that (X+uK)(ua-n)∈(-v(M+uL)-1; -v(M+uL)) for some integer L This is just Kronecker, done.
22.05.2022 20:36
Perhaps we can prove $a,b,1$ are linearly dependent over $\mathbb{N}$ this way: If $1-\epsilon=\{xa\} < \{mxa\}$ where $m=\lceil \frac{1}{\epsilon} \rceil$ then we have $\{xb\} < \frac{1-b}{\lfloor \frac{a}{\epsilon} \rfloor}$ and $\{mxb\} < \frac{1-b}{\lfloor \frac{a}{m\epsilon-1} \rfloor}< \frac{1-b}{\lfloor \frac{a}{\epsilon} \rfloor}$ We know $\{mxb\} \equiv m\{xb\} (\bmod\; 1)$ and observe $\{xb\} < \frac{1-b}{\lfloor \frac{a}{\epsilon} \rfloor} = \frac{\epsilon (1-b)}{a} + (\frac{1-b}{\lfloor \frac{a}{\epsilon} \rfloor} - \frac{1-b}{\frac{a}{\epsilon}}) \le \frac{\epsilon (1-b)}{a} + \frac{1-b}{(\frac{a}{\epsilon}-1)^2} \le \frac{\epsilon (1-b)}{a} + 1.01 \frac{\epsilon^2 (1-b)}{a^2}$ for sufficiently small $\epsilon$. Therefore, $\{xb\} < \frac{\epsilon (1-b)}{a} + O(\epsilon^2)$ and $m\{xb\} < \frac{m\epsilon (1-b)}{a} + O(m\epsilon^2)$. Using $(m-1)\epsilon < 1 < m\epsilon$ we can get $\lfloor m\{xb\} \rfloor \le \frac{1-b}{a}$
22.05.2022 20:50
@above, there is an easy way to prove this, consider an N such that ||Na|| and ||Nb|| is very small, WLOG {Na} and {Nb} are very close to 0. Let x={Na} and y={Nb}, then we need to choose an M such that Mx∈(A,A+a) and My∈(B,B+b) for some integer A and B. Let M=[(A+a)/x], we need [(A+a)/x]y∈(B,B+b) for some B. Now [(A+a)/x]y < (A+a)x/y and > (A+a)x/y-y, we just need (A+a)x/y>B+y and (A+a)x/y<B+b or (A+a)x/y∈(B+y,B) for some B. The rest is Kronecker since x/y is irrational.
23.05.2022 04:46
Okay here is a complete solution. Thanks to Justanaccount for helping out! Assume $\alpha,\beta \notin \mathbb{Q}$ Note the number of $k_1$ satisfying $\lfloor k_1 \alpha \rfloor < X$ is precisely $\lfloor \frac{X}{\alpha} \rfloor$. Let $a=\frac{1}{\alpha}$ and $b=\frac{1}{\beta}$. From $\lfloor k_1\alpha \rfloor \ne \lfloor k_2\beta\rfloor$ we can see if $\lfloor Xa \rfloor > \lfloor (X-1)a \rfloor$ then $\lfloor Xb \rfloor = \lfloor (X-1)b \rfloor$, for otherwise there exists a solution $(k_1,k_2)$ to $\lfloor k_1\alpha \rfloor = \lfloor k_2\beta \rfloor = X$ In other words, if $\{xa\} > 1-a$ then $\{xb\} < 1-b$. Claim There exists integers $m,n,k$ such that $ma+nb=k$. Proof of Claim We first prove there exists $n$ such that $||na||, ||nb||<\epsilon$ where $||na||=\min\{1-\{na\}, \{na\} \}$. We can easily find $||na||<\epsilon^3$, and we note $||na||, ||2na||, \cdots, ||\lceil \frac{1}{\epsilon} \rceil na||$ are all smaller than $\epsilon$. We can prove with pigeonhole principle at least one of $||tnb||$ where $1\le t\le \lceil \frac{1}{\epsilon} \rceil$ works. Suppose $\{na\},\{nb\} < \epsilon$. Let $x=\{na\}, y=\{nb\}$. Assume for the sake of contradiction $\frac xy$ is not rational. If there exists integers $M,A,B$ such that $Mx\in (A,A+a)$ and $My\in (B,B+b)$, then I am done, because $\{Mna\}=\{(Mn-1)a\} + 1$ and $\{Mnb\} = \{(Mn-1)b\} + 1$. We take $M=\lfloor \frac{A+a}{x} \rfloor$. This guarantees $x(\frac{A+a}{x}-1)=A+a-x \le Mx \le x\frac{A+a}{x} = A+a$. Since $a>x$, $Mx\in (A,A+a)$ We have $My \in ((A+a)\frac yx - y, (A+a)\frac yx)$. We need to show for some $A$, there exists an integer $B$ such that $(A+a)\frac yx - y \ge B$ and $(A+a)\frac yx \le B+b$. If $\frac yx$ is irrational, there exists $A$ such that $y\le \{(A+a)\frac yx\} \le b$. Therefore, $\frac yx$ must be rational. Now, let $na=C+x, nb=D+y$ then $x=qy$ for some $q\in \mathbb{Q}$. Therefore, $\frac{na-C}{nb-D}=q \rightarrow (na-C)=q(nb-D)$ Let $q=\frac uv$ where $u,v\in \mathbb{Z}$ then $v(na-C)=u(nb-D) \rightarrow (vn)a-(un)b=vC-uD$ Back to the problem if $m,n$ are of opposite signs, say $ma\equiv nb(\bmod\; 1)$, then pick $||tb||=\epsilon$. If $\{tb\}=\epsilon < \frac{ab}{mn}$ then $\{tmb\}=m\epsilon < \frac{ab}{n} < b$ and $\{tma\} = \{tnb\} < \frac{ab}{m} < a$. It follows that $\{tma\} < \{(tm-1)a\}$ and $\{tmb\} < \{(tm-1)b\}$, contradiction. If $\{tb\}=1-\epsilon>1-\frac{ab}{mn}$ then $\{tmb\}=1-m\epsilon > 1- \frac{ab}{n} > 1-b$ and $\{tma\} = \{tnb\} > 1- \frac{ab}{m} > 1- a$. It follows that $\{tma\} > \{(tm+1)a\}$ and $\{tmb\} > \{(tm+1)b\}$, contradiction. Therefore, $m,n$ are of the same sign. WLOG $m,n,k$ are all positive and $k$ is minimal. Assume for the sake of contradiction $k\ge 2$. Thus, either $ma\ge 1$ or $nb\ge 1$. WLOG $nb\ge 1$, so it suffices to take $\{Xa\}<a$ and $\{Xb\} < \frac 1n < b$ WLOG $\gcd(k,m,n)=1$. Let $\{Xa\}=Z+\epsilon$, then I want $Xk-Zm\equiv 1(\bmod\; n)$, which wins because $\{\frac{X(k-ma)}{n} \} = \{ \frac{Xk}{n} - Xa \frac mn\} = \{ \frac{Xk-(Z+\epsilon)m}{n} \}$ But this is doable by density; $(X, Xa (\bmod\; n))$ are dense in $\mathbb{Z}_n \times [0,n)$ so we can clearly take $Xk\equiv Zm+1 (\bmod\; n)$ and $\{Xa\} < \epsilon$ for any $\epsilon > 0$ (another way to think about it is that $\{\frac{Xa}{n}\}$ is dense in $[0,1)$, and fixing $X$ mod $n$ preserves the density )
03.07.2022 03:47
For obvious reasons $a/b$ is not rational. Note that $k$ appears in the sequence $\lfloor na\rfloor$ iff $\{ \frac{k}{a}\} >1- \frac{1}{a}$. ($k\in(na-1,na)$ If either of $a,b$ is rational wlog $b$ then $\lfloor nb\rfloor$ would contain all multiples of some number $M$ and we would have due to kroncker that for some $k$ $\{ \frac{kM}{a}\} >1- \frac{1}{a}$ thus a conflict. So neither of $a,b$ is rational. As before we can't have $$\{ \frac{\lfloor na \rfloor }{b}\} >1- \frac{1}{b}$$Write $$\frac{\lfloor na \rfloor }{b}=n\frac{a}{b}-\frac{\{ na\} }{b}$$Of course if $\frac{\{ na\} }{b}$ were larger than $\{ n\frac{a}{b}\}$ then the previous inequality would hold so in particular we have that $$\{ n\frac{a}{b}\}>\frac{\{ na\} }{b}$$for every $n$. Now invoking kronecker choose $N$ such that $\{ N\frac{a}{b}\}=d$ : $d<\frac{1}{8b}$ . Next take $k=\lceil \frac{M}{d} \rceil N$ and see that $\{k\frac{a}{b}\}=\{\lceil \frac{M}{d} \rceil N\frac{a}{b}\} = \{ \lceil \frac{M}{d} \rceil d\}<d $ and then we have also $\{ ka\}<b\{ k \frac{a}{b}\}<\frac{1}{8}$ but: $$ \{ ka\}=\{ \lceil \frac{M}{d} \rceil Na\}=\{ \lceil \frac{M}{d} \rceil \{ Na\} \}$$this together with the fact that $\{ Na\}<\frac{1}{8}$ will give that $M\frac{\{Na\}}{d}$ is within $1/4$ distance to an integer for every $M$ due to kronecker $\frac{\{Na\}}{d}=q$ is rational and furthermore an integer.Thus $q=\frac{\{Na\} }{\{N\frac{a}{b}\}}=\frac{Na-\lfloor Na \rfloor }{N\frac{a}{b}-\lfloor N\frac{a}{b}\rfloor }$ and this gives $\frac{q}{b}+\frac{r}{a}=1$ for some rational $r$ . Interchanging the roles of $a,b$ in the above argument we get an integer $p$ and a rational $s$ such that $\frac{p}{a}+\frac{s}{b}=1=\frac{q}{b}+\frac{r}{a}$ but then we get that $p=r,q=s$ and the desired result.
12.10.2022 15:23
In fact,instead of the version $(nx,ny)$ is dense on $[0,1]^2$ when considered modulo $1$ when $x,y,1$ are independent on $\mathbb{Q}$,we have the following version that immediately overkill this problem:(the key is that it actually gives all possible points for all possible $r_i$s,not only for independent ones) for any real numbers $r_1,r_2,\cdots,r_k$,we have $(p_1,p_2,\cdots,p_k)$ as a limit point of $(nr_1,nr_2,\cdots,nr_k)$ considered modulo $1$ iff $\forall n_1,n_2,\cdots,n_k \in \mathbb{Z},n_1r_1+\cdots +n_kr_k \in \mathbb{Z}$,we have $p_1n_1+\cdots+p_kn_k\in\mathbb{Z}$. Now its easy to finish since the problem is equivalent with $\{xa\}\ge 1-a,\{xb\}\ge 1-b$.
14.10.2022 11:03
This nice result belongs to T.Skolem.
01.09.2023 09:57
This is an improvement of $\mathrm{Beatty's\ Theorem}$
14.04.2024 18:04
CANBANKAN wrote: WLOG $\gcd(k,m,n)=1$. Let $\{Xa\}=Z+\epsilon$, then I want $Xk-Zm\equiv 1(\bmod\; n)$, which wins because $\{\frac{X(k-ma)}{n} \} = \{ \frac{Xk}{n} - Xa \frac mn\} = \{ \frac{Xk-(Z+\epsilon)m}{n} \}$ But this is doable by density; $(X, Xa (\bmod\; n))$ are dense in $\mathbb{Z}_n \times [0,n)$ so we can clearly take $Xk\equiv Zm+1 (\bmod\; n)$ and $\{Xa\} < \epsilon$ for any $\epsilon > 0$ How can you take $X,Z$ such that $Xk-Zm\equiv 1\pmod n$? Of course $(k,m,n) = 1$, however, $Z$ depends on $X$.
24.11.2024 23:50
Since $a$ is irrational, $(X, Xa) \to \mathbb{Z}/n\mathbb{Z} \times [0,n)$ has dense image, meaning for every $r \in \mathbb{Z}/n\mathbb{Z}, s \in \mathbb{R}/n\mathbb{Z}, \varepsilon > 0$, there exists $X$ such that $X \mapsto r$ in $\mathbb{Z} \mapsto \mathbb{Z}/n\mathbb{Z} $ and $||Xa-s||_{\mathbb{R}/n\mathbb{Z}} < \varepsilon$. Thus I can first pick $u,v$ such that $uk - vm = 1$ or something, and pick a good $X$ fixing $X (\bmod\; n) = u$ and $Z = \lfloor Xa\rfloor$ is very close to $v$. I will hopefully find a time to clarify my post.