God Plays Dice: 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.

God Plays Dice

06 December 2007

A cute number-theoretic result

2 comments:

Blog Archive

Contributors

Other blogs