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 3 of 5: First case: direct application of rule (ii)

Previous step Next step

In plain words

If the second point is simply the first plus a jump of $k$ , then rule (ii) — which links any number to itself-minus- $k$ — reads off the same-color fact immediately.

s=r+k \ \Longrightarrow\ |s-k|=r \ \Longrightarrow\ \text{color}(s)=\text{color}(r)

Detailed analysis

Write $r=r_i$ , $s=r_{i+1}$ . If $s=r+k$ then $|s-k|=r$ , so applying coloring rule (ii) to $i=s$ (valid since $s\ne k$ , as only one index in this construction equals $k$ ) gives directly that $s$ and $r=|s-k|$ share a color.