Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
@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
up vote 12 down vote accepted

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:

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


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

An integer lying between two consecutive integers: contradiction.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.