Can 1, 2, 3, ... be expressed as the disjoint union of three sets?

[Ackbach]

Here is this week's POTW:

-----

For a positive real number $\alpha$ define
$$S(\alpha)=\{\lfloor n\alpha\rfloor: n=1,2,3,\dots\}.$$
Prove that $\{1,2,3,\dots\}$ 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 $\le x$.)

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 219 - Jun 07, 2016

This was Problem B-6 in the 1995 William Lowell Putnam Mathematical Competition.

Congratulations to kiwi for his correct solutions, which follows:

Spoiler

Assume that the required three sets exist. We seek a contradiction.

\(\alpha\), \(\beta\), \(\gamma\) are all real numbers. It may not be possible to express them as the ratio of two integers, however it is possible to estimate them to any desired level of accuracy using integer ratios.

We can write:
\(\beta = \frac nm \alpha + \frac {e_1}{rm}\) and \(\beta = \frac qr \gamma + \frac {e_2}{rm}\) where n,m,q,r are integers and \(e_i\) is a real number with absolute value as small as we please.

\(\therefore rm \beta = rn \alpha + e_1 = mq \gamma + e_2\)

Now if we choose \(e_1,e_2 \lt 0.25\) then \(rm \beta, rn \alpha, mq \gamma\) are all within 0.5 of each other.

Without loss of generality we can assume that:
\(rm \beta \leq rn \alpha \leq mq \gamma\ \leq rm \beta +0.5\)

Now if the required union of sets can be achieved then \(\lfloor rm \beta \rfloor \neq \lfloor rn \alpha \rfloor\) so there exists an integer I such that:
\(rm \beta \leq I \leq rn \alpha \leq mq \gamma\ \leq rm \beta +0.5 \leq I +0.5\)

or

\( I \leq rn \alpha \leq mq \gamma \leq I +0.5\)

so

\(\lfloor rn \alpha \rfloor = \lfloor mq \gamma \rfloor\)

but \(\lfloor rn \alpha \rfloor \in S(\alpha)\) and \(\lfloor mq \gamma \rfloor \in S(\gamma)\) so \(S(\alpha)\) and \(S(\gamma)\) are not disjoint. A contradiction and the required sets cannot be formed.