いものやま。

雑多な知識の寄せ集め

階段昇降問題を解いてみた。

f:id:yamaimo0625:20190601082323j:plain

事の起こりは、以下のツイート:

これ、よくある引っ掛け問題で、実際に試してみると分かるのだけど、15日目ではなく13日目には15段目に到達する。
なぜかというと、1日1段ずつ昇っていった結果、13日目は最初12段目にいて、そこから3段昇ると、2段降りる前に目標の15段目に到達してしまうから。
つまり、最終日は降りる必要がないので、1段ではなく3段進むのがポイント。

これを受けて、『数学ガール』などで有名な結城先生が出した問題が、以下:

これを「階段昇降問題」と呼ぶことにして、これについて考えてみた。

具体例の分析による解答

まずは上記の具体例( d=15, m=3, n=2)について考えてみる。

前述の通り、最終日は1段ではなく3段進む、というのがポイントで、つまり 15-3=12段をまずは進み、あと1日でゴールとなっているわけだから、これを式で表すと、以下のようになる:

 (15 - 3) \div (3 - 2) + 1 = 12 \div 1 + 1 = 13

となると、以下のようになりそう:

 \displaystyle
x = \frac{d - m}{m - n} + 1

ただ、 \frac{d-m}{m-n}は割り切れるとは限らないので、これだとダメそう。

そこで、割り切れないような具体例として、 d=15, m=4, n=1を考えてみる。

この場合、最終日までに 15-4=11段以上進んでいればいいわけだけど、 11 \div (4 - 1) = 3あまり 2となって、3日進んだだけだとちょっと足りず、4日でまず (4 - 1) \times 4 = 12段進み、5日目に3段昇ってゴールとなる。
つまり、割り切れなかった場合、さらにあと1日かかることになる。

こういうときに便利なのが天井関数(ceiling function)というもので、 \lceil x \rceilと書いた場合、 x以上の最小の整数を返す。
例えば、 \lceil 3 \rceil = 3だし、 \lceil 3.66\ldots \rceil = 4となる。

これを使うと、この d=15, m=4, n=1の例は、以下のように書けることが分かる:

 \begin{align}
\lceil (15 - 4) \div (4 - 1) \rceil + 1 &= \lceil 11 \div 3 \rceil + 1 \\
&= \lceil 3.66 \ldots \rceil + 1 \\
&= 4 + 1 \\
&= 5
\end{align}

なので、以下のようにすれば大丈夫そう:

 \displaystyle
x = \left\lceil \frac{d - m}{m - n} \right\rceil + 1

でも、実はこれだとまだダメだったり。

注意が必要なのが d - mの部分で、問題文をよく読んでみると、 d \ge mという仮定はどこにも書かれていない。
なので、 d \lt mの場合、マイナスの日数になってしまう可能性がある。

実際、この見落としをしている回答があったり。

 d \lt mの場合、初日で昇りきってしまうので、一項目は0になるのがポイント。
そこを踏まえると、以下のようになる:

 \displaystyle
x = \mathrm{max} \left\{ 0, \left\lceil \frac{d - m}{m - n} \right\rceil \right\} + 1

もう少しスマートな解答

結城先生のツイートへの返信を見ていると、大体上記の回答になっているっぽい。

けど、もうちょっとスマートな解答があった。

 t日目で一番高いところで何段目まで昇るのかを考えてみると、以下のようになる:

 (m - n)(t - 1) + m

これが d段以上になっている、最小の t \in \mathbb{Z}_+が答えなわけだから、以下のように書ける:


x = \mathrm{min} \left\{ t \in \mathbb{Z}_+ \, | \, (m - n)(t - 1) + m \ge d \right\}

ところで、

\begin{align}
(m - n)(t - 1) + m &= (m - n)t - (m - n) + m \\
&= (m - n)t - m + n + m \\
&= (m - n)t + n
\end{align}

なので、

 \begin{align}
(m - n)(t - 1) + m \ge d &\Longleftrightarrow (m - n)t + n \ge d \\
&\Longleftrightarrow t \ge \frac{d - n}{m - n} \quad (\because m > n) \\
&\Longleftrightarrow t \ge \left\lceil \frac{d - n}{m - n} \right\rceil \quad (\because t \in \mathbb{Z}_+)
\end{align}

よって、

 \begin{align}
x &= \mathrm{min} \left\{ t \in \mathbb{Z}_+ \, | \, (m - n)(t - 1) + m \ge d \right\} \\
&= \mathrm{min} \left\{ t \in \mathbb{Z}_+ \, \left| \, t \ge \left\lceil \frac{d - n}{m - n} \right\rceil \right. \right\} \\
&= \mathrm{max} \left\{ 1, \left\lceil \frac{d - n}{m - n} \right\rceil \right\} \quad \left(\because \left\lceil \frac{d - n}{m - n} \right\rceil \in \mathbb{Z} \right)
\end{align}

つまり、以下のようになる:

 \displaystyle
x = \mathrm{max} \left\{ 1, \left\lceil \frac{d - n}{m - n} \right\rceil \right\}

この式の方がさっきの式よりスッキリしてるかな、と思う。
 d mからそれぞれ nを引いた値の比率( \frac{d - n}{m - n})が重要なんだとパッと分かるし。

プログラムでの確認

結城先生は解答をツイートしてないけど、代わりに答え合わせのプログラムを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

今日はここまで!