Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|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

1 Answer 1

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: 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.

share|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

 
discard

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