第2問

n

と

k

を、

k < n

を満たす互いに素な正の整数とする。集合

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

の各数を青か白のどちらかで塗り、次を満たすとする：(i) 各

i \in M

について、

i

と

n-i

は同じ色である；(ii)

i \ne k

を満たす各

i \in M

について、

i

と

|i-k|

は同じ色である。

M

のすべての数が同じ色であることを証明せよ。

ステップ 5/5: 輪全体にわたって等式をつなげる

前のステップ次のステップ

ざっくり言うと

輪の上の隣り合う組がすべて一致を強いられると、輪全体が一色に収束する——ドミノが次々と倒れて、最後には全部同じ向きに横たわるのと同じである。

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

詳しい解説

ステップ3〜4より、すべての $i=1,\dots,n-2$ に対して $\text{color}(r_i)=\text{color}(r_{i+1})$ が成り立つ。この $n-2$ 個の等式をつなげると、 $r_1,\dots,r_{n-1}$ はすべて同じ色であることが分かる。これらはステップ1よりちょうど $M$ の元（それぞれ一回ずつ現れる）なので、 $M$ のすべての数は同じ色である。