今回の記事は本選の第４問です。問題は公式サイトから確認してください。
なかなかとっつきにくいです。2の周囲がどうなるかがとっかかりになると思います。
まずは比較的作りやすいものを考えましょう。２のマスに１のマスも３のマスも隣り合っていれば書き込まれる状況はかなり限定されそうです。
まずは２のマスに１のマスと３のマスが隣接する状況を考える。
このとき条件bから２の両隣は１と３が両方くることはできず、
すなわち２のマスの左右はどちらも１またはどちらも３であり、
上下もどちらも１またはどちらも３である。
したがって、配置は以下のようになり、条件aからさらに右下のように２のマスがあることがわかる。
これで少し周囲が１通りに埋まりました。これはまだまだ続けられそうです。
したがって条件a,bをみたすように配置すると2 × 2のマスに
を縦横に並べる形式になることがわかる。そこでこれを単位マス群とよぶことにする
ということで、ある２のマスに１のマスと３のマスの両方が接していたら条件a,bをみたす展開は１通りしかないことがわかりました。あとはcの成否を確かめるだけです。
左上のマスを単位マス群の左上にした場合、単位マスはm2個算入されることから総和は
(1+2+2+3)∙ m2 + (1+2)m + (1+2)m + 1 = 8m2+6m+1
左上のマスを単位マス群の右上にした場合、総和は
(1+2+2+3)∙ m2 + (2+3)m + (1+2)m + 2 = 8m2+8m+2
左上のマスを単位マス群の左下にした場合、総和は
(1+2+2+3)∙ m2 + (1+2)m + (2+3)m + 2 = 8m2+8m+2
左上のマスを単位マス群の右下にした場合、総和は
(1+2+2+3)∙ m2 + (2+3)m + (2+3)m + 3 = 8m2+10m+3
となるが、m ≧ 0 より 6m+1 < 8m+2 < 10m+3となるので
この場合は条件cをみたさない。
左上のマスをどれにするかによって得られる計算結果は違うものになってしまいました。
ということは、ある２のマスに１と３の両方が接している場合は条件abcを同時にみたさない、ということがここで示せました。
あとはこれ以外、すなわち、２のマスに隣接しているのがすべて１のマス、またはすべて３のマスの場合です。
このままでは考えづらそうですが、ちょっとした工夫をすると何かが見えてきます。
ここで、「隣接するすべてのマスが１のマス」である２をすべて３に変え、さらに「隣接するすべてのマスが３のマス」である２をすべて１に変えると、条件aをみたしながら２が出てこない配置、すなわち１と３が縦横交互に配置されたものができる。
すなわち、ここで考えるものは「１と３が縦横交互に配置されたものの一部のマスを２に書き換えたもの」といえる。
このように、１と３の市松模様みたいなものを基準に考えることができるようになりました。これで議論を進めます。
１のマス、もしくは１だったマスを１つ選び、これを最上段とする1 × n のマス列を考え、これをM1とする。
この列をn列だけ右に動かして得られるマス列をM2とし、M1のすぐ右の列からn-1列でM1と同じ行の範囲をNとする。
すると最初に選んだマスを左上とするn × nマスの総和はM1とNの総和であり、右に1列ずらしたn × nマスの総和はM2とNの総和である。
条件cからすなわちM1の総和はM2の総和に等しいことがわかる。
この1 × nが比べたい図形です。これに対して成立する規則を適用するとどこかで無理が生じる、ということを示しにいきます。
1 ∙ { (n+1)/2 – a1 } + 2 ∙ (a1+a2) + 3 ∙ {(n-1)/2 – a2 = 2n + a1 – a2 – 1
となる。
M2の最上段は３または３だったマスであるので１だったマスの数をb1、３だったマスの数をb2とおくとM2の総和は
1 ∙ { (n-1)/2 – b1 } + 2 ∙ (b1+b2) + 3 ∙ {(n+1)/2 – b2} = 2n + b1 – b2 + 1
となる。
これらは等しいので2n + a1 – a2 – 1=2n + b1 – b2 + 1
すなわちa1 – a2 – 2= b1 – b2 がわかる。
しかしこのまま突っ走ろうにもM2の最上段は３または３だったマスなのでうまくいきません。
１段ずらして最上段を１または１だったマスにして考え直しましょう。
M3において１だったマスの数をc1、３だったマスの数をc2とおくと
M3は最上段の３もしくは３だったマスを除外し最下段に１または１だったマスを追加したことから
b1 ≦ c1 ≦ b1+1,b2-1 ≦c2 ≦ b2となるので
b1 – b2 ≦ c1 – c2 ≦ b1 – b2+2
ちょっとひっかかりができてしまいました。このままではa1 – a2=c1 – c2となる場合があるため無理が生じることがいえません。ちょっと脇道をみてみる必要がありそうです。
したがってM2を上に１段ずらして得られるマス群をM4とすると
条件bよりM2の最下段は2でないので3のマスでありM4の最上段は1のマスである。
このM4で改めてc1 – c2を考えると
c1 = b1,c2 = b2となり
c1 – c2=b1 – b2 < a1 – a2となる。
無事に脇道に対応させることができました。ここまでくればあと一息。
限られた範囲しかとれないはずの値がいくらでも小さくできるのはおかしい、ということになります。
条件cをみたす場合これを繰り返すことでこの値をいくらでも減らすことができるはずだが、マスの数が有限であるためこの値はある負の値より小さくすることはできないので矛盾。
したがって３条件をすべてみたす書き方は存在しないことがわかる。□