算数オリンピック：悔しかったので n×n のマス目で解いてみた。

難しいなあ…: 思いついたことをなんでも書いていくブログ

こちらで解けなかった算数オリンピックの「第4問」について。
悔しいのであれからずっと考えていました。で、今日解けた。会議中だったのは秘密。

5×5のマス目に6個の○を次の条件を満たすように書きます。 条件：各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。

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

どうしてもケースが思いつかず、最後はグーグル神様に泣きついたら、「知恵袋」先生を訪ねるようご託宣頂き、そこでいただいた偉大なるヒントのおかげで解けました。

もうあちこちに解答がありますので屋上屋を重ねるわけですが、せっかく自分で解いたのでうれしくて記念に書いておきます。

n×nのマス目の場合、次のように問題を変更しました。

n×n のマス目に n+1 個の○を次の条件を満たすように書きます。
条件：各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。

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

この解は、n!n(n-1) + n^2(n-3)! (_n-1C₂)^2 ですね（ただしn>=3）。

第2項ですが、

		２		＿
		○
２	○	×	○
		○

みたいなケースで、×の位置に注目して、4つの○を先に配置することを考えます。で、

1．列に注目して、○がない列が n-3 列あり、それらの列に、先に配置した4つの○とかぶらないように○を入れていくことを考えます。すると、各列は n-3 個のマスに一つずつ○を入れていくことになるので、その入れ方は (n-3)!通りあります。

2．上の図のように、どこかのマス目に×を入れたとき、そこの行・列にちょうど2個ずつ○が入る仕方を考えます。列の配置を固定して行の入れ方を考えると、1行にはマス目が n 個あり、×以外に○を2個入れるのですから、その入れ方は _n-1C₂ 通りになります。列についても同じことが言えるので、結局、(_n-1C₂)^2 通りになります。

3．最後に×の入れ方を考えますが、これはどこのマス目に入れても大丈夫ですので、n^2通りあります。

これらを掛け合わせて第2項が出ます。

で、n!n(n-1) + n^2(n-3)! (_n-1C₂)^2 を整理すると、n!n(n-1)(n+2)/4 という形になりました。すっきりした！

おかげさまでここしばらくの会議中、充実した時間が過ごせました。数学問題ってどこにでも持って行けてすごく都合がいいですよね。また次の問題を探そうっと。