代表選考合宿 2022
問題 1

$m=an+b(n+1)$ なる非負整数 $a,b$ が存在するとき，$1,2,\dots,n$ のまとまりを $a$ 回，$1,2,\dots,n,n$ のまとまりを $b$ 回書き込めば問題文の条件を満たすのでこのような $m$ は $n$-カラフルである．$m\geq n^2-n$ であるとき $m=an+b(n+1)$ なる非負整数 $a,b$ が存在するので，$n$-カラフルでない正整数は有限個である．

$m=n^2-n-1$ が $n$-カラフルであるとして矛盾を示す．鳩の巣原理よりある $1\leq k\leq n$ が存在して $k$ が書き込まれるはマスは $n-2$ 個以下である．$m$ が $n$-カラフルであるために任意の $k$ が書き込まれた任意のマスについて，そこから時計回りに進んで $k$ が書き込まれたマスに辿り着くまでに移動するマスは高々 $n+1$ である必要があるので

$$n^2-n-1=m\leq (n-2)(n+1)$$

が成り立つ必要があるが，これは明らかに矛盾である．よって $m=n^2-n-1$ が $n$-カラフルでない最大の正整数である．