こんにちは。東久留米市の学習塾塾長です。
今回は、2019年日本数学オリンピック予選に出題された場合の数の問題を取り上げます。
問題は、
「4×4のマス目の各マスを、赤、青、黄、緑のいずれかの1色で塗る方法のうち、どの行と列についても、次の3つの条件のうちのいずれかをみたすものは何通りあるか。
● 1色で4個のマスをすべて塗る
● 異なる2色でそれぞれ2個のマスを塗る
● 4色すべてでそれぞれ1個のマスを塗る
ただし、回転や裏返しにより一致する塗り方も異なるものとして数える。」
です。
早速、取り掛かりましょう。
与えられた条件の下で、4×1のマス目のマスに色を塗るとき、
(1) 3個のマスにA色が塗られた場合、残りの1個のマスもA色
(2) 2個のマスにA色、1個のマスにB色が塗られた場合、残りの1個のマスはB色
(3) 3個のマスに1個ずつA色、B色、C色が塗られた場合、残りの1個のマスはD色
というように、3個のマスに色が塗られた時点で残りの1個のマスの色が一意的に決定します。(このとき、3個のマスの色の塗り方はすべての場合を尽くしています)
例えば図1のように、第1列目c1の4個のマスのうち、マークした3個のマスに色が塗られると、残りのSに塗られる色は1つに決まり、また、第2行目のr2の4個のマスについても、マークした3個のマスに色が塗られると、残りのQに塗られる色は1つに決まります。

▲図1.4個のマスのうち3個のマスに色が塗られると残りの1個のマスの色は1通りに決まります
これは4×4のマス目のいずれの行、列でも同様なので、図2でマークした3×3のマス目の9個のマスに色が塗られると、、S、T、U、P、Q、Rに塗られる色は1つに決まることになります。

▲図2.マークしたマスに色が塗られるとS、T、U、P、Q、Rに塗られる色は1つに決まります
そこで問題となるのが、図2の第4列c4と第4行r4が共有するXに、与えられた条件をみたすように色を塗ることが可能かということです。
もしそれが可能ならば、条件をみたす色の塗り方は、3×3のマス目の9個のマスの色の塗り方になり、これは、それぞれのマスに赤、青、黄、緑のいずれを塗っても(1)、(2)、(3)のいずれかに該当するので、

になります。
そこで、ここから与えられた条件をみたすようにXを塗ることが可能かを調べていきましょう。
まず、赤=(0,0)、青=(1,0)、黄=(0,1)、緑=(1,1)、
Z=a(0,0)+b(1,0)+c(0,1)+d(1,1)
=(b+d,c+d)
(a、b、c、dは、0≦a,b,c,d≦4、a+b+c+d=4をみたす整数)
として、それぞれの与えられた条件でのZを調べていくと、
(4)「1色で4個のマスをすべて塗る」の場合
a=4,b=c=d=0 → Z=(0,0)
a=c=d=0,b=4 → Z=(4,0)
a=b=d=0,c=4 → Z=(0,4)
a=b=c=0,d=4 → Z=(2,2)
(5)「異なる2色でそれぞれ2個のマスを塗る」の場合
a=b=2,c=d=0 → Z=(2,0)
a=c=2,b=d=0 → Z=(0,2)
a=d=2,b=c=0 → Z=(2,2)
b=c=2,a=d=0 → Z=(2,2)
b=d=2,a=c=0 → Z=(4,2)
c=d=2,a=b=0 → Z=(2,4)
(6)「4色すべてでそれぞれ1個のマスを塗る」の場合
a=b=c=d=1 → Z=(2,2)
のように、Z=(b+d,c+d)のb+dとc+dはどちらも偶数になることが判ります。
逆に、b+dとc+dが共に偶数になる場合のa、b、c、dの組合せは、
・a=4,b=c=d=0
・b=4,a=c=d=0
・c=4,a=b=d=0
・d=4,a=b=c=0
・a=b=2,c=d=0
・a=c=2,b=d=0
・a=d=2,b=c=0
・b=c=2,a=d=0
・b=d=2,a=c=0
・c=d=2,a=b=0
・a=b=c=d=1
で、これは(4)、(5)、(6)の組合せと一致します。
一方、b+d(またはc+d)が奇数になるときは、bとdのいずれが1つが奇数で他が偶数(またはcとdのいずれか1つが奇数で他が偶数)の場合で、これをみたす組合せは(4)、(5)、(6)にありません。
つまり、Z=(b+d,c+d)で、b+dとc+dが共に偶数になるものは、与えられた条件をみたす塗り方になり、b+dとc+dのいずれかが奇数になるものは、与えられた条件をみたす塗り方にならないことが判ります。
そこで、ここからZを利用して調べていくことにしましょう。
まず図3の左側の図に示すように、各列は与えられた条件をみたすように色を塗ることが可能なので、各列のZは(偶数,偶数)になり、したがって、4×4のマス目の16個のマスの和も(偶数,偶数)になります。

▲図3.各列のZが(偶数,偶数)なので、4×4のマス目の16個のマスの和も(偶数,偶数)です
一方、図3の右側の図のように、r1、r2、r3は与えられた条件をみたすように色を塗ることが可能なので、これらの行のZは(偶数,偶数)になり、これらの3×4のマス目の12個のマスの和も(偶数,偶数)になります。
すると、4×4のマス目の16個の和が(偶数,偶数)で、3×4のマス目の12個のマス目の和が(偶数,偶数)なので、これらの差であるr4 のZは(偶数,偶数)になり、r4 は与えられた条件をみたすように色を塗ることが可能と判ります。
以上から、4×4のマス目の各マスを、赤、青、黄、緑のいずれかの1色で塗る方法のうち与えられた条件をみたすものは、

で、これが答えです。
楽しい問題です。
今回は、2019年日本数学オリンピック予選に出題された場合の数の問題を取り上げます。
問題は、
「4×4のマス目の各マスを、赤、青、黄、緑のいずれかの1色で塗る方法のうち、どの行と列についても、次の3つの条件のうちのいずれかをみたすものは何通りあるか。
● 1色で4個のマスをすべて塗る
● 異なる2色でそれぞれ2個のマスを塗る
● 4色すべてでそれぞれ1個のマスを塗る
ただし、回転や裏返しにより一致する塗り方も異なるものとして数える。」
です。
早速、取り掛かりましょう。
与えられた条件の下で、4×1のマス目のマスに色を塗るとき、
(1) 3個のマスにA色が塗られた場合、残りの1個のマスもA色
(2) 2個のマスにA色、1個のマスにB色が塗られた場合、残りの1個のマスはB色
(3) 3個のマスに1個ずつA色、B色、C色が塗られた場合、残りの1個のマスはD色
というように、3個のマスに色が塗られた時点で残りの1個のマスの色が一意的に決定します。(このとき、3個のマスの色の塗り方はすべての場合を尽くしています)
例えば図1のように、第1列目c1の4個のマスのうち、マークした3個のマスに色が塗られると、残りのSに塗られる色は1つに決まり、また、第2行目のr2の4個のマスについても、マークした3個のマスに色が塗られると、残りのQに塗られる色は1つに決まります。

▲図1.4個のマスのうち3個のマスに色が塗られると残りの1個のマスの色は1通りに決まります
これは4×4のマス目のいずれの行、列でも同様なので、図2でマークした3×3のマス目の9個のマスに色が塗られると、、S、T、U、P、Q、Rに塗られる色は1つに決まることになります。

▲図2.マークしたマスに色が塗られるとS、T、U、P、Q、Rに塗られる色は1つに決まります
そこで問題となるのが、図2の第4列c4と第4行r4が共有するXに、与えられた条件をみたすように色を塗ることが可能かということです。
もしそれが可能ならば、条件をみたす色の塗り方は、3×3のマス目の9個のマスの色の塗り方になり、これは、それぞれのマスに赤、青、黄、緑のいずれを塗っても(1)、(2)、(3)のいずれかに該当するので、

になります。
そこで、ここから与えられた条件をみたすようにXを塗ることが可能かを調べていきましょう。
まず、赤=(0,0)、青=(1,0)、黄=(0,1)、緑=(1,1)、
Z=a(0,0)+b(1,0)+c(0,1)+d(1,1)
=(b+d,c+d)
(a、b、c、dは、0≦a,b,c,d≦4、a+b+c+d=4をみたす整数)
として、それぞれの与えられた条件でのZを調べていくと、
(4)「1色で4個のマスをすべて塗る」の場合
a=4,b=c=d=0 → Z=(0,0)
a=c=d=0,b=4 → Z=(4,0)
a=b=d=0,c=4 → Z=(0,4)
a=b=c=0,d=4 → Z=(2,2)
(5)「異なる2色でそれぞれ2個のマスを塗る」の場合
a=b=2,c=d=0 → Z=(2,0)
a=c=2,b=d=0 → Z=(0,2)
a=d=2,b=c=0 → Z=(2,2)
b=c=2,a=d=0 → Z=(2,2)
b=d=2,a=c=0 → Z=(4,2)
c=d=2,a=b=0 → Z=(2,4)
(6)「4色すべてでそれぞれ1個のマスを塗る」の場合
a=b=c=d=1 → Z=(2,2)
のように、Z=(b+d,c+d)のb+dとc+dはどちらも偶数になることが判ります。
逆に、b+dとc+dが共に偶数になる場合のa、b、c、dの組合せは、
・a=4,b=c=d=0
・b=4,a=c=d=0
・c=4,a=b=d=0
・d=4,a=b=c=0
・a=b=2,c=d=0
・a=c=2,b=d=0
・a=d=2,b=c=0
・b=c=2,a=d=0
・b=d=2,a=c=0
・c=d=2,a=b=0
・a=b=c=d=1
で、これは(4)、(5)、(6)の組合せと一致します。
一方、b+d(またはc+d)が奇数になるときは、bとdのいずれが1つが奇数で他が偶数(またはcとdのいずれか1つが奇数で他が偶数)の場合で、これをみたす組合せは(4)、(5)、(6)にありません。
つまり、Z=(b+d,c+d)で、b+dとc+dが共に偶数になるものは、与えられた条件をみたす塗り方になり、b+dとc+dのいずれかが奇数になるものは、与えられた条件をみたす塗り方にならないことが判ります。
そこで、ここからZを利用して調べていくことにしましょう。
まず図3の左側の図に示すように、各列は与えられた条件をみたすように色を塗ることが可能なので、各列のZは(偶数,偶数)になり、したがって、4×4のマス目の16個のマスの和も(偶数,偶数)になります。

▲図3.各列のZが(偶数,偶数)なので、4×4のマス目の16個のマスの和も(偶数,偶数)です
一方、図3の右側の図のように、r1、r2、r3は与えられた条件をみたすように色を塗ることが可能なので、これらの行のZは(偶数,偶数)になり、これらの3×4のマス目の12個のマスの和も(偶数,偶数)になります。
すると、4×4のマス目の16個の和が(偶数,偶数)で、3×4のマス目の12個のマス目の和が(偶数,偶数)なので、これらの差であるr4 のZは(偶数,偶数)になり、r4 は与えられた条件をみたすように色を塗ることが可能と判ります。
以上から、4×4のマス目の各マスを、赤、青、黄、緑のいずれかの1色で塗る方法のうち与えられた条件をみたすものは、

で、これが答えです。
楽しい問題です。
※コメント投稿者のブログIDはブログ作成者のみに通知されます