06 December 2007

A cute number-theoretic result

Here's a cute result that I saw a few days ago: let α and β be irrational positive numbers, such that 1/α + 1/β = 1. Then for any positive integer n, exactly one of $n = \lfloor k\alpha \rfloor$ and $n = \lfloor k\beta \rfloor$ has a positive integer solution k, which is unique. That is, the two sequences
\lfloor \alpha \rfloor, \lfloor 2\alpha \rfloor, \lfloor 3\alpha \rfloor, \cdots

and
\lfloor \beta \rfloor, \lfloor 2\beta \rfloor, \lfloor 3\beta \rfloor, \cdots

contain, between them, each positive integer exactly once. In the case where $\alpha = \sqrt{2}$ and $\beta = 2 + \sqrt{2}$, for example, these sequences are
1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, ...
and
3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, ...
which partition the positive integers.

The proof is quite nice. It's enough to show that the number of integers of the form $\lfloor k\alpha \rfloor$ plus the number of integers of the form $\lfloor k\beta \rfloor$ which are less than n is equal to n-1. The number of integers of the form $\lfloor k\alpha \rfloor$ which are less than n is $\lfloor n/\alpha \rfloor$; the number of integers of the form $\lfloor k\beta \rfloor$ which are less than n is $\lfloor n/\beta \rfloor$. Now, we have the inequalities

n/\alpha - 1 < \lfloor n/\alpha \rfloor < n/\alpha

and
n/\beta - 1 < \lfloor n/\beta \rfloor < n/\beta

(the inequalities are strict since n/α and n/β are irrational.) Adding these together,
n/\alpha + n/\beta - 2 < \lfloor n/\alpha \rfloor + \lfloor n/\beta \rfloor < n/\alpha + n/\beta

and recalling that 1/α + 1/β = 1, we have
n - 2 < \lfloor n/\alpha \rfloor + \lfloor n/\beta \rfloor < n

and the middle member of the equation must be n-1; that's what we wanted. So the two sequences $\{ \lfloor k\alpha \rfloor \}_{k=1}^{\infty}, \{ \lfloor k\beta \rfloor \}_{k=1}^{\infty}$ contain between them n-1 members which are less than n, and n members which are less
than n+1; thus exactly one of them contains n, for any positive integer n.

The analogous theorem for three sequences of integers, where 1/α + 1/β + 1/γ = 1, doesn't hold; a weaker theorem holds that on average an integer n can be written in exactly one of the forms
\lfloor k\alpha \rfloor, \lfloor k\beta \rfloor, \lfloor k\gamma \rfloor
, though, and actually no integer can be written in all three of these forms; I leave this as an exercise for the reader. What I don't know is whether there is some set α, β, γ for which the original result is salvaged.

2 comments:

David said...

What I don't know is whether there is some set α, β, γ for which the original result is salvaged.

It isn't possible; in fact this was problem B6 on the 1995 Putnam.

Aaron said...

*Very* cute! ^_^