## April 2012 solution

Sequences of the form floor(i1) with an irrational α1 are known as Beatty sequences after Samuel Beatty.

This month's riddle was originally published by Samuel Beatty as a problem in the American Mathematical Monthly in 1926. The claim is known as Rayleigh Theorem or Beatty's Theorem, and it has several proofs.

Here's one:

Take the numbers in the range 1,..., n-1 for some n. Though it may be difficult to characterize which ones of them appear in the sequence floor(i1), the total number of those that appear in the sequence is known: it is floor(n1). Similarly, the total number of them to appear in floor(i2) is floor(n2), so the grand-total to appear in either sequence is floor(n1)+floor(n2)=n-1.

One easy way to see the final equality is to observe that floor(n2)-0 is the same as n-ceil(n-n2) = n-ceil(n(1-1/α2)) = n-ceil(n1). This places floor(n1)+floor(n2) at n-(ceil(n1)-floor(n1)) =n-1. (It cannot be n, because that would suggest that n1 is an integer, when it was assumed to be irrational.

So, the total number of elements in the range equals the sum of the number of elements in the range that appears in either sequence, and this number increases by 1 whenever n is increased by 1, so the new element added (n) must belong to one of the two sequences, but not to both.

Q.E.D.

Further reading: The Wikipedia page discussing Beatty sequences gives much more detail and insight regarding Beatty sequences, including two more proofs of Rayleigh Theorem, and is a highly recommended read.