算数オリンピックの問題（小学生向け）

とやさん経由で。
http://b.hatena.ne.jp/articles/201101/2261

下記、最後の問題に悩んでしまった…。

＜問題＞
5×5のマス目に6個の○を次の条件を満たすように書きます。

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

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

「プログラムで解く」という趣旨から外れるけど（って、そういう趣旨だったのか？！）、思い切り算数で解いてみました。なんとか解けたんじゃないかなあ*1。
以下、ネタバレにつき「続きを読む」記法にて。正解＆解説歓迎でっす。

この問題のポイント

「まず5個を各行各列重複しないように入れて、残りの1個を好きなところに入れれば終了、よって2400通り」という発想から離れることが重要。俺、この発想から離れるのに1時間近くかかった…orz

基本的な考え方

まずは各行各列に少なくとも1個は入れなければならない以上、入れ方は、(1)6個のうち5個の○を、各行各列に配置する組み合わせと、(2)4個の○を各行各列に重複しないように入れて、5個目6個目を空いている行、空いている列に入れる（ただし(1)と重複しないよう、空いている行かつ列には入れない）、の2パターンが考えられる。
(1)は、まず5個を入れる組み合わせが、5!＝5×4×3×2×1＝120通り。残り1個の○は、空いている20マスのうちどこに入れてもいいので、入れ方の組み合わせは全部で、120×20＝2400通り…[1]
(2)がちょっと厄介。まず4行4列に重複しないように4個を入れる組み合わせは、4!＝4×3×2×1＝24通り。残りの2個は、(1)と重複しないように入れようと思うと、空いている行のうち4カ所、空いている列のうち4カ所にそれぞれ入りうるので、各行4通り×各列4通り＝16通り。また、4行4列の選び方が、（1個しか入らない行と列を選ぶ選び方なので）5行×5列＝25通り。これを全部乗じて、24×25×16＝9600通り…[2]
ただし、(2)には重複がある。2個入ってる行が2つ、2個入ってる列が2つある。4行4列のうち、それぞれ2カ所に入るので、各行及び各列に入れる組み合わせは、4C2＝（4×3×2×）÷（2×1）＝12通り。上述の通り、4行4列に重複しないように4つの○を入れる組み合わせは、5×5＝25通りあるので、12×12×25＝3600通り…[3]
よって、[1]＋[2]−[3]＝2400＋9600−3600＝8400通り（答え）。

考察：(1)の2400通りの中には同じ配置（重複）はないの？？

各行各列に入れた5個の○をA、B、C、D、Eとし、6個目の○をFとする。
このとき、Fを、Aと同じ行または列に入れた時、B、C、D、Eの配置によって「各行各列に少なくとも1個は○を書く」という条件を満たすAの位置は一意に決まるため、どのような位置にFを入れても、B、C、D、E、Fの配置は「各行各列に少なくとも1個は○を書く」という条件を満たさない。
このため、Fがどこに入った場合でも、B、C、D、E、Fの配置は、各行各列に入れた120通りのいかなる配置と重複はせず、よって2400通りの中に重複がある可能性は考慮する必要がない。

と、ここまで考えたけど

まだ(2)の重複排除が甘い気がする…。もう少し考えてみます。とほほ。

*1:1/26追記：なんとか解けたか？…と、この時は思ってたけど、答えの数値だけをチェックしたら、間違えてることが判明。といいつつ、考え方の経緯を書き残しておくことは無駄じゃないと思うので、間違っていると知りつつ残しておくことにします。