[答1001] 球の分裂
[答1001] 球の分裂
初めに1と書かれた球があって、1分後はそのままですが、2以上の自然数nについて、
ちょうどn分後に 全ての球はその球に書かれた数以上n以下の自然数が書かれた球に分裂します。
( 図は 1分後~5分後の状態を それぞれ 紺色,橙色,緑色,水色,赤色で表しています )
n≧k において 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分後に6である球の1分後からの番号は、
1→2→2→3→3→3→3→5→6→6 のように、最初が1で最後が6になります。
数を□,増える数を ⇒ で表せば □⇒□□⇒□□□□⇒⇒□⇒□□ になり、
その並べ方は 両端を除いて □8個,⇒5個 の並べ方と等しく、13!/(8!・5!)=1287 通りです。
ただし、n分後の数は(n+1)以上にならないので、次のような並びはありえません。
1→4→4→4→5→5→5→5→5→6 ,1→2→4→5→5→5→5→5→6→6
□,⇒ で表せば □⇒⇒⇒□□□⇒□□⇒□□□□ ,□⇒□⇒⇒□⇒□□□□□⇒□□ です。
この場合、途中で □より⇒の方が多くなる箇所ができます。
□より⇒の方が1個多くなる所で区切り、区切りの後を □,⇒を逆にして上下に並べれば、
□⇒⇒|⇒□□□⇒□□⇒□□□□ ,□⇒□⇒⇒|□⇒□□□□□⇒□□
□⇒⇒|□⇒⇒⇒□⇒⇒□⇒⇒⇒⇒ ,□⇒□⇒⇒|⇒□⇒⇒⇒⇒⇒□⇒⇒ です。
その並べ方は 両端を除いて □3個,⇒10個 の並べ方と等しく、13!/(3!・10!)=286 通りです。
よって、f(10,6)=1287-286=1001 です。
このようにして、k≧3 において、f(n,k) を求めるときは、
□(n-2)個,⇒(k-1)個 の 並べ方から □(k-3)個,⇒n個 の 並べ方を減じて、
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 を満たすxはありません。
f(x,2)=1001 のとき x-1=1001 、x=1002 です。
f(45,3)=989,f(46,3)=1034 より f(x,3)=1001 を満たすxはありません。
f(18,4)=950,f(19,4)=1120 より f(x,4)=1001 を満たすxはありません。
f(12,5)=910,f(13,5)=1260 より f(x,5)=1001 を満たすxはありません。
よって、f(x,y)=f(10,6) を満たす(10,6)以外の自然数の組は (x,y)=(9,7),(1002,2) です。
.