Let n and k be relatively prime positive integers with k < n. Each number in the set M = {1, 2, 3, ... , n-1} is colored either blue or white. For each i in M, both i and n-i have the same color. For each i in M not equal to k, both i and |i-k| have the same color. Prove that all numbers in M must have the same color.
Solution
n and k are relatively prime, so 0, k, 2k, ... , (n-1)k form a complete set of residues mod n. So k, 2k, ... , (n-1)k are congruent to the numbers 1, 2, ... , n-1 in some order. Suppose ik is congruent to r and (i+1)k is congruent to s. Then either s = r + k, or s = r + k - n. If s = r + k, then we have immediately that r = s - k and s have the same color. If s = r + k - n, then r = n - (k - s), so r has the same color as k - s, and k - s has the same color as s. So in any case r and s have the same color. By giving i values from 1 to n-2 this establishes that all the numbers have the same color.
Solutions are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
22 Oct 1998