日本数学オリンピック予選の問題（９）

こんにちは。東久留米市の学習塾塾長です。

今回は、２０１９年日本数学オリンピック予選に出題された場合の数の問題を取り上げます。

問題は、
「４×４のマス目の各マスを、赤、青、黄、緑のいずれかの１色で塗る方法のうち、どの行と列についても、次の３つの条件のうちのいずれかをみたすものは何通りあるか。

● １色で４個のマスをすべて塗る

● 異なる２色でそれぞれ２個のマスを塗る

● ４色すべてでそれぞれ１個のマスを塗る

ただし、回転や裏返しにより一致する塗り方も異なるものとして数える。」
です。

早速、取り掛かりましょう。

与えられた条件の下で、４×１のマス目のマスに色を塗るとき、
（１） ３個のマスにＡ色が塗られた場合、残りの１個のマスもＡ色
（２） ２個のマスにＡ色、１個のマスにＢ色が塗られた場合、残りの１個のマスはＢ色
（３） ３個のマスに１個ずつＡ色、Ｂ色、Ｃ色が塗られた場合、残りの１個のマスはＤ色
というように、３個のマスに色が塗られた時点で残りの１個のマスの色が一意的に決定します。（このとき、３個のマスの色の塗り方はすべての場合を尽くしています）

例えば図１のように、第１列目ｃ1の４個のマスのうち、マークした３個のマスに色が塗られると、残りのＳに塗られる色は１つに決まり、また、第２行目のｒ2の４個のマスについても、マークした３個のマスに色が塗られると、残りのＱに塗られる色は１つに決まります。

▲図１．４個のマスのうち３個のマスに色が塗られると残りの１個のマスの色は１通りに決まります

これは４×４のマス目のいずれの行、列でも同様なので、図２でマークした３×３のマス目の９個のマスに色が塗られると、、Ｓ、Ｔ、Ｕ、Ｐ、Ｑ、Ｒに塗られる色は１つに決まることになります。

▲図２．マークしたマスに色が塗られるとＳ、Ｔ、Ｕ、Ｐ、Ｑ、Ｒに塗られる色は１つに決まります

そこで問題となるのが、図２の第４列ｃ4と第４行ｒ4が共有するＸに、与えられた条件をみたすように色を塗ることが可能かということです。

もしそれが可能ならば、条件をみたす色の塗り方は、３×３のマス目の９個のマスの色の塗り方になり、これは、それぞれのマスに赤、青、黄、緑のいずれを塗っても（１）、（２）、（３）のいずれかに該当するので、

になります。

そこで、ここから与えられた条件をみたすようにＸを塗ることが可能かを調べていきましょう。

まず、赤＝（０，０）、青＝（１，０）、黄＝（０，１）、緑＝（１，１）、
Ｚ＝ａ（０，０）＋ｂ（１，０）＋ｃ（０，１）＋ｄ（１，１）
　＝（ｂ＋ｄ，ｃ＋ｄ）
（ａ、ｂ、ｃ、ｄは、０≦ａ，ｂ，ｃ，ｄ≦４、ａ＋ｂ＋ｃ＋ｄ＝４をみたす整数）
として、それぞれの与えられた条件でのＺを調べていくと、

（４）「１色で４個のマスをすべて塗る」の場合
ａ＝４，ｂ＝ｃ＝ｄ＝０ →　Ｚ＝（０，０）
ａ＝ｃ＝ｄ＝０，ｂ＝４ →　Ｚ＝（４，０）
ａ＝ｂ＝ｄ＝０，ｃ＝４ →　Ｚ＝（０，４）
ａ＝ｂ＝ｃ＝０，ｄ＝４ →　Ｚ＝（２，２）

（５）「異なる２色でそれぞれ２個のマスを塗る」の場合
ａ＝ｂ＝２，ｃ＝ｄ＝０ →　Ｚ＝（２，０）
ａ＝ｃ＝２，ｂ＝ｄ＝０ →　Ｚ＝（０，２）
ａ＝ｄ＝２，ｂ＝ｃ＝０ →　Ｚ＝（２，２）
ｂ＝ｃ＝２，ａ＝ｄ＝０ →　Ｚ＝（２，２）
ｂ＝ｄ＝２，ａ＝ｃ＝０ →　Ｚ＝（４，２）
ｃ＝ｄ＝２，ａ＝ｂ＝０ →　Ｚ＝（２，４）

（６）「４色すべてでそれぞれ１個のマスを塗る」の場合
ａ＝ｂ＝ｃ＝ｄ＝１　　 →　Ｚ＝（２，２）

のように、Ｚ＝（ｂ＋ｄ，ｃ＋ｄ）のｂ＋ｄとｃ＋ｄはどちらも偶数になることが判ります。

逆に、ｂ＋ｄとｃ＋ｄが共に偶数になる場合のａ、ｂ、ｃ、ｄの組合せは、
・ａ＝４，ｂ＝ｃ＝ｄ＝０
・ｂ＝４，ａ＝ｃ＝ｄ＝０
・ｃ＝４，ａ＝ｂ＝ｄ＝０
・ｄ＝４，ａ＝ｂ＝ｃ＝０
・ａ＝ｂ＝２，ｃ＝ｄ＝０
・ａ＝ｃ＝２，ｂ＝ｄ＝０
・ａ＝ｄ＝２，ｂ＝ｃ＝０
・ｂ＝ｃ＝２，ａ＝ｄ＝０
・ｂ＝ｄ＝２，ａ＝ｃ＝０
・ｃ＝ｄ＝２，ａ＝ｂ＝０
・ａ＝ｂ＝ｃ＝ｄ＝１
で、これは（４）、（５）、（６）の組合せと一致します。

一方、ｂ＋ｄ（またはｃ＋ｄ）が奇数になるときは、ｂとｄのいずれが１つが奇数で他が偶数（またはｃとｄのいずれか１つが奇数で他が偶数）の場合で、これをみたす組合せは（４）、（５）、（６）にありません。

つまり、Ｚ＝（ｂ＋ｄ，ｃ＋ｄ）で、ｂ＋ｄとｃ＋ｄが共に偶数になるものは、与えられた条件をみたす塗り方になり、ｂ＋ｄとｃ＋ｄのいずれかが奇数になるものは、与えられた条件をみたす塗り方にならないことが判ります。

そこで、ここからＺを利用して調べていくことにしましょう。

まず図３の左側の図に示すように、各列は与えられた条件をみたすように色を塗ることが可能なので、各列のＺは（偶数，偶数）になり、したがって、４×４のマス目の１６個のマスの和も（偶数，偶数）になります。

▲図３．各列のＺが（偶数，偶数）なので、４×４のマス目の１６個のマスの和も（偶数，偶数）です

一方、図３の右側の図のように、ｒ1、ｒ2、ｒ3は与えられた条件をみたすように色を塗ることが可能なので、これらの行のＺは（偶数，偶数）になり、これらの３×４のマス目の１２個のマスの和も（偶数，偶数）になります。

すると、４×４のマス目の１６個の和が（偶数，偶数）で、３×４のマス目の１２個のマス目の和が（偶数，偶数）なので、これらの差であるｒ4 のＺは（偶数，偶数）になり、ｒ4 は与えられた条件をみたすように色を塗ることが可能と判ります。

以上から、４×４のマス目の各マスを、赤、青、黄、緑のいずれかの１色で塗る方法のうち与えられた条件をみたすものは、

で、これが答えです。


楽しい問題です。