# Pretty solution to question about floor function

I was recently asked this question by a student, and I don't know a nice, elegant way to solve it (actually, I'm not sure I know how to solve it at all).

Let $S(\alpha)=\lbrace \lfloor n\alpha\rfloor\ |\ n\in\mathbb{Z}^+\rbrace$. Show that $S(\sqrt{2})$ and $S(2+\sqrt{2})$ are disjoint.

I remember some tricks involved here, like replacing $\sqrt{2}$ by $1+(\sqrt{2}-1)$, and showing that $\lfloor n\sqrt{2}\rfloor=\lfloor m(2+\sqrt{2})\rfloor$ implied some inequalities on $n$, or $m$. So my question is: what is an elegant way to show this disjointness?

I should mention the student who asked me has just finished a calculus sequence (!), so I would prefer to avoid anything advanced.

Thanks.

-
@Aryabhata’s reference is more than adequate, but I note that this specific instance of the result is covered in detail on pp. 77-8 of Graham, Knuth, & Patashnik, Concrete Mathematics. – Brian M. Scott Mar 28 '12 at 22:23

This is a consequence of Beatty's theorem which has elementary proofs.

Beatty's theorem says that, if $p, q \gt 0$ are irrationals such that

$$\frac{1}{p} + \frac{1}{q} = 1$$

then the sets $\{\lfloor np\rfloor\}$ and $\{\lfloor nq \rfloor\}$ partition the naturals.

A (reasonably clever) proof of the disjointness can be found in the above wiki page here: http://en.wikipedia.org/wiki/Beatty_sequence#Second_proof

To paraphrase,

if $$M \lt n \sqrt{2} \lt M+1$$ and

$$M \lt n'(2 + \sqrt{2}) \lt M+1$$

where $M, n, n'$ are positive integers, then we have

$$\frac{M}{\sqrt{2}} + \frac{M}{\sqrt{2} + 2} \lt n+n' \lt \frac{M+1}{\sqrt{2}} + \frac{M+1}{\sqrt{2} + 2}$$

i.e

$$M \lt n+n' \lt M+1$$

An integer lying between two consecutive integers: contradiction.

-
Stunning, thank you! – user641 Mar 28 '12 at 23:02
@SteveD: You are welcome! – Aryabhata Mar 28 '12 at 23:05
@Aryabhata do you teach? I wish I had a teacher like you. – Kirthi Raman Mar 29 '12 at 9:55
@AlexSmith: You are very kind. Thank you. I don't teach, though. – Aryabhata Mar 29 '12 at 15:47