|
けーすけ |
|
一般化にトライしてみました。
横ｎ列、縦ｎ行の格子点のうち1行で 2箇所を選ぶ選び方は、 nC2＝n(n-1)/2 通りで、これをなるべくｎ行で均等に分ける場合が 最も碁石を多く使うことになります。（証明省略） 1行平均 (m-1)/2n個 各行にp個またはp+1個の碁石を配置するとすれば、 pC2 ≦ (n-1)/2 ＜ (p+1)C2 → p(p-1) ≦ (n-1) ＜ p(p+1) 1/4を加えて因数分解すると、 (p-1/2)＾2 ≦ n-3/4 ＜ (p+1/2)＾2 → ｐ ＝ Int{1/2＋√(n-3/4)} となります。 （Int：小数点以下切り捨て） 各行p個の碁石で網羅出来ないパターン（碁石2個の組み合わせ）は、 n(n-1)/2 - np(p-1)/2 通りで、その差を埋めるため、1行1個ずつ碁石を増やしていきます。 碁石を1個増やす行数をq行とします。 1行の碁石をp個→（p+1）個に増やす場合、碁石2個の組み合わせは p通り増えるので、 qは上記網羅出来ないパターン数をpで割った数になります。 （余り切り捨て） q ＝ Int{n(n-1)/(2p)-n(p-1)/2} 上記を用い、碁石の数の合計は、 np+q となります。 検証すると、 n p q 碁石の数 3 2 0 6 4 2 1 9 5 2 2 12 6 2 4 16 7 3 0 21 8 3 1 25 ・・・・ 100 10 45 1045 |
|
11月21日（木） 20:46:31
41135 |