じゃんけんと階乗の問題

K.Ooi @k_ooi

昨日，@hyukiさんのクイズに数学ガールのツイートで乗ってしまって，その後出歩きながら頭から離れなかったので，今から連続ツイートします。16個の予定。

K.Ooi @k_ooi

昨日の@hyukiさんのじゃんけんクイズ，@igarisさんのn人拡張版(1)。僕「ところでユーリ，n人でじゃんけんする時，手の出方は全部で何通り？」ユーリ「誰でもグー・チョキ・パーのどれかを出すんだから，3×3×…　3^n通りだにゃ。」僕「ご名答。」

K.Ooi @k_ooi

.@hyuki @igaris (2) 「じゃあ何種類の手が出ているかで場合分けしてみよう。みんなが同じ手だったら1種類，勝負がついたら2種類，グー・チョキ・パーが全部出てあいこになったら3種類。」「ほほう」

K.Ooi @k_ooi

.@hyuki @igaris (3) 「n人でじゃんけんして，手が1種類の場合の数をa(n)，2種類をb(n)，3種類をc(n)とする。」「ふむふむ」「1種類というのは全員がグー，全員がチョキ，全員がパーの3つの場合しかないからa(n)=3」「a(n)はnが何でも3なのかー」

K.Ooi @k_ooi

.@hyuki @igaris (4) 「ところで，ユーリを含めてn人でじゃんけんをしたとして，ユーリ以外のn-1人の手が1種類しかない時，ユーリの手の出し方は1人勝ちになるか，あいこになるか，1人負けになるかのいずれかだ。」「後出しするみたい。」

K.Ooi @k_ooi

.@hyuki @igaris (5) 「ユーリ以外のn-1人の手が2種類の時は，ユーリの手の出し方は別の手を出してあいこにするか，勝ちに加わるか，負けに加わるか。」「後出しして負けたらバカでしょ。」「3種類の時は？」「もうなに出したってあいこは変わらないよ」

K.Ooi @k_ooi

.@hyuki @igaris (6) 「今のを式に表すと，ユーリが加わってn人の時に勝負がつく手の出方は b(n)=2*a(n-1)+2*b(n-1)。3種類の手が出てあいこになるのは c(n)=1*b(n-1)+3*c(n-1)。」「1種類のはa(n)=a(n-1)だにゃ。」

K.Ooi @k_ooi

.@hyuki @igaris (7) 「そうだ，今の3つの式を全部足してみて？」「式を足すって…　右辺どうし，左辺どうし足しても等号が成り立つってことか。ええとa(n)+b(n)+c(n)=3*{a(n-1)+b(n-1)+c(n-1)}。まとめるときれいな形になるね。」

K.Ooi @k_ooi

.@hyuki @igaris (8) 「a(n)+b(n)+c(n)は全部の手の出方だからね。最初にやったとおり3^nになる。2人でやると全部で9通り。あいこはa(2)=3通り，勝負がつくのはb(2)=6通り。3種類手が出ることはないからc(2)=0だね。」

K.Ooi @k_ooi

.@hyuki @igaris (9) ユーリ「a(3)=3，b(3)=2*a(2)+2*b(2) =2*3+2*6 =18，c(3)=b(2)+0 =6。3人であいこになるのは9通りかあ…」僕「でね，あいこになる場合を考えるとb(n)=3^(n)-a(n)-c(n)を使って…」

K.Ooi @k_ooi

.@hyuki @igaris (10)「お兄ちゃん，勝負がつく方で考えた方がわかりやすくない？ b(n)=2*b(n-1)+6だよ。」「うん。そこでB(n)=b(n)+6とおく。」「何その天下りは？」「いいからさっきの式の両辺に6を足してごらん。」

K.Ooi @k_ooi

.@hyuki @igaris (11)「b(n)+6=2*b(n-1)+12」「右辺を2でくくって。」「あ，B(n)=2*B(n-1)ってことか。」「B(n)=2^(n-2)*B(2)だね」「B(2)=b(2)+6=12だからB(n)=2^(n-2)*3*2*2」

K.Ooi @k_ooi

.@hyuki @igaris (12)「b(n)=3*2^n-6ってことだね。」「偉いなあユーリ。今度はc(n)=2*c(n-1)+3^(n-1)-3に取り組むよ。」「えー，だってc(n)=3^n-a(n)-b(n)だからc(n)=3^n-3*2^n+3でいいじゃない。」

K.Ooi @k_ooi

.@hyuki @igaris (13)「そうなんだけど，さっき天下りっていわれたから。c(n)がc(n-1)の定数倍を含む式で表される時，等比数列に変形することを考えよう。今回の場合，c(n)+f(n)+α=2*{c(n-1)+f(n-1)+α}としたい。」

K.Ooi @k_ooi

.@hyuki @igaris (14)「2*f(n-1)-f(n)=3^(n-1)，2*α-α=-3になるので，α=-3はすぐ出てくる。f(n)はf(n)=β*3^nとおくと2*β*3^(n-1)-β*3^n=3^(n-1)だから3^n=3*3^(n-1)を使ってβ=-1。」

K.Ooi @k_ooi

.@hyuki @igaris (15)「両辺に-3^n-3を足して，c(n)-3^n-3=2*c(n-1)+3^(n-1)-3-3*3^(n-1)-3=2*{c(n-1)-3^(n-1)-3}だ。C(n)=2C(n-1)になった。C(2)=-12で，C(n)=-3*2^n。」

K.Ooi @k_ooi

.@hyuki @igaris (16)「c(n)=3^n-3*2^n+3となる。」「ねえねえ，n=10の時，全部で59049通りのうち勝負がつくのは3066通りしかないよ。10人でじゃんけんしたら，平均18～19回ぐらいあいこが続いてやっと勝負が決まるということか……」

たばすこ @brv00

続きを書いてみました。 RT @k_ooi: .@hyuki @igaris (16)「c(n)=3^n-3*2^n+3となる。」「ねえねえ，n=10の時，全部で59049通りのうち勝負がつくのは3066通りしかないよ。10人でじゃんけんしたら，平均18～19回ぐらいあい ...

たばすこ @brv00

(2-1) 「ねえ、お兄ちゃん」「ん？」「3種類あるから3^n通りなんだよね」「そうだね」「2種類だと2^n通りだよね」「確かに」 @k_ooi @hyuki @igaris

たばすこ @brv00

(2-2) 「『2種類』の手の出方は『グーとチョキ』、『チョキとパー』、『パーとグー』の3通りだよね」「…」「場に2種類しかないと勝負がつくよね」「ははあ、何が言いたいかわかったよユーリ。でもそれだとね…」「わかってる！」 @k_ooi @hyuki @igaris

たばすこ @brv00

(2-3) 「わかってる。2^nじゃ多すぎなんだ。場にグーとパーしかない『ばーいのかず』は2^n通り。でもそれだと勝負がついてるとは限らない、グーしかない場合やパーしかない場合を含んじゃってる。その2つを引かなきゃいけない」 @k_ooi @hyuki @igaris

たばすこ @brv00

(2-4) 「つまりこうなる/// 2^n-2 ///3通りあるからこれを3倍する/// 3(2^n-2) /// これでもb(n)は出てくる、よね？」 @k_ooi @hyuki @igaris

たばすこ @brv00

(2-5) 「うん、それでも出るね。あいこになるのは/// 3^n - b(n) = 3^n - 3(2^n - 2) = 3^n - 3*2n + 6 /// a(n)=3を引けばc(n)はさっきと同じになる」「ねえお兄ちゃん」「？」 @k_ooi @hyuki @igaris

たばすこ @brv00

(2-6) 「b(1)=0だね」「そうだね」「1人だと勝負はつかないんだね」 @k_ooi @hyuki @igaris

たばすこ @brv00

「勝負」＝「ミルカさん争奪戦」みたいな百合展開を書く度胸はなかった。