 nothing ( No.5 ) |
- 日時： 2012/06/14 22:09
- 名前： KST
- それでは、解答・解説のお時間です。
［解答］
求める最大値は、16個である。以下、これを証明する。
まず、像16個の配置は存在する。例えば、次のように配置すれば、これは条件を満たす。
¶¶¶○○○
¶○○¶¶○
○¶○¶○¶
○¶○○¶○
○○¶¶○○
○○¶○¶¶
次に最大値が16個であることを証明する。
6×6のマス目に像を17個置いたとき、必ず傾いていない長方形ができる(ダメな配置になる)ことを示せば良い。
1以上6以下の自然数iにおいて、マス目のi列目に置く像の個数をti(≧0)とおく。
t1+t2+t3+t4+t5+t6=17に注意する。
このとき、各列において、置いた像のうち、2個を選ぶ方法の総数(置いた像が1個以下の場合は0通りと数える)の、6列における総和が、6マスから2マス選ぶ方法の数より大きければ、鳩の巣原理より、必ず傾いていない長方形ができることが分かる。
すなわち、n個からk個選ぶ場合の数を(n,k)と表すことにして、
(t1,2)+(t2,2)+(t3,2)+(t4,2)+(t5,2)+(t6,2)＞(6,2)=15
となれば良い。
また、コーシー・シュワルツの不等式より、
(t12+t22+t32+t42+t52+t62)(12+12+12+12+12+12)≧(t1+t2+t3+t4+t5+t6)2
なので、
(t12+t22+t32+t42+t52+t62)≧172/6
が成り立つ。
よって、
(t1,2)+(t2,2)+(t3,2)+(t4,2)+(t5,2)+(t6,2)−15
=1/2｛t1(t1−1)+t2(t2−1)+t3(t3−1)+t4(t4−1)+t5(t5−1)+t6(t6−1)｝−15
=1/2(t12+t22+t32+t42+t52+t62)−1/2(t1+t2+t3+t4+t5+t6)−15
=1/2(t12+t22+t32+t42+t52+t62)−17/2−15
≧1/2・172/6−17/2−15
=7/12＞0
より、示された。
|
|
FAQ
RSS