If $\frac1\alpha+\frac1\beta=1$, irrational, then $\{\lfloor n\alpha\rfloor:n\in\Bbb N\}\uplus\{\lfloor n\beta\rfloor:n\in\Bbb N\}=\Bbb N$

Question

Let $\alpha,\beta\in\Bbb R\setminus\Bbb Q$ such that $\frac1\alpha+\frac1\beta=1$, and define $S(x)=\{\lfloor nx\rfloor:n\in\Bbb N\}$. (Note that my convention takes $0\notin\Bbb N$.) The claim is that $S(\alpha)$ and $S(\beta)$ form a partition of $\Bbb N$. I find this claim rather startling, although it is at least believable considering that $d(S(x))=\frac1x$ (this is natural density), so that the condition $\frac1\alpha+\frac1\beta=1$ is necessary in view of $1=d(\Bbb N)=d(S(\alpha))+d(S(\beta))=\frac1\alpha+\frac1\beta$.

This result is quoted in another MSE question as "well-known", but no reference is given. Is there an easy way to prove this?

Answer 1

One way to prove this is to write down a criteria for membership in the set $S_r=\{[nr]:n\in\mathbb Z\}$, noting that for $r>1$ the set $\{[nr]:n\in\mathbb N\}$ is exactly the positive elements thereof. To do this, note that if $x=[nr]$ for some $n$, then $x=nr-f$ for some $0\leq f < 1$. Rearranging gives $$-x/r=-n+f/r.$$ Note that the existence of a solution is equivalent to the fractional parts of either side being equal, as we have an integer $-n$ to freely choose. Thus, we equivalently may write: $$\{-x/r\}=f/r.$$ However, as $f$ is an arbitrary element of $[0,1)$, this is equivalent to a final necessary and sufficient criteria for membership in $S_r$: $$\{-x/r\}<1/r$$ where $\{y\}$ is the fractional part of $y$ - that is, the unique element $z$ of $[0,1)$ such that $y-z$ is an integer.

Then, what remains to show is that for irrational $r$ and $s$ with $\frac{1}r+\frac{1}s=1$, for any positive integer $x$ we have that $x$ is in exactly one of $S_r$ or $S_s$. That is, exactly one of the following equations hold: $$\{-x/r\}<1/r$$ $$\{-x/s\}<1/s$$ To do this, note that $\frac{-x}r+\frac{-x}s=-x$, which is an integer. As neither of these terms may be an integer due to irrationality, it follows that $\{-x/r\}+\{-x/s\}=1$. Thus, we may rearrange our equations by substitution: $$\{-x/r\}<1/r$$ $$1-\{-x/r\}<1-1/r.$$ Or, equivalently: $$\{-x/r\}<1/r$$ $$\{-x/r\}>1/r.$$ Obviously, exactly one of these holds unless $\{-x/r\}=1/r$. However, this would imply that $\frac{-x-1}r$ is an integer, which is impossible since $r$ is irrational and $-x-1$ is non-zero. This proves that exactly one of these holds or any positive integer $x$, proving the desired statement. Note that these proofs can be extended to show that $S_r\cup S_s = \mathbb Z\setminus \{-1\}$ and $S_r\cap S_s=\{0\}$, noting that our argument works whenever $\frac{-x}r$ and $\frac{-x-1}r$ are not integers.

Answer 2

http://en.wikipedia.org/wiki/Beatty_sequence

2 proofs given here. This is known as Beatty Sequence.

Answer 3

Note that for any $x\in N$, one has $$ \frac xr+\frac xs=x. $$ Since $\frac xr$ and $\frac xs$ are irrational, one must have $$ \{\frac xr\}+\{\frac xs\}=1 \tag{1}$$ where $\{f\}$ is the decimal part of $f$.

Step 1. Show $A\cap B=\emptyset$. Clearly $A\neq \emptyset, B\neq\emptyset$. Suppose $A\cap B\not=\emptyset$. Namely, there are $m,n\in N $ such that $x=:\lfloor mr\rfloor=\lfloor ns\rfloor$. Then there are $a,b\in (0,1)$ such that $$ mr=x+a,ns=x+b $$ from which one has $$ \frac{x}{r}=m-\frac{a}{r}, \frac{x}{s}=n-\frac{b}{s}. $$ Thus one has $$ \{\frac{x}{r}\}=1-\frac{a}{r}, \{\frac{x}{s}\}=1-\frac{b}{r}. $$ By using (1), one has $$ \frac a{r}+\frac{b}{s}=1. \tag{2}$$ Since $a,b\in(0,1)$, one has $$ \frac a{r}+\frac{b}{s}<\frac 1{r}+\frac{1}{s}=1$$ which is against (2). So $A\cap B=\emptyset$.

Step 2. Show $A\cup B=N$. For any $x\in N$, $$ \{\frac xr\}+\{\frac xs\}=1. $$ If $\{\frac xr\}<\frac 1r$, then $$ \frac xr=m+\{\frac xr\}\text{ or }x=mr+r\{\frac xr\}$$ where $m\in N$, and hence $x= \lfloor mr\rfloor\in A$. If $\{\frac xr\}>\frac 1r$, then $$ \{\frac xs\}=1-\{\frac xr\}<1-\frac 1r=\frac1s. $$ Repeating the same thing, one has $x=\lfloor ns\rfloor\in B$ for some $n\in N$. If $\{\frac xr\}=\frac 1r$, then $\{\frac xs\}=\frac 1s$ and hence there are $m,n\in N$ such that $$ \lfloor mr\rfloor=x,\lfloor ns\rfloor=x $$ which gives $x\in A\cap B$. From Step 1, it is impossible.

Answer 4

Let us note first that if $u$, $v$ are not integers but their sum is an integer then $$[u]+[v] =u+v-1$$ Indeed, write $u = [u]+ \epsilon$, $v=[v]+ \delta$. Then $\epsilon + \delta$ is an integer, and $0< \epsilon, \delta < 1$ so $\epsilon + \delta=1$, done.

Using the above we conclude that for every $N\ge 1$ natural we have $$[\frac{N+1}{r}] + [\frac{N+1}{s}]=N$$ But we have $$\# (A \cap \{ 1,2, \ldots, N\})= [\frac{N+1}{r}]\\ \# (B \cap \{1,2, \ldots, N\} )= [\frac{N+1}{s}]$$ so $$\#\{A \cap \{1,2, \ldots, N\} + \#(B \cap \{1,2, \ldots, N\}) = N$$ for all $N\ge 1$. A moment's thought and we conclude that $A$, $B$ form a partition of $\mathbb{N}$