Putnam 1995

------
 
 
Problem B6

Let N be the positive integers. For any α > 0, define Sα = { [nα]: n ∈ N}. Prove that we cannot find α, β, γ such that N = Sα ∪ Sβ ∪ Sγ and Sα, Sβ, Sγ are (pairwise) disjoint.

 

Solution

We prove the stronger result that the three sets cannot be disjoint (whether or not their union is N).

Take any integer k > α, β, γ. Let { } denote the fractional part. Then at least two of the k3 + 1 points ({i/α}, {i/β}, {i/γ}), where i = 0, 1, 2, ... , k3, must lie in a cube side 1/k. Suppose they are i > j. Let h = i - j, then for some positive integers a, b, c we have |h/α - a|, |h/β - b|, |h/γ - c| ≤ 1/k. Hence |h - aα|, |h - bβ|, |h - cγ| < 1 (since k > α, β, γ). So each of [aα], [bβ], [cγ] is h or h - 1. Hence two are equal.

 


 

Putnam 1995

© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998