来年になったら本気だす


by lagrange4
カレンダー
S M T W T F S
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30

数学botからの挑戦状(被害妄想)

数学問題bot @mathematics_bot
というツイッターアカウントがありまして、
1時間に1回、もしくはリプライを飛ばすと出題をする、そうです。

さっき知ったところでして、まわってきたのがこの問題( ・ω・)っ

3000枚のカードに1から3000まで番号が書かれており、1を一番上として番号順に積み重なっている。『一番上のカードを一番下に挿入し、次に一番上になったカードを捨てる』という作業を繰り返したとき、最後に残るカードの数字は何か。(コマ大数学科第6回ヨセフスの問題・改) #数学

と、それなりにとっつきやすそうな問題なので解いてみようかなあと。
よろしければおつきあいくださいませ(´▽`)

間違ってたらこっそり修正します|ン、)



1.力技で解いてみる

まず1回力技で考えてみましょう
作業としては2枚1セットで考えるとよさそう

「1、2」→1を一番下に、2を捨てる

とありますが
それだと循環して切れ目がわかりづらいので、別の山を作る、と考えて操作することにしましょう

1、2、3、…、2998、2999、3000 の 3000枚を1作業繰り返すと

1、3、5、…、2995、2997、2999 の 1500枚の山ができることになります

とりあえずここまでは大丈夫でしょうか?
続いてもう一操作

1、5、9、13、…2989、2993、2997 の 750枚
1、9、17、25、33、41、…、[Last]の375枚の山ができます

最初はちゃんと後ろの数字やろうとしたんだけどネタばらししてしまうと実際は必要ないので割愛しちゃいましょう(ゝω・)
最後の番号を[Last]としましょう(この数字は毎回違うと思って良いです

さてここからが問題
187回操作が終わった時にできるもの
元の山:[Last]の1枚
操作後の山:1、17、33、49…の187枚

この次の動作は「[Last]、1」のペアになるので、[Last]が操作後の山の1番下に入り、1の札は捨てられます
なので枚数は変わらず187枚です

仕切りなおしてこの状態から考えましょう

手元にあるのは、17、33、49、65、81…、[Last]の187枚

奇数枚なのでさっきと同じような操作をすると、17、49、81、…の93枚と[Last]1枚ができて、
[Last]、17のペアより49、81、…[Last]の93枚

同様に49、113、…となるけど[Last]と49のペアができるので、
49からスタートの46枚

そろそろ疲れてきましたね(;´∀`)

2.数列を考える

お気づきの方も多いと思いますが、上記の数字の並びは全て等差数列になっています

上記をまとめてみると以下のような数列になっているのがわかると思います(っ・ω・)っ

3000枚:n + 1 (n≧0)
1500枚:2n + 1
750枚:4n + 1
375枚:8n + 1
187枚:16n + 1 (n≧1) → 16n + 17 (n≧0)
93枚:32n + 17 (n≧1) → 32n + 49 (n≧0)
46枚:64n + 49 (n≧1) → 64n + 113 (n≧0)

1山操作する毎に、二項間の差が2倍になっていきます
直感でわかる人はわかると思いますが、最初は公差1のペアから1枚捨てるので偶数の数字が捨てられ、
できた山は公差2に。次の操作は公差2のペアなので1枚捨てていくと次の差は2 + 2 = 4、
次の差は4+4、8+8と倍々になっていきます

奇数枚の山を操作すると、n=0の番号が捨てられるのでn=1からスタートすることになるんですが、
次の山の操作を考えるとn=0からの数列にした方が都合がいいので変形しています

という操作をずーっと続けていくと

46枚:64n + 49 (n≧1) → 64n + 113 (n≧0)
23枚:128n + 113 (n≧0)
11枚:256n + 113 (n≧1) → 256n + 369 (n≧0)
5枚:512n + 369 (n≧1) → 512n + 881 (n≧0)
2枚:1024n + 881 (n≧1) → 1024n + 1905 (n≧0)
1枚:2048n + 1905 (n≧0)

というので答え

1905

そんな感じになると思いますがいかがでしょう|ω・)

ちょっと数字だらけでややこしいとは思いますがご容赦くださいませ
もうちょっと見やすくできたらなあとは思うので考えてみます(-ω-)


おまけ

3.もうちょっと式を一般化する

もうちょっとどうにかなりそうなんですが、奇数枚の扱いを別アプローチにしないと式が煩雑になりそうなのがなんとも…
もう少し考えてみます_(:3 」∠)_


指摘・質問なんでも歓迎いたしますのでよろしく
それではさよなら、さよならヾ(*´∀`)ノシ
[PR]
by lagrange4 | 2013-06-13 17:53 | のーみそこねこね