Problem 2

Let

n

and

k

be relatively prime positive integers with

k < n

. The set

M = \{1, 2, \ldots, n-1\}

is colored so that each number is either blue or white, subject to: (i) for each

i \in M

, the numbers

i

and

n-i

have the same color; and (ii) for each

i \in M

with

i \ne k

, the numbers

i

and

|i-k|

have the same color. Prove that all the numbers in

M

must have the same color.

Step 5 of 5: Chain the equalities across the whole cycle

Previous step Next step

In plain words

Once every consecutive pair along the cycle is forced to match, the whole cycle collapses to a single color, the same way a chain of dominoes toppling one after another ends up all lying the same way.

\text{color}(r_1)=\text{color}(r_2)=\cdots=\text{color}(r_{n-1})

Detailed analysis

Steps 3–4 show $\text{color}(r_i)=\text{color}(r_{i+1})$ for every $i=1,\dots,n-2$ . Chaining these $n-2$ equalities shows all of $r_1,\dots,r_{n-1}$ share one color. Since these are exactly the elements of $M$ (each appearing once, by Step 1), every number in $M$ has the same color.