FC2ブログ

Welcome to my blog

[答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) です。

.

スポンサーサイト



Comments 16

There are no comments yet.
ひとりしずか  
No title

やさしい落ち着いた色・・・

ニリンソウ  
No title

この色のクジャクサボテンも初めてです
キツクなくていい色ですね。

ナイス

こっこちゃん  
No title

クジャクサボテンのピンク珍しいですね

優しさ頂きました

今日一日楽しく過ごします ナイス☆

uch*n*an  
No title

この問題は,答えを求めるだけならば,[解答1]のようにすればよく容易ですが,
その意味まで考えると,[解答2]のようにカタラン数もどきと分かり,
なかなか味わい深い問題でした。さすが息子さん,といったところでしょうか。

これでしばらくお休みですね。とはいっても再開は早そうですね。
私は[16]が初参加ですが,フィボナッチが出てくるのが面白くての参加でした。
その後,最初は気が向いたらの参加でしたが,いつの間にか毎回参加になりました。
知らないことを教えて頂き一杯勉強させて頂き,ありがとうございます。
再開後はどうなるか分かりませんが,マイペースで参加できたらいいな,
と思っています。

ゆうこ つれづれ日記  
No title

こんにちは~~
クジャクサボテンですね。
薄いピンクのクジャクサボテンは
初めて見ました。
育ててみたいわ~~~~
ナイス☆

スモークマン  
No title

グーテンアーベント ^^
一般高が求め目方の発想にはついていけてません…^^;
漸化式にも気付いてませんでしたが...法則に沿って書き出してみました...最後の1個はなさそうに思ったら...そっか2番目にでて来るじゃんってなアバウトなことで…Orz
面白い問題を考えられたものですね☆
1001問目をプレゼントされた限りはそこに向かっての創作のモチベーションとなったことでしょう? ^^
第2ステージの千夜一夜問を期待していまっす♪

さっちゃんこ  
No title

こんばんは
クジャクサボテンの淡いピンク色は未だ見た事がありません
優しい色合いですネ


ナイス☆彡

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!をありがとうございます。
白に近い色の花は優しく感じますね。
それに、花が大きいと落ち着いた雰囲気があります。

ヤドカリ  
No title

ニリンソウさん、早速のコメントをありがとうございます。
ピンクが中間色であるだけに、色としては優しいですね。
ピンクをあまり見かけない理由は分かりませんが。

ヤドカリ  
No title

こっこちゃんさん、早速のコメントとナイス!をありがとうございます。
白や赤のクジャクサボテンは割に見かけますが、
中間色のピンクはあまり見かけませんね。

ヤドカリ  
No title

uch*n*anさん、早速のコメントをありがとうございます。
長男がわざわざ「1001番の問題」と言って提供してくれた問題なので、
1000番からも続けなければならなくなったように思いました。
ところで、
調べましたところ、貴殿は[27]からは毎回参加で毎回正解です。
[1026]まで続ければ、連続1000問正解してくれることでしょう。
[1026]まで続けることを私の当面の目標としましょう。

ヤドカリ  
No title

ゆうこさん、コメントとナイス!をありがとうございます。
ゆうこさんは白い花がお好きですね。
薄いピンクは白にほんのり赤みがさしたようで、
これの魅力的な色だと思います。

ヤドカリ  
No title

スモークマンさん、コメントとナイス!をありがとうございます。
uch*n*anさんが書いてくれているように、
カタラン数のことを知っていれば、この発想ができます。
スモークマンさんは、第1問からの参加者、
これからもよろしくお願いします。

ヤドカリ  
No title

さっちゃんこさん、コメントとナイス!をありがとうございます。
確かにピンクのクジャクサボテンは珍しいですね。
さっちゃんこさんも見られる機会があればいいですね。

アキチャン  
No title

こんばんわ。
赤色はよくありますが、ピンク色は珍しいですね(o^-^o)
優しいですね。

ヤドカリ  
No title

アキチャンさん、コメントとナイス!をありがとうございます。
あまり見られないピンクですが、綺麗に咲いているときに撮れました。
クジャクサボテンは花が大きく豪華な感じがします。