こんにちは。東久留米市の学習塾塾長です。
今回は、２０２０年日本ジュニア数学オリンピック予選の問題です。
問題は、
「８×８のマス目があり、各マスには片面が白色、もう一方の面が黒色のコインが１枚ずつ置いてある。いずれのコインも白色の面が表になっている状態から始めて、ＡさんとＢさんが以下の操作を２０２０回行う。
まず、Ａさんが相異なる８つのマスを選び、それらのマスに置かれている８枚のコインをすべて裏返す。次に、Ｂさんが行または列を１つ選び、その行または列に置かれている８枚のコインをすべて裏返す。
このとき、以下の条件をみたす最大の非負整数ｋを求めよ。
ＡさんはＢさんの行動にかかわらず、２０２０回の操作が終わったときに黒色の面が表になっているコインをｋ枚以上にできる。」
です。
早速、取り掛かりましょう。
Ａさんが任意の８つのマスを選ぶことができるのに対して、Ｂさんは行または列のいずれか１つしか選べないので、行または列のいずれか１つに置かれた８枚すべてが黒色コインでない状態以外では、Ａさんは黒色コインを増やすことが可能です。
そこで、各行各列に１つ以上の白色コインが置かれている状態を考えると、その簡単な例は、図１のような、マス目の対角線上に並んだマス（☆）白色のコインが置かれている場合です。
▲図１．マス目の対角線上のマスに白色のコインが置かれている状態を考えます
ここで、ｎ回目の操作の後で、マス目上にある黒色コインの個数をｂnとします。このとき、ｂ0＝０、 ｂ1＝８です。
まず、１回目のＡさんの操作で、図１の☆のマス以外の８マスを選んで、それらのマスに置かれている８枚のコインをすべて裏返すと、２行または２列以上に黒色コインが置かれることになります。（☆を黒色にしないので、各行各列には最大７個の黒色コインしか置けません）
そこで図２の左側の図ように、１回目のＡさんの操作で、マス目の１行目の２～８列目と２行目１列目のマスを黒色コインにした場合を考えます。
▲図２．マス目の１行目の２～８列目と２行目１列目のマスを黒色コインにした場合を考えます
このとき、２回目のＢさんの操作で、１行目を選んだ場合、図３の中央の図のように、２回目の操作後、ｂ2＝２になり、その他の行または列を選んだ場合、ｂ2＝１４または１６になります。
また、上記以外で、ある行または列に黒色コインが最大ｍ個（ｍ≦７）置かれるようにＡさんが操作し、続いてＢさんが黒色コインがｍ個置かれてる行または列を選んだ場合、
ｂ2＝８－ｍ＋（８－ｍ）＝１６－２ｍ
になり、したがって、
ｂ2≧２
です。
さらに、図２の右側の図のように、３回目のＡさんの操作で、マス目の１行１列目とその他の白色コインが置かれている７つのマスを選ぶ（図の場合は、１行１～７列目と３行目１列目）ことにより、マス目の対角線上の８つのマスに白色コインが置かれた状態に戻すことができます。
このように、Ａさんが、Ａさんの操作後にマス目の対角線上の８つのマスを白色コインにする操作を繰り返すことにより、高々（６４－８）÷２×２－１＝５５（回）の操作で、図３の左側の図のような状態にすることが可能で、それ以降の２０１９回目の操作までＢさんが選んだ行または列のコインを再び裏返すことにより、図３の左図の状態を２０１９回目の操作後まで保つことができます。
▲図３．奇数回目（≦５５）のＡさんの操作後と次のＢさんの操作です
２０２０回目のＢさんの操作では、いずれの行または列の１つを選んでも同じで、図３の右側の図のように、ｂ2020＝６４－１４＝５０です。
以上から、Ｂさんの操作にかかわらず、
ｂ2020≧５０ （☆）
であることが判りました。
次に、Ａさんの操作にかかわらず、ｂ2020≦５０ になるかを調べます。
初めに、マス目上の黒色コインの個数はいつでも偶数個になることを示します。
ある操作で、白色コインｍ個、黒色コイン８－ｍ個を裏返すと、黒色コインが増えた個数は、ｍ－（８－ｍ）＝２ｍ－８（個）で、これは偶数個です。
一方、１回目のＡさんの操作前のマス目上にある黒色コインの個数は０個（偶数）であることから、マス目上の黒色コインの個数はいつでも偶数個になります。
Ａさんのｉ回目の操作後、マス目上の黒色コインが５２個以上になるのは、その直前のＢさんのｉ－１回目操作後のマス目上の黒色コインの個数が、４４個、４６個、４８個または５０個のいずれかの場合で、そのとき、Ａさんのｉ回目の操作後のマス目上の黒色コインの個数は、それぞれ、５２個、５４個、５６個または５８個のいずれかになります。
一方、マス目上の黒色コインの枚数と、そのときの行または列に置かれる黒色コインの最大個数は、図４に示すように、
（マス目上の黒色コイン） → （行または列に置かれる黒色コインの最大個数） は、
・ ５２、５４、５６個の場合 → ７個以上
・ ５８個の場合 → ８個
です。
▲図４．マス目上の黒色コインの個数と各行各列に置かれる黒色コインの最大個数です
すると、Ａさんのｉ回目の操作後、マス目上の黒色コインが５２個、５４個、５６個の場合、Ｂさんのｉ＋１回目の操作で、黒色コインが７個以上の行または列を選ぶことにより、黒色コインを６個減らすことができるので、マス目上の黒色コインは、それぞれ、４６個、４８個、５０個、つまり、５０個以下になります。
さらに、Ａさんのｉ回目の操作後、マス目上の黒色コインが５８個の場合、Ｂさんのｉ＋１回目の操作で、黒色コインが８個の行または列を選ぶことにより、黒色コインを８個減らすことができるので、マス目上の黒色コインは、５０個になります。
したがって、Ａさんの操作でマス目上の黒色コインが５２個、５４個、５６個、５８個になった場合、Ｂさんは黒色コインが最大個数置かれている行または列を選んで操作することを２０２０回目まで繰り返すことにより、
ｂ2020≦５０
とすることができます。
以上から、Ａさんの操作にかかわらず、
ｂ2020≦５０ （★）
であることが判りました。
したがって、（☆）と（★）から、ｂ2020＝５０ であることから、ｋの最大値は ５０ で、これが答えです。
簡単な問題です。
今回は、２０２０年日本ジュニア数学オリンピック予選の問題です。
問題は、
「８×８のマス目があり、各マスには片面が白色、もう一方の面が黒色のコインが１枚ずつ置いてある。いずれのコインも白色の面が表になっている状態から始めて、ＡさんとＢさんが以下の操作を２０２０回行う。
まず、Ａさんが相異なる８つのマスを選び、それらのマスに置かれている８枚のコインをすべて裏返す。次に、Ｂさんが行または列を１つ選び、その行または列に置かれている８枚のコインをすべて裏返す。
このとき、以下の条件をみたす最大の非負整数ｋを求めよ。
ＡさんはＢさんの行動にかかわらず、２０２０回の操作が終わったときに黒色の面が表になっているコインをｋ枚以上にできる。」
です。
早速、取り掛かりましょう。
Ａさんが任意の８つのマスを選ぶことができるのに対して、Ｂさんは行または列のいずれか１つしか選べないので、行または列のいずれか１つに置かれた８枚すべてが黒色コインでない状態以外では、Ａさんは黒色コインを増やすことが可能です。
そこで、各行各列に１つ以上の白色コインが置かれている状態を考えると、その簡単な例は、図１のような、マス目の対角線上に並んだマス（☆）白色のコインが置かれている場合です。
▲図１．マス目の対角線上のマスに白色のコインが置かれている状態を考えます
ここで、ｎ回目の操作の後で、マス目上にある黒色コインの個数をｂnとします。このとき、ｂ0＝０、 ｂ1＝８です。
まず、１回目のＡさんの操作で、図１の☆のマス以外の８マスを選んで、それらのマスに置かれている８枚のコインをすべて裏返すと、２行または２列以上に黒色コインが置かれることになります。（☆を黒色にしないので、各行各列には最大７個の黒色コインしか置けません）
そこで図２の左側の図ように、１回目のＡさんの操作で、マス目の１行目の２～８列目と２行目１列目のマスを黒色コインにした場合を考えます。
▲図２．マス目の１行目の２～８列目と２行目１列目のマスを黒色コインにした場合を考えます
このとき、２回目のＢさんの操作で、１行目を選んだ場合、図３の中央の図のように、２回目の操作後、ｂ2＝２になり、その他の行または列を選んだ場合、ｂ2＝１４または１６になります。
また、上記以外で、ある行または列に黒色コインが最大ｍ個（ｍ≦７）置かれるようにＡさんが操作し、続いてＢさんが黒色コインがｍ個置かれてる行または列を選んだ場合、
ｂ2＝８－ｍ＋（８－ｍ）＝１６－２ｍ
になり、したがって、
ｂ2≧２
です。
さらに、図２の右側の図のように、３回目のＡさんの操作で、マス目の１行１列目とその他の白色コインが置かれている７つのマスを選ぶ（図の場合は、１行１～７列目と３行目１列目）ことにより、マス目の対角線上の８つのマスに白色コインが置かれた状態に戻すことができます。
このように、Ａさんが、Ａさんの操作後にマス目の対角線上の８つのマスを白色コインにする操作を繰り返すことにより、高々（６４－８）÷２×２－１＝５５（回）の操作で、図３の左側の図のような状態にすることが可能で、それ以降の２０１９回目の操作までＢさんが選んだ行または列のコインを再び裏返すことにより、図３の左図の状態を２０１９回目の操作後まで保つことができます。
▲図３．奇数回目（≦５５）のＡさんの操作後と次のＢさんの操作です
２０２０回目のＢさんの操作では、いずれの行または列の１つを選んでも同じで、図３の右側の図のように、ｂ2020＝６４－１４＝５０です。
以上から、Ｂさんの操作にかかわらず、
ｂ2020≧５０ （☆）
であることが判りました。
次に、Ａさんの操作にかかわらず、ｂ2020≦５０ になるかを調べます。
初めに、マス目上の黒色コインの個数はいつでも偶数個になることを示します。
ある操作で、白色コインｍ個、黒色コイン８－ｍ個を裏返すと、黒色コインが増えた個数は、ｍ－（８－ｍ）＝２ｍ－８（個）で、これは偶数個です。
一方、１回目のＡさんの操作前のマス目上にある黒色コインの個数は０個（偶数）であることから、マス目上の黒色コインの個数はいつでも偶数個になります。
Ａさんのｉ回目の操作後、マス目上の黒色コインが５２個以上になるのは、その直前のＢさんのｉ－１回目操作後のマス目上の黒色コインの個数が、４４個、４６個、４８個または５０個のいずれかの場合で、そのとき、Ａさんのｉ回目の操作後のマス目上の黒色コインの個数は、それぞれ、５２個、５４個、５６個または５８個のいずれかになります。
一方、マス目上の黒色コインの枚数と、そのときの行または列に置かれる黒色コインの最大個数は、図４に示すように、
（マス目上の黒色コイン） → （行または列に置かれる黒色コインの最大個数） は、
・ ５２、５４、５６個の場合 → ７個以上
・ ５８個の場合 → ８個
です。
▲図４．マス目上の黒色コインの個数と各行各列に置かれる黒色コインの最大個数です
すると、Ａさんのｉ回目の操作後、マス目上の黒色コインが５２個、５４個、５６個の場合、Ｂさんのｉ＋１回目の操作で、黒色コインが７個以上の行または列を選ぶことにより、黒色コインを６個減らすことができるので、マス目上の黒色コインは、それぞれ、４６個、４８個、５０個、つまり、５０個以下になります。
さらに、Ａさんのｉ回目の操作後、マス目上の黒色コインが５８個の場合、Ｂさんのｉ＋１回目の操作で、黒色コインが８個の行または列を選ぶことにより、黒色コインを８個減らすことができるので、マス目上の黒色コインは、５０個になります。
したがって、Ａさんの操作でマス目上の黒色コインが５２個、５４個、５６個、５８個になった場合、Ｂさんは黒色コインが最大個数置かれている行または列を選んで操作することを２０２０回目まで繰り返すことにより、
ｂ2020≦５０
とすることができます。
以上から、Ａさんの操作にかかわらず、
ｂ2020≦５０ （★）
であることが判りました。
したがって、（☆）と（★）から、ｂ2020＝５０ であることから、ｋの最大値は ５０ で、これが答えです。
簡単な問題です。