[答1001] 球の分裂

[答1001] 球の分裂


　初めに１と書かれた球があって、１分後はそのままですが、２以上の自然数ｎについて、

　ちょうどｎ分後に 全ての球はその球に書かれた数以上ｎ以下の自然数が書かれた球に分裂します。

　( 図は １分後～５分後の状態を それぞれ 紺色，橙色，緑色，水色，赤色で表しています )

　n≧k において ｎ分後の分裂直後にｋと書かれた球の個数を f(n，k) として、f(10，6)＝？

　また、 f(x，y)＝f(10，6) を満たす(10，6)以外の自然数の組(x，y)＝？


[解答1]

　n＜k のとき f(n，k)＝0 ，f(n，1)＝1 ，f(n，k)＝f(n－1，k)＋f(n，k－1) であり、

　上のように表を作れば、f(10，6)＝1001 、

　f(x，y)＝f(10，6) を満たす(10，6)以外の自然数の組は (x，y)＝(9，7)，(1002，2) です。


[解答2]

　たとえば、10分後に６である球の１分後からの番号は、

　１→２→２→３→３→３→３→５→６→６　のように、最初が１で最後が６になります。

　数を□，増える数を ⇒ で表せば　□⇒□□⇒□□□□⇒⇒□⇒□□　になり、

　その並べ方は 両端を除いて □８個，⇒５個 の並べ方と等しく、13!/(8!･5!)＝1287 通りです。

　ただし、ｎ分後の数は(n＋1)以上にならないので、次のような並びはありえません。

　１→４→４→４→５→５→５→５→５→６ ，１→２→４→５→５→５→５→５→６→６

　□，⇒ で表せば　□⇒⇒⇒□□□⇒□□⇒□□□□ ，□⇒□⇒⇒□⇒□□□□□⇒□□　です。

　この場合、途中で □より⇒の方が多くなる箇所ができます。

　□より⇒の方が１個多くなる所で区切り、区切りの後を □，⇒を逆にして上下に並べれば、

　□⇒⇒|⇒□□□⇒□□⇒□□□□ ，□⇒□⇒⇒|□⇒□□□□□⇒□□
　□⇒⇒|□⇒⇒⇒□⇒⇒□⇒⇒⇒⇒ ，□⇒□⇒⇒|⇒□⇒⇒⇒⇒⇒□⇒⇒　です。

　その並べ方は 両端を除いて □３個，⇒10個 の並べ方と等しく、13!/(3!･10!)＝286 通りです。

　よって、f(10，6)＝1287－286＝1001 です。

　このようにして、k≧3 において、f(n，k) を求めるときは、

　□(n－2)個，⇒(k－1)個 の 並べ方から □(k－3)個，⇒ｎ個 の 並べ方を減じて、

　f(n，k)＝(n＋k－3)!/｛(n－2)!･(k－1)!｝－(n＋k－3)!/｛(k－3)!･n!｝

　 ＝(n＋k－3)!･n(n－1)/｛n!･(k－1)!｝－(n＋k－3)!･(k－1)(k－2)/｛(k－1)!･n!｝

　 ＝(n＋k－3)!･｛n(n－1)－(k－1)(k－2)｝/｛n!･(k－1)!｝

　 ＝(n＋k－3)!･(n＋k－2)(n－k＋1)/｛n!･(k－1)!｝＝(n＋k－2)!･(n－k＋1)/｛n!･(k－1)!｝ 、

　また、明らかに f(n，1)＝1 ，f(n，2)＝n－1 ですが、k＝1，2 のときも

　f(n，k)＝(n＋k－2)!･(n－k＋1)/｛n!･(k－1)!｝ が成り立ちます。

　x≧2，y＜x のとき f(x，y) は xについても yについても単調増加になります。

　f(10，6)＝f(9，y) とすれば y＝7，8，9 しか考えられませんが、f(9，7)＝1001 で y＝7 です。

　f(10，6)＝f(9，7)＝f(8，y) とすれば y＝8 しか考えられませんが、f(8，8)＝429 で不適です。

　f(x，y)＝f(10，6)，x≧11 とすれば、y≦5 です。

　f(x，1)＝1 より f(x，1)＝1001 を満たすｘはありません。

　f(x，2)＝1001 のとき x－1＝1001 、x＝1002 です。

　f(45，3)＝989，f(46，3)＝1034 より f(x，3)＝1001 を満たすｘはありません。

　f(18，4)＝950，f(19，4)＝1120 より f(x，4)＝1001 を満たすｘはありません。

　f(12，5)＝910，f(13，5)＝1260 より f(x，5)＝1001 を満たすｘはありません。

　よって、f(x，y)＝f(10，6) を満たす(10，6)以外の自然数の組は (x，y)＝(9，7)，(1002，2) です。

.