事の起こりは、以下のツイート:
長男がいきなり「3歩進んで2歩下がる」と言って、次男が「ってことは、1歩しか進まないよね」と言ったので、「15段の階段で毎日『3歩進んで2歩下がる』を繰り返したら、何日目に15段目に着くか?」と聞いてみた。予想通りに「15段!」と答えたので、実際に階段を上り下りして答えを確かめてもらった。
— 7931 (@wed7931) 2019年5月29日
これ、よくある引っ掛け問題で、実際に試してみると分かるのだけど、15日目ではなく13日目には15段目に到達する。
なぜかというと、1日1段ずつ昇っていった結果、13日目は最初12段目にいて、そこから3段昇ると、2段降りる前に目標の15段目に到達してしまうから。
つまり、最終日は降りる必要がないので、1段ではなく3段進むのがポイント。
これを受けて、『数学ガール』などで有名な結城先生が出した問題が、以下:
毎日『m段上ってn歩下がる』を繰り返したら、x日目にd段目に初めて着いた。xをd,m,nで表せ。文字はすべて正の整数で、m>nとする。#数学の問題 https://t.co/LRJLTFERDH
— 結城浩 (@hyuki) 2019年5月30日
これを「階段昇降問題」と呼ぶことにして、これについて考えてみた。
具体例の分析による解答
まずは上記の具体例()について考えてみる。
前述の通り、最終日は1段ではなく3段進む、というのがポイントで、つまり段をまずは進み、あと1日でゴールとなっているわけだから、これを式で表すと、以下のようになる:
となると、以下のようになりそう:
ただ、は割り切れるとは限らないので、これだとダメそう。
そこで、割り切れないような具体例として、を考えてみる。
この場合、最終日までに段以上進んでいればいいわけだけど、あまりとなって、3日進んだだけだとちょっと足りず、4日でまず段進み、5日目に3段昇ってゴールとなる。
つまり、割り切れなかった場合、さらにあと1日かかることになる。
こういうときに便利なのが天井関数(ceiling function)というもので、と書いた場合、以上の最小の整数を返す。
例えば、だし、となる。
これを使うと、このの例は、以下のように書けることが分かる:
なので、以下のようにすれば大丈夫そう:
でも、実はこれだとまだダメだったり。
注意が必要なのがの部分で、問題文をよく読んでみると、という仮定はどこにも書かれていない。
なので、の場合、マイナスの日数になってしまう可能性がある。
d>mが仮定されてないのがたぶん落とし穴。(うっかりするとマイナスの日数になるはず) https://t.co/WtSF6H4au5
— やまいも (@yappy0625) 2019年5月30日
実際、この見落としをしている回答があったり。
d=1, m=5, n=4とかのとき、マイナスになりませんか…?
— やまいも (@yappy0625) 2019年5月30日
の場合、初日で昇りきってしまうので、一項目は0になるのがポイント。
そこを踏まえると、以下のようになる:
もう少しスマートな解答
結城先生のツイートへの返信を見ていると、大体上記の回答になっているっぽい。
けど、もうちょっとスマートな解答があった。
日目で一番高いところで何段目まで昇るのかを考えてみると、以下のようになる:
これが段以上になっている、最小のが答えなわけだから、以下のように書ける:
ところで、
なので、
よって、
つまり、以下のようになる:
この式の方がさっきの式よりスッキリしてるかな、と思う。
とからそれぞれを引いた値の比率()が重要なんだとパッと分かるし。
プログラムでの確認
結城先生は解答をツイートしてないけど、代わりに答え合わせのプログラムをGistに書いていた:
なので、自分もプログラムを書いて確認してみた:
これを実行してみると、以下のような感じ:
d=7, m=5, n=4 x=3 1日目: 1, 2, 3, 4, 5, 4, 3, 2, 1 2日目: 2, 3, 4, 5, 6, 5, 4, 3, 2 3日目: 3, 4, 5, 6, 7 d=7, m=5, n=2 x=2 1日目: 1, 2, 3, 4, 5, 4, 3 2日目: 4, 5, 6, 7 d=7, m=8, n=6 x=1 1日目: 1, 2, 3, 4, 5, 6, 7 d=7, m=11, n=8 x=1 1日目: 1, 2, 3, 4, 5, 6, 7 d=15, m=3, n=2 x=13 1日目: 1, 2, 3, 2, 1 2日目: 2, 3, 4, 3, 2 3日目: 3, 4, 5, 4, 3 4日目: 4, 5, 6, 5, 4 5日目: 5, 6, 7, 6, 5 6日目: 6, 7, 8, 7, 6 7日目: 7, 8, 9, 8, 7 8日目: 8, 9, 10, 9, 8 9日目: 9, 10, 11, 10, 9 10日目: 10, 11, 12, 11, 10 11日目: 11, 12, 13, 12, 11 12日目: 12, 13, 14, 13, 12 13日目: 13, 14, 15 d=15, m=15, n=14 x=1 1日目: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
うん、大丈夫そうw
今日はここまで!