塗り絵と正方形 (2022年JJMO予選 第5問)

　今回はJMOではなく、今年のJJMOからのピックアップです。本問のような「塗り絵」タイプの数え上げ問題は数オリにおいては定番中の定番です。

解答

　45² = 2025であるので、45×45のマス目のうち黒く塗られていない部分は3か所のみである。そこで任意の自然数kに対して以下のような予想を立てる。

「(2k+1)×(2k+1)マスのマス目があり、このうち3つを残して黒く塗る。どのような塗り方をしても、全てのマス目が黒く塗られているn×nのマス目が存在するような正の整数nの最大値はkである。」

　上記予想を以下の手順で証明する。

(i) n≦kであることを示す

　
　(2k+1)×(2k+1)のマス目に対して左及び上から数えてk+1番目のマスを、そのマス目の中心と呼ぶ事とする。例えば上図はk = 5に対応するマス目を記しており、白抜き部分がマス目の中心に対応する。

　ここでn×nのマス目を(2k+1)×(2k+1)のマス目内にはみ出さずに配置する事を考えると、n≧k+1の時はn×nのマス目をどのように配置しても必ず(2k+1)×(2k+1)のマス目の中心を含む。従って(2k+1)×(2k+1)のマス目に対してその中心を黒く塗らない塗り方を考えた場合、nの最大値はk+1より小さくなる(すなわちn≦kが成立する)。

(i) n=kとなるマス目の存在を示す

　上の図で示す通り(k = 5の場合を示している)、(2k+1)×(2k+1)のマス目からはマスを共有しない4つのk×kのマス目を切り出すことが出来る。黒く塗られないマス目は3つであることから、この4つのk×kのマス目のうち少なくとも1つは全てが黒く塗られる事になる。

　従って3つを残してすべて黒く塗る場合、全てのマス目が黒く塗られているk×kのマス目が必ず存在する。

　以上(i)及び(ii)より予想は確かに成立し、45×45のマス目の場合はk = 22の場合に相当するので求めるべきnの最大値は22である。

コメント

　いきなり45×45マスで考ると大変であり、とりあえず小さめのマス目で実験を行った所このような解答に辿り着きました。

　真面目に論証しようとすると中々に骨が折れますが、幸いにも予選は答えのみ解答すれば十分です。真ん中を塗らない事でnが22以下である事は予想しやすい為、確証はなくとも正答できた人は多かったのではないでしょうか。