第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

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

ステップ 2/5: 隣り合う剰余の差の二通りの形

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

ざっくり言うと

剰余の輪の上をある印から次の印へ歩くとき、各歩幅は $k$ である——ただし輪の頂点（値 $n$ ）を越えると、単純な和より $n$ だけ低い場所に着地する。

r_{i+1} = r_i + k \quad\text{or}\quad r_{i+1} = r_i + k - n

詳しい解説

定義より $r_{i+1}-r_i \equiv k \pmod n$ であり、 $r_i,r_{i+1}\in\{1,\dots,n-1\}$ なので、実際の（modではない）差はちょうど $k$ であるか、 $k-n$ （ $k$ を足すと $n$ を超えて一周してしまう場合）のいずれかである。