第247問の解答


1.問題 規則性

何個かの碁石がになっています。
まず、この2つに分けます。分けた山をさらに2つに分け・・・という作業を全部の1個ずつになるまで続けます。
また、2つに分けるたびに、2つ碁石の数かけた数をノートに記録します。

すると、ノートに記録された数の合計120であったそうです。
では、碁石何個あったでしょうか。

2.解答例1Taroさん、たなかさん、丸天後藤様むらかみさん、中村明海さん、あんみつさん、KINさん、TORAさん、名倉っちさん、ふじさきたつみさん、BossFさん、M.Hossieさん、有無相生さん、鈴木オヤジさん、うっしーさん、他多数)

山の分け方によらないと仮定して、1個ずつ分けていくことにします。

参考図1 参考図2

碁石の数が個とします。
最初の1個を分けると、記録する数は1×(n−1)=n−1
2番目の1個を分けると、記録する数は1×(n−2)=n−2
3番目の1個を分けると、記録する数は1×(n−3)=n−3
 ・・・
となり、記録した数の合計は、
 1+2+・・・+(n−1)=n(n−1)/2
となります。

参考図3

n(n−1)/2=120より、n=16個と分かります。


碁石の数がn個のとき、記録した数の合計をf(n)とします。
山の分け方によらず、f(n)=n(n-1)/2・・(A)となることを帰納法で示します。

(1)n=2のとき、f(2)=2・1/2=となり、OK.

(2)(n-1)個以下のとき、(A)が成り立つと仮定。

  n個のとき、まずk個(n-k)個に分けたとすると、

参考図4

 f(n)f(k)f(n-k)k(n-k) ・・・(B)
   =k(k-1)/2+(n-k)(n-k-1)/2+k(n-k)
   =k(k-1)/2+{n2/2−(2k+1)/2・n+k(k+1)/2}+kn-k2
   =n2/2−n/2
   =n(n-1)/2

よって、n個のときも(A)は、成り立つ。

以上から、数学的帰納法により、(A)は任意の(n≧2)で成り立つことが分かる。

答:16個

以上


3.解答例2ヒデー王子さん、数楽者さん、他)

同じ山にある碁石は互いにひもで結ばれていると考えることにしましょう。
碁石がn個あれば、ひもの数はnC2=n(n-1)/2本

参考図5  

n個ある碁石をk個(n-k)個に分けたとき、
k個の山の碁石は、ひもの数kC2=k(k-1)/2本
(n-k)個の山の碁石は、ひもの数n-kC2=(n-k)(n-k-1)/2本
そして2つに分かれた碁石間のひもk(n-k)本は切ることになる。
(これは、解答例1の(B)に対応している)

すなわち、本問題の2つに分けたときに記録する数は、この切ったひもの本数に等しい。

従って、全部の山の碁石がすべて1個になったときは、全てのひもを切ったことになるので、記録された数の合計は元のひもの本数n(n-1)/2本に等しい。

以下、解答例1と同様。


(その他の解法)