パズル万華鏡

面白いパズルの紹介と解説をします。

山分け問題(1)の解1

 山分け問題(1)の解答例を示します。

 

問題(1)の解1

 数学的帰納法で示す。

 求める総和をf(n)=n(n-1)/2と仮定する。

(A)n=2の時、f(2)=1となり、明らか。

(B)n≦k のとき成り立つと仮定し、n=k+1のときを考える。

石の数k+1個の山を、mとk+1-mに分ける。1≦m≦k。

  f(k+1) = m(k+1-m) + f(m) + f(k+1-m)

     = m(k+1-m) + m(m-1)/2 + (k+1-m)(k-m)/2

     = (k+1)k/2

(A),(B)により、命題は示された。

f:id:isemba:20170811062500j:plain