はてなブックマークニュースで見た算数オリンピックの問題を、総当りせずに、算数的に解けたので嬉しくなってエントリ。
5×5のマス目に6個の○を次の条件を満たすように書きます。

条件:各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。

このとき、6個の○を書く方法は全部で何通りありますか。

仕事したり通勤したりしながらですが、なんだかんだで丸一日かかりました。制限時間内に解いた小学生はすごいなー

列ごとの◯の数

お絵かきロジックみたいな感じで、各行ごとの◯の数を表の上に書いてみます。

html

すると、条件を満たす配置をするとき、上の数字の並びは5パターンしかないことに気が付きました。

「各行・各列に少なくとも一つは◯を書く」ので、5つ数字はすべて「1」以上である必要があり、この時点で6つある◯のうち5つを使っているので、5つの数字のうち、どれか一つを「2」にするしかありません。つまり以下の5パターンしかないことになります。

  • 21111
  • 12111
  • 11211
  • 11121
  • 11112

同じことを行から列に置き換えても全く同じことが言えます。

html-1

これより「条件を満たすように◯を配置して列・行ごとの◯の数を数えた結果には5x5=25通りのパターンがある」ということが言えます。

ということは、列・行ごとの◯の数を固定した状態で配置パターンを数えて、それを25倍すれば答えが出そうです。

◯の数を固定して考える

html-2

◯の数を固定することで配置に制限ができました。この制限のおかげで考えるのがすごく楽になります。

「2」という数字が目立っているのでここから考えます。5マスの中に◯を2個書くパターンは10通りありますが、タテの「2」とヨコの「2」が交差するマスに◯を書くか書かないかで話が変わってきます。

html-3

上のように、交差するマスに◯を書くと、黄色の4マスには1つしか◯を書くことができなくなります。ピンクの4マスも同様です。

html-4

交差するマスに◯を書かないとなると、今度は黄色とピンクの4マスに2つの◯を書くことになります。

2つの場合それぞれについて◯の配置パターンを数えて両方の数を足すことにします。この数を25倍したものが最終的な答えになるはずです。

2つの「2」が重なるマスに◯を置かない場合

html-4

4マスに2つの◯を書くのでパターンの数は以下の6通りです。

  • oo__
  • o_o_
  • o__o
  • _oo_
  • _o_o
  • __oo

黄色もピンクも同じ条件でかつ黄色の配置がピンクの配置に制限をもたらすことがないので、黄色の6通りの配置それぞれにピンクの6通りをかけて、6x6=36通りの配置があることがわかりました。

「2」以外の列・行は全て「1」なので、黄色とピンクに◯が埋まると、◯を書くことができなくなるマスが発生します。上で出した36通りの配置どれを選んでも残りのマスは4個残ります。

html-5

残った4マスのどこかに◯を書くと、同じ列・行にある2つのマスが「置けないマス」として確定して残りのマスは1つになるので、◯の置き方は4x1=4通り。そのうち2つに1つは順序が違うだけなので2で割って2通りになります。

上で計算した黄色とピンクの36通りそれぞれに対して2通りのパターンがあることになり、36x2=72通りが「2が重なるマスに◯を置かない場合のパターン数」です。

2つの「2」が重なるマスに◯を置く場合

html-3

4マスに1つの◯を書くことになるのでパターンの数は4通りです。黄色とピンクがそれぞれ4通りあるので、「2」の行と列を埋める配置は4x4=16通りあることになります。

html-6

残ったマスは3x3の9マスです。これに残り3つの◯を配置します。さっきと同じように、空いているマスのどこかに◯を置くと、その影響で同じ列・行にある4つのマスが「置けないマス」として確定し、残り4マス2◯になります。

以下は前節と同様で9x4x1の36通り、順序が3x2=6通りあるので36/6=6通りが「3x3の9マスに3つの◯を配置パターンの数」です。

黄色とピンクの16通りそれぞれに3x3マスの6通りがあることになり、16x6=96通りが「2が重なるマスに◯を置く場合のパターン数」になります。

仕上げ

これで材料が出揃いました。これまでのパターン数を計算して最終的な答えを出します。

行・列ごとに◯の数を数えた結果のパターン25通りそれぞれに対して、「2」が重なるマスに◯を置かない場合が72通り、「2」が重なるマスに◯を置く場合が96通りあるので、25x(72+96)=4200通りの書き方があります。わーわー。パチパチパチ

感想

昨日の夜dankogaiがリハビリしているのを見て、楽しそうだなーと思って挑戦。C言語で解決する方法が示されていたので、パソコンを使わない算数的な解き方を考えてみました。

最初は難しくて手も足も出ませんでしたが、問題のスケールを落として「3x3のマスに4つの◯」という問題にして解いてみたら考えやすくなって本題の回答までたどり着きました。しかし解き方をひらめいた時の気持ち良さというのは堪えられないですね。楽しかったです。