MathLabs

第5問

∣x−y∣∈{5,7,12}|x-y|\in\{5,7,12\} ならば常に f(x)≠f(y)f(x)\ne f(y) となる関数 f:Z→{1,2,…,k}f:\mathbb Z\to\{1,2,\dots,k\} が存在するような最小の正整数 kk を求めよ。
ステップ 2/5: 禁止される色の数を評価する
#{y:∣x−y∣∈{5,7,12}, ∣y∣<∣x∣}≤3\#\{y:|x-y|\in\{5,7,12\},\ |y|<|x|\}\le 3
詳しい解説

xx が正なら、既彩色の隣接点は順序の前にある x−5,x−7,x−12x-5,x-7,x-12 に限られ、xx が負の場合も対称である。したがって既彩色の隣接点は高々3個で、禁止色も高々3色である。