*k*, which is unique. That is, the two sequences

and

contain, between them, each positive integer exactly once. In the case where and , 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 plus the number of integers of the form which are less than

*n*is equal to

*n*-1. The number of integers of the form which are less than n is ; the number of integers of the form which are less than

*n*is . Now, we have the inequalities

and

(the inequalities are strict since n/α and n/β are irrational.) Adding these together,

and recalling that 1/α + 1/β = 1, we have

and the middle member of the equation must be n-1; that's what we wanted. So the two sequences 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 , 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:

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.

*Very* cute! ^_^

Post a Comment