« 日本語って一つじゃないんだな、と。 | トップページ | 保守主義(?)の強さをかいま見た思いがした »

2011/02/26

算数オリンピック:悔しかったので 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-1C2)^2 ですね(ただしn>=3)。

第2項ですが、

      _
×
 

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

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

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

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

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

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

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

« 日本語って一つじゃないんだな、と。 | トップページ | 保守主義(?)の強さをかいま見た思いがした »

日記・コラム・つぶやき」カテゴリの記事

コメント

この記事へのコメントは終了しました。

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/83801/50974574

この記事へのトラックバック一覧です: 算数オリンピック:悔しかったので n×n のマス目で解いてみた。:

« 日本語って一つじゃないんだな、と。 | トップページ | 保守主義(?)の強さをかいま見た思いがした »