Show that it is possible to partition the positive integers into 100 non-empty sets so that if a + 99b = c for integers a, b, c, then a, b, c are not all in different sets.
Solution
Let t(n) be the largest k such that 2k divides n. Put Ai = {n : t(n) = i mod 100} for i = 0, 1, 2, ... , 99.
Suppose a + 99b = c and t(a) < t(b). Then 99b is divisible by a higher power of 2, than a. Hence t(c) = t(a). Similarly if t(a) > t(b), then t(c) = t(b). So at least two of t(a), t(b), t(c) must be the same.
© John Scholes
jscholes@kalva.demon.co.uk
20 December 2003