2005年 日本数学オリンピック本選 第１問 解答例
表裏の区別のある硬貨が$${17\times 17}$$の正方形状にすべて表を上にして並べられている。一回の操作で、縦に連続する$${5}$$枚の硬貨、横に連続する$${5}$$枚の硬貨、または斜めに連続する$${5}$$枚の硬貨を同時にひっくり返す。この操作を何回か繰り返して、すべての硬貨が裏を上にして並んでいる状態にすることはできるか。
考え方：
硬貨の並びはマス目と等価です。
マス目に対して操作を行う問題で「できない」ことを示すのによくつかわれるのが、
各マス目を塗り分けたり数字をあてはめたりし、
操作によって変わらない量を作り出すことです。
また、操作によって裏表が切り替わることから、
２色の塗分け（または$${0, 1}$$の書き込み）を行い
偶奇性を活用するのが有効そうです。
そこで、
マス目に上手く$${0}$$か$${1}$$を書き込み（塗分け）
$${1}$$のマスのうち「裏が上」になっている数の総和の偶奇が
操作によって変わらないようにし、
かつ$${1}$$のマスの総数が奇数にすることができれば、
すべてを「裏が上」にすることは不可能であることが示せます。
この問題では連続する$${5}$$枚の硬貨に対する操作を行いますから、
$${5}$$マスの周期をもつ塗分け方を探します。
斜めについてはこの$${5\times 5}$$の対角だけでなく、
そこから上下または左右に1つずつずらした各$${5}$$通りの斜めのとり方についても、$${1}$$の数が偶数になるようにする必要があります。
その一例が
です。
この$${5\times 5}$$を、全体の$${1}$$の数が奇数になるように敷き詰めれば、
上記のロジックで証明が行えます。
解答例：
$${17\times 17}$$の並びに下のように$${0}$$か$${1}$$を割り当てる。
この時、任意の縦、横、斜めのに$${5}$$つ連続する並びは$${1}$$を$${4}$$つ含む。
$${1}$$が割り当てられた硬貨のうち裏を上にしているものの総数を$${S}$$とする。
最初は$${S=0}$$であり、一回の操作で$${S}$$の変化量は$${-4, -2, 0, 2, 4}$$となるので、
$${S}$$は常に偶数である。
すべての硬貨が裏を上にしている状態では$${S=231}$$であるため、
この状態にすることはできない。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
間違いなど見つけましたら是非お教えください。
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)