数学オリンピック 2018 日本本選 4

今回の記事はこちらの問題、本選の第4問です。

nを正の奇数とする。縦横に無限に広がるマス目があるとき、以下の条件をすべて満たすように各マスに1,2,3のいずれかの数をちょうど1つずつ書き込むことはできないことを示せ。
(a)辺を共有して隣りあうマスに同じ数字は書かれていない。
(b)縦または横に連続したどの1 × 3または3 × 1のマス目にも上、下、左または右から順に1,2,3と書かれていない。
(c)n × nのマス目に書かれた数の総和は位置によらずすべて等しい。

なかなかとっつきにくいです。2の周囲がどうなるかがとっかかりになると思います。

まずは比較的作りやすいものを考えましょう。2のマスに1のマスも3のマスも隣り合っていれば書き込まれる状況はかなり限定されそうです。

ここでは簡単にするため「1がかかれたマス」を「1のマス」などと記述する。
まずは2のマスに1のマスと3のマスが隣接する状況を考える。
このとき条件bから2の両隣は1と3が両方くることはできず、
すなわち2のマスの左右はどちらも1またはどちらも3であり、
上下もどちらも1またはどちらも3である。
したがって、配置は以下のようになり、条件aからさらに右下のように2のマスがあることがわかる。

これで少し周囲が1通りに埋まりました。これはまだまだ続けられそうです。

さらに拡張を続けていくと、以下のような配置ができる。

したがって条件a,bをみたすように配置すると2 × 2のマスに

を縦横に並べる形式になることがわかる。そこでこれを単位マス群とよぶことにする

ということで、ある2のマスに1のマスと3のマスの両方が接していたら条件a,bをみたす展開は1通りしかないことがわかりました。あとはcの成否を確かめるだけです。

nは奇数なのでn=2m+1となる整数mが存在し、左上のマスの選び方によって計算が変わってくる。
左上のマスを単位マス群の左上にした場合、単位マスは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をみたさない。

左上のマスをどれにするかによって得られる計算結果は違うものになってしまいました。
ということは、ある2のマスに1と3の両方が接している場合は条件abcを同時にみたさない、ということがここで示せました。

あとはこれ以外、すなわち、2のマスに隣接しているのがすべて1のマス、またはすべて3のマスの場合です。
このままでは考えづらそうですが、ちょっとした工夫をすると何かが見えてきます。

以降はどの2のマスについても「隣接するすべてのマスが1のマス」または「隣接するすべてのマスが3のマス」になっている場合を考えればよい。
ここで、「隣接するすべてのマスが1のマス」である2をすべて3に変え、さらに「隣接するすべてのマスが3のマス」である2をすべて1に変えると、条件aをみたしながら2が出てこない配置、すなわち1と3が縦横交互に配置されたものができる。
すなわち、ここで考えるものは「1と3が縦横交互に配置されたものの一部のマスを2に書き換えたもの」といえる。

このように、1と3の市松模様みたいなものを基準に考えることができるようになりました。これで議論を進めます。

簡単にするため1のマスを置き換えた2のマスを「1だったマス」、3のマスを置き換えた2のマスを「3だったマス」とよぶことにする。
1のマス、もしくは1だったマスを1つ選び、これを最上段とする1 × n のマス列を考え、これをM1とする。
この列をn列だけ右に動かして得られるマス列をM2とし、M1のすぐ右の列からn-1列でM1と同じ行の範囲をNとする。
すると最初に選んだマスを左上とするn × nマスの総和はM1とNの総和であり、右に1列ずらしたn × nマスの総和はM2とNの総和である。
条件cからすなわちM1の総和はM2の総和に等しいことがわかる。

この1 × nが比べたい図形です。これに対して成立する規則を適用するとどこかで無理が生じる、ということを示しにいきます。

M1における1だったマスの数をa1、3だったマスの数をa2とおくとM1の総和は
1 ∙ { (n+1)/2 – a1 } + 2 ∙ (a1+a2) + 3 ∙ {(n-1)/2 – a2 = 2n + a1 – a2 – 1
となる。
M2の最上段は3または3だったマスであるので1だったマスの数をb1、3だったマスの数を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の最上段は3または3だったマスなのでうまくいきません。
1段ずらして最上段を1または1だったマスにして考え直しましょう。

M2を下に1段ずらして得られるマス群をM3とする。
M3において1だったマスの数をc1、3だったマスの数をc2とおくと
M3は最上段の3もしくは3だったマスを除外し最下段に1または1だったマスを追加したことから
b1 ≦ c1 ≦ b1+1,b2-1 ≦c2 ≦ b2となるので
b1 – b2 ≦ c1 – c2 ≦ b1 – b2+2

ちょっとひっかかりができてしまいました。このままではa1 – a2=c1 – c2となる場合があるため無理が生じることがいえません。ちょっと脇道をみてみる必要がありそうです。

a1 – a2=c1 – c2となる場合はすなわちc1がb1より1大きくc2がb2より1小さい場合なのでM2の最上段が3だったマスでM3の最下段は1だったマスである。
したがってM2を上に1段ずらして得られるマス群をM4とすると
条件bよりM2の最下段は2でないので3のマスでありM4の最上段は1のマスである。
このM4で改めてc1 – c2を考えると
c1 = b1,c2 = b2となり
c1 – c2=b1 – b2 < a1 – a2となる。

無事に脇道に対応させることができました。ここまでくればあと一息。
限られた範囲しかとれないはずの値がいくらでも小さくできるのはおかしい、ということになります。

したがって、最上段が1のマスもしくは1だったマスである1 × n のマスを右にnマス、上か下に1マス移動させると(1だったマスの個数)-(3だったマスの個数)を減らすことができる。
条件cをみたす場合これを繰り返すことでこの値をいくらでも減らすことができるはずだが、マスの数が有限であるためこの値はある負の値より小さくすることはできないので矛盾。
したがって3条件をすべてみたす書き方は存在しないことがわかる。□
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク