# Using your Head is Permitted

## April 2012 solution

Sequences of the form floor(*i**α_{1}) 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(*i**α_{1}), the total number of those that appear in
the sequence is known:
it is floor(*n*/α_{1}). Similarly, the total number of them
to appear in floor(*i**α_{2}) is
floor(*n*/α_{2}), so the grand-total to appear in either
sequence is
floor(*n*/α_{1})+floor(*n*/α_{2})=*n*-1.

One easy way to see the final equality is to observe that
floor(*n*/α_{2})-0 is the same as
*n*-ceil(*n*-*n*/α_{2}) =
*n*-ceil(*n*(1-1/α_{2})) =
*n*-ceil(*n*/α_{1}).
This places
floor(*n*/α_{1})+floor(*n*/α_{2}) at
*n*-(ceil(*n*/α_{1})-floor(*n*/α_{1}))
=*n*-1. (It cannot be *n*, because that would suggest that
*n*/α_{1} 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.

Back to riddle

Back to main page