Putnam 1995, Problem B-6

For a positive real number \( \alpha \), define
\[
S(\alpha) = \{ \lfloor n\alpha \rfloor : n = 1,2,3,\ldots \}.
\]
Prove that \( \{1,2,3,\ldots\} \) cannot be expressed as the disjoint union of three sets \( S(\alpha), S(\beta) \) and \( S(\gamma) \). [As usual, \( \lfloor x \rfloor \) is the greatest integer \( \leq x \).]


Solution:
Obviously \( \alpha, \beta, \gamma \) have to be greater than 1, and no two can both be rational, so without loss of generality assume that \( \alpha \) and \( \beta \) are irrational. Let \( \{x\} = x - \lfloor x \rfloor \) denote the fractional part of \( x \). Then \( m \in S(\alpha) \) if and only if \( f(m/\alpha) \in (1 - 1/\alpha, 1) \cup \{0\} \). In particular, this means that \( S(\alpha) \cap \{1, \dots, n\} \) contains \( \lfloor (n + 1)/\alpha \rfloor \) elements, and similarly. Hence for every integer \( n \),  
\[
n = \left\lfloor \frac{n + 1}{\alpha} \right\rfloor + \left\lfloor \frac{n + 1}{\beta} \right\rfloor + \left\lfloor \frac{n + 1}{\gamma} \right\rfloor - 3.
\]  
Dividing through by \( n \) and taking the limit as \( n \to \infty \) shows that \( 1/\alpha + 1/\beta + 1/\gamma = 1 \). That in turn implies that for all \( n \),  
\[
\left\{ -\frac{n + 1}{\alpha} \right\} + \left\{ -\frac{n + 1}{\beta} \right\} + \left\{ -\frac{n + 1}{\gamma} \right\} = 2.
\]  
Our desired contradiction is equivalent to showing that the left side actually takes the value 1 for some \( n \). Since the left side is an integer, it suffices to show that \( \{ -(n + 1)/\alpha \} + \{ -(n + 1)/\beta \} < 1 \) for some \( n \).  
A result in ergodic theory (the two-dimensional version of the Weil equidistribution theorem) states that if \( 1, r, s \) are linearly independent over the rationals, then the set of points \( (\{nr\}, \{ns\}) \) is dense (and in fact equidistributed) in the unit square. In particular, our claim definitely holds unless \( a/\alpha + b/\beta = c \) for some integers \( a, b, c \).  
On the other hand, suppose that such a relation does hold. Since \( \alpha \) and \( \beta \) are irrational, by the one-dimensional Weil theorem, the set of points \( (\{-n/\alpha\}, \{-n/\beta\}) \) is dense in the set of \( (x, y) \) in the unit square such that \( ax + by \) is an integer. It is simple enough to show that this set meets the region \( \{(x, y) \in [0, 1]^2 : x + y < 1\} \) unless \( a + b \) is an integer, and that would imply that \( 1/\alpha + 1/\beta \), a quantity between 0 and 1, is an integer. We have our desired contradiction.