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 4 of 5: Second case: bridge with rules (i) and (ii)

Previous step Next step

In plain words

When the jump wraps around past $n$ , a direct link isn't available, so the argument takes a detour: reflect $r$ across $n$ using rule (i), landing exactly on the number rule (ii) connects to $s$ .

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

Detailed analysis

If instead $s=r+k-n$ , then $r=n-(k-s)$ , so $n-r=k-s$ . Rule (i) gives $\text{color}(r)=\text{color}(n-r)=\text{color}(k-s)$ . Rule (ii) applied to $i=s$ gives $\text{color}(s)=\text{color}(|s-k|)=\text{color}(k-s)$ (since $s<k$ here). Chaining the two equalities, $\text{color}(r)=\text{color}(s)$ again.