原神wiki
雑談/ファルザン / 838
2030
コメント
views
7
フォロー
簡単な例として1段、2段、3段を試したらすぐに1手、3手、7手ってのは分かるから、その流れで127手はいけた。
実際に手を動かして気付いたら100年経ってたけど、そうやればよかったんだ
ちゃんと考えるとこんな感じ（以下白字）：n+1段のハノイの塔を動かすには①上の1～n段目までを完全にどかして別の列に積み上げる。②n+1段目を①とは別の列の一番下に移動させる。③最初にどかした1～n段をn+1段目の上にのせる。の3stepを踏めばOK。いまn段のハノイの塔を別の列へ移すのに必要な手数をA[n]とすると、①は定義からA[n]手、②は1手、③はA[n]手（※n+1段目は1～n段までのすべてを乗せられる段なので①のときと同じ手順を踏める）なので、A[n+1]=2A[n]+1が成立する（初項は明らかにA[1]=1）。あとは素直に漸化式を解くなり数学的帰納法を使うなりすれば一般解A[n]=2^n - 1にたどり着けるぞ（たかだか第7項の具体値が分かればいいのでA[1],A[2],…って順に計算してもOK）。"n+1段目を追加するとn段目までのセットを待避&乗せるで合計2回移動させないといけないから手数が倍くらいになる"ってところに気づけたら、細かく計算しなくても手数が2^nオーダーって見積れますね。
2の累乗はありとあらゆるロジックに現れる整った数字だからね。それはともかくあそこの選択肢は他も３つも強い規則性を持っていたり、煩悩の数とも捉えられたり色々と面白い、明らかに完全無作為ではない。