1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This explicitly proved in the "Concrete Mathematics: Foundation for Computer Science" by Ronald L. Graham, Donald E. Knuth, Oren Patashnik. see en.wikipedia.org/wiki/Concrete_Mathematics. $\endgroup$ – Omran Kouba Apr 20 '14 at 18:46
  • $\begingroup$ These are in two books I like by Niven, one called Irrational Numbers, really good and worth it. The other, called Diophantine Approximations, is unusual in using no continued fractions. He says Beatty 1926 and often rediscovered. $\endgroup$ – Will Jagy Apr 20 '14 at 18:59
  • $\begingroup$ @Will There is an entire book on Diophantine Approximations that doesn't use continued fractions? Color me dubious. $\endgroup$ – Mario Carneiro Apr 20 '14 at 19:04
  • $\begingroup$ yeah, Preface: "A unique feature of this monograph is that continued fractions are not used. This is a gain in that no space need be given over to there description, but a loss in that certain refinements appear out of reach without the continued fraction approach." Anyway, Dover reprint, cheap, store.doverpublications.com/0486462676.html Also, I was unable to find the Beatty thing in the other book, I guess he really likes brevity and focus and elementary exposition. $\endgroup$ – Will Jagy Apr 20 '14 at 19:10
  • $\begingroup$ @Will Well, Sandeep gets the checkmark because Wikipedia is always easier to access than a book reference, and proof 2 given there is nice and elementary, too. But that does sound like a nice book. $\endgroup$ – Mario Carneiro Apr 20 '14 at 19:12
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nicely done. This would be a good contest-math Q. $\endgroup$ – DanielWainfleet Jan 4 '17 at 3:26
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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}$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.