『果物の分配』

『果物の分配』解答

◆宮城県　斉藤　誠さんからの解答。

果物が２個（猿２匹）の場合は
Ｍ（２，１）　　２，０
Ｍ（２，２）　　１，１

果物が３個（猿３匹）の場合は
Ｍ（３，１）　　３，０，０
Ｍ（３，２）　　２，１，０
Ｍ（３，３）　　１，１，１

【問題１、２】

果物が４個（猿４匹）の場合は
Ｍ（４，１）　　４，０，０，０
Ｍ（４，２）　　３，１，０，０
　　　　　　　　２，２，０，０
Ｍ（４，３）　　２，１，１，０
Ｍ（４，４）　　２，１，１，０

果物が５個（猿５匹）の場合は
Ｍ（５，１）　　５，０，０，０、０
Ｍ（５，２）　　４，１，０，０、０
　　　　　　　　３，２，０，０、０
Ｍ（５，３）　　３，１，１，０、０
　　　　　　　　２，２，１，０、０
Ｍ（５，４）　　２，１，１，１、０
Ｍ（５，５）　　１，１，１，１、１

【問題３】

Ｍ（ｎ，ｎ）　　　＝１
Ｍ（ｎ，ｎ−１）＝１
Ｍ（ｎ，１）　　　＝１

【問題４】
Ｍ（ｎ，２）＝［ｎ
――
２		］

【問題５】

（１）

ｋ＞ｎ
――
２		のとき
Ｍ（ｎ，ｋ）＝Ｍ（ｎ−１，ｋ−１）について
Ｍ（５，３）　　３，１，１
　　　　　　　　２，２，１
Ｍ（５，４）　　２，１，１，１
のようにｋがｎの半分以上の場合には一番右が全て１になるので
赤字部分がＭ（ｎ−１，ｋ−１）に等しくなる

（２）

ｋ≦ｎ
――
２		のとき
Ｍ（ｎ，ｋ）＝Ｍ（ｎ−１，ｋ−１）＋Ｍ（ｎ−ｋ，ｋ）について
ｎ＝６の調査が必要。
Ｍ（６，１）　　６，０，０，０、０、０
Ｍ（６，２）　　５，１，０，０、０、０
　　　　　　　　４，２，０，０、０、０
　　　　　　　　３，３，０，０、０、０
Ｍ（６，３）　　４，１，１，０、０、０
　　　　　　　　３，２，１，０、０、０
　　　　　　　　２，２，２，０、０、０
Ｍ（６，４）　　３，１，１，１、０、０
　　　　　　　　２，２，１，１，０，０
Ｍ（６，５）　　２，１，１，１、１、０
Ｍ（６，６）　　１，１，１，１、１、１

となりＭ（６，３）を例にすると
Ｍ（６，３）　　４，１、１
　　　　　　　　３，２、１
　　　　　　　　２，２、２
のように赤字の部分がＭ（ｎ−１，ｋ−１）と同じ、
最後の１行はｎ→ｎーｋにした（ｎは３（＝ｋ）減るので）
Ｍ（３，３）　　１，１、１
と同じ。すなわちＭ（ｎ−３，ｋ）
Ｍ（ｎ，ｋ）＝Ｍ（ｎ−１，ｋ−１）＋Ｍ（ｎ−ｋ，ｋ）が示される。

【問題６】

ｋ≧ｎ
――
２		のとき
（１）　ｋ＝ｎ
――
２		の場合
この場合はｎが偶数に限られるのでＭ（６，３）を例にすると
Ｍ（６，３）　　４，１，１，０、０、０
　　　　　　　　３，２，１，０、０、０
　　　　　　　　２，２，２，０、０、０
ｎから３（＝ｋ）を引いて各猿から１ずつ取り上げると、次の状態、Ｓ（３）と同じになる。
　　　　　　　　３，０，０
　　　　　　　　２，１，０
　　　　　　　　１，１，１
すなわち、Ｍ（ｎ，ｋ）＝Ｓ（ｎーｋ）

（２）　ｋ＞ｎ
――
２		の場合
Ｍ（ｎ，ｋ）＝Ｍ（ｎ−１，ｋ−１）なのでｎ−１をｎ、ｋ−１をｋと置き換えると
２ｋ＞ｎの間繰り返されるので最後には
Ｍ（ｎ，ｋ）＝Ｍ（ｎ、ｎ／２）となり、これは（１）に等しくなる。

故に、（１）（２）をあわせて
Ｍ（ｎ，ｋ）＝Ｓ（ｎ−ｋ）

この式で、ｎを２ｎ，ｋをｎとすると、
Ｓ（ｎ）＝Ｍ（２ｎ，ｎ）が成り立ちます。

ここまでをまとめると

Ｍ（ｎ，１）＝１
Ｍ（ｎ，２）＝ｎ
――
２
《ｋ＞ｎ
――
２		の場合》
　Ｍ（ｎ，ｋ）＝Ｍ（ｎ−１，ｋ−１）

《ｋ≦ｎ
――
２		の場合》
　Ｍ（ｎ，ｋ）＝Ｍ（ｎ−１，ｋ−１）＋Ｍ（ｎーｋ、ｋ）


Ｍ（ｎ，ｎ−１）＝１
Ｍ（ｎ，ｎ）＝１

Ｓ（ｎ）＝Ｍ（２ｎ，ｎ）

【問題７】

　以上の関係を用いて、果物が６個（猿６匹）の場合

　Ｓ（６）
＝Ｍ（１２，６）
＝Ｍ（１１，５）＋Ｍ（６，６）
＝Ｍ（１０，４）＋Ｍ（６，５）＋Ｍ（６，６）
＝Ｍ（９，３）　＋Ｍ（６，４）＋Ｍ（６，５）＋Ｍ（６，６）
＝Ｍ（８，２）　＋Ｍ（６，３）＋Ｍ（６，４）＋Ｍ（６，５）＋Ｍ（６，６）
＝４＋Ｍ（５，２）＋Ｍ（３，３）＋Ｍ（４，２）＋Ｍ（６，５）＋Ｍ（６，６）
＝４＋２＋１＋２＋１＋１
＝１１
【問題８】

　果物が７個（猿７匹）の場合

　Ｓ（７）
＝Ｍ（１４，７）

＝Ｍ（１３，６）＋１
　　∵Ｍ（７，７）＝１

＝Ｍ（１２，５）＋２
　　∵Ｍ（７，６）＝１）

＝Ｍ（１１，４）＋Ｍ（４，２）＋２
　　∵Ｍ（７，５）→Ｍ（４，２）

＝Ｍ（１０，３）＋Ｍ（６，３）＋４　
　　∵Ｍ（４，２）＝２
　　　Ｍ（７，４）→Ｍ（６，３）

＝Ｍ（１０，３）＋Ｍ（５，２）＋Ｍ（３，３）＋４
　　∵Ｍ（６，３）→Ｍ（５，２）＋Ｍ（３，３）

＝Ｍ（９，２）＋Ｍ（６，２）＋Ｍ（４，３）＋７
　　∵Ｍ（５，２）＝２
　　　Ｍ（３，３）＝１
　　　Ｍ（７，３）→Ｍ（６，２）＋Ｍ（４，３）　　　

＝１５
　　∵Ｍ（６，２）＝３、Ｍ（４，３）＝１
　　　Ｍ（９，２）＝４
計算するのが面倒なので、表を作成。

表

この表は、「問題６」でまとめた結果を当てはめれば、機械的にいくらでも増殖出来ます。
証明というより多少はしょっているので説明になってしまいました。
やっとここまできたのですが、リーグ戦にどう応用しようか思案中？

【コメント】

　完璧な解答です。
リーグ戦への適用については、私がどうこういうよりも、黙って解答をお待ちしていようと思います。

◆神奈川県　今村　義彦さんからの解答。

＠問1、2、3は省略する。

＠問4 M(n,2)の一般式は？

ｎが奇数の場合と偶数の場合に分けられる。

1）n = 2m (m ≧ 1)の場合
もっとも偏った分け方は

　(n-1,1,0,0,...,0)

であり、もっとも平均的な（平等的な）分け方は

　(n/2,n/2,0,0,...,0)

である。したがって、分け方の方法は

　M(n,2) = n/2

である。

2) n = 2m + 1 (m ≧ 1)の場合
同様に、(n-1,1,0,0,...,0)と((n+1)/2,(n-1)/2,0,0,...,0)とが分配の上限と下限であるから、

　M(n,2) = (n-1)/2

となる。

答え：

　M(n,2) = n/2 　{ｎが偶数のとき。}
　M(n,2) = (n-1)/2　{ｎが奇数のとき。}

＠問5

　M(n,k) = M(n-1,k-1)　 {k > n/2}
　M(n,k) = M(n-1,k-1) + M(n-k,k)　 {k ≦ n/2} を示せ。

ｋ番目の猿までに分配するということは、ｋ番目の猿が最低1個の果実を持つということである。

1）k > n/2の場合、ｋ番目の猿は最高1個の果実を持つ。なぜならば、

　1（個）* k > n/2≧ 1

であり、かつ、

　2（個）* k < n

である。つまり、2個までは持てない。
このことから、ｋ番目の猿が持つ果実の数は1のみであり、のこりの(n-1)個を(k-1)匹の猿で分配することと等価である。
したがって、

　M(n,k) = M(n-1,k-1) {k > n/2} .................(1)

2)k ≦ n/2の場合、ｋ番目の猿は最低1個の果実を持ち、また、2個以上を持つことも可能である。
例えば、もっとも平均化された場合にはn/k個の果実を持つことができる。
(k ≦ n/2)より、

　2 ≦n/k

が成り立つので、２個の場合は保証されるわけである。
さて、この２個以上の場合には、以下の手順で分配することを考えることにする。つまり、

したがって、

　M(n,k) = M(n-1,k-1) + M(n-k,k) {k ≦ n/2} .....(2)

となる。

＠問6 k≧ n/2のとき、M(n,k) = S(n-k)となることを示しなさい。

M(n,k)を条件{k≧ n/2}に照らし合わせて考えたとき、k番目の猿には最低1個の果実が分配される。
そして、k番目の猿に２個の果実が分配される場合は、ちょうどk=n/2が成立するときのみである。
式(1)より順次第一の引数を減じていくと、

　M(n,k)
= M(n-1,k-1)
= M(n-2,k-2)
= M(2n-2k+1,n-k+1)
= M(2n-2k,n-k) .........................(3)

更に、式(2)を用いて(3)を展開すると、

　M(2n-2k,n-k)
= M(2n-2k-1,n-k-1) + M(n-k,n-k)
= M(2n-2k-2,n-k-2) + M(n-k,n-k-1) + M(n-k,n-k)
= M(n-k,1) + M(n-k,2) +,,,+ M(n-k,n-k)
= S(n-k)

＠問7、8は省略する。

　『果物の分配』へ

　数学の部屋へもどる