読者です 読者をやめる 読者になる 読者になる

数学塾variée@吉祥寺

数学塾の中の人の日記

素因数分解してきづいた(2012 JMO予選6)

授業で 2012 年の JMO 予選の問題を扱いました。

2 x 100 のマス目があり,各マスを赤または青で塗りつぶす。以下の2つの条件をともにみたすような塗り方は何通りあるか。ただし,回転や裏返しにより重なりあう塗り方も異なるものとして数える。

  • 赤く塗られたマスも青く塗られたマスもそれぞれ1つ以上存在する。
  • 赤く塗られたマス全体は 1 つに繋がっており,青く塗られたマス全体も 1 つに繋がっている。ここで,異なる 2 つのマスは辺を共有するときに繋がっていると考える。

最初に考えたのは「左上が青の場合を数えて 2 倍すればいい」です。書き出してみると 5 パターンありました。

f:id:variee:20131221213204p:plain

生徒も「数えた」と言ってましたが,まあ普通は数えますよね。

答えは 39800 = 200 x 199 です。答えを見てから気づいたのですが,多角形(≒ 円上の点)と対応づけられます。例えば赤 1 枚のとき配置は 200 通りあり,これは赤の枚数によりません。

f:id:variee:20131221215332p:plain

赤の枚数が 1 枚から 199 枚までの 199 通り。その配置が各 200 通りあるので,計 200 x 199 = 39800 通りです。軽くて予選らしい,いい問題だと思います。