JMO予選2019問9


答え\(\cdots4^9(=262144)\)
【分析】
まず、気付くべきは
・どの行・列も3つの数を決めれば、残り1つも決まる
(∵色をA,B,C,Dのように表すと、
A,A,Aで塗られてる→残りはA
A,A,Bで塗られてる→残りはB
A,B,Cで塗られてる→残りはD)
というこの事実でしょう。すると次に気になるのが、
・実は左上の3×3マスの塗り方を決めれば、残り7マスは自動的に決められるのでは?
ということです。右下の1マスを除けば、これは上の事実から当たり前ですが、残りの右下の1マスが一番右の列と一番下の行がともに条件を満たすように塗れるかというのが問題です。
しかし、これは実験していけば、左上の9マスをどう塗っても条件を満たすように残りの7マスを塗ることができる様子がわかってきます!
∴求める答えは\(4^9\)なのですが、ここでは、今の予想が正しいことを証明していくことにしましょう。それは、「色に数を対応させる」というこの手の問題ではありがちな考え方で綺麗に証明できます。

【略証】
赤,青,黄,緑を(0,0),(0,1),(1,0),(1,1)に対応させ、「行の合計」・「列の合計」というのを、そこに書かれた色に対応するものを成分同士足したものとする。
例えば、青,青,黄,緑で書かれた列の合計は(0,1)+(0,1)+(1,0)+(1,1)=(2,3)である。
すると、

$$
行・列が条件を満たす塗り方である\\
⇔行・列の合計の成分はどちらも偶数である…①$$


といったことが確かめられる。
今、左上の3×3マスを適当に4色で塗ってみたとすると、最初に述べたよう、上3行が条件を満たすように一番右の列の上3マスの色が自動的に1つ決まり、さらに、4列全てが条件を満たすように一番下の行4マスの色も自動的に1つに決まります。
問題はこのとき、一番下の行も条件を満たしているのかということですが、現時点でどの列も条件を満たしているので、どの列の合計も(偶数,偶数)の形です。
∴「16マス全ての合計」というのを考えてみてもやっぱり(偶数,偶数)の形です。
そして、上3行はすでに条件を満たすことがわかっていたので、上3行に対して、行の合計は全て(偶数,偶数)の形ですから、一番下の行の合計も(偶数,偶数)の形となり、一番下の行も確かに条件を満たすことがわかる。
∴求める場合の数は左上の3×3マスの色の決め方で、\(4^9\)通り

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です