逆から考えると簡単になる問題とは？

問題は普通、スタートからゴールに向かって考えます。けれども、ゴールから逆向きにたどった方が、ずっと簡単になる問題があります。この記事では、逆から考えると見通しが良くなる3つの問題を取り上げ、どんなときに「逆」が効くのかを考えます。

石取りゲーム：負けの状態から逆算する

21個の石の山があります。2人が交互に、1個から3個までの石を取ります。最後の石を取った人が勝ちです。先手と後手、どちらが必勝でしょうか。

先手の最初の一手を考え始めると、場合が増えて困ります。そこで、ゴールの近くから逆にたどります。残りが1個、2個、3個のとき、自分の番なら全部取って勝ちです。では、残りが4個のときはどうでしょう。1個、2個、3個のどれを取っても、相手の番で残りが3個、2個、1個になり、相手が全部取って勝ちます。つまり、残り4個で自分の番になった人は負けです。

残りが5個、6個、7個なら、1個から3個を取って、相手の番を「残り4個」にできるので勝ちです。残り8個は、どう取っても相手に5個、6個、7個を渡すので、負けです。このように、自分の番で負けになる残り個数は、4の倍数だと分かります。

21個は4の倍数ではありません。先手は最初に1個を取って、残りを20個、つまり4の倍数にします。その後は、相手が $x$ 個取ったら、自分は $4-x$ 個を取ります。相手の番はいつも4の倍数になり、最後は先手が取って勝ちます。先手必勝です。

計算の逆算：操作を逆にたどる

ある数に3を足して、2倍し、4を引いたら20になりました。元の数はいくつでしょうか。

「ある数 $x$」と置いて式を立てることもできますが、操作を逆にたどる方法もあります。最後の「4を引く」を逆にして、$20+4=24$。次に「2倍」を逆にして、$24\div2=12$。最後に「3を足す」を逆にして、$12-3=9$。元の数は9です。

$$(9+3)\times2-4=20$$

この式は、答えを元に戻して計算し、確かに20になることを確認するものです。逆算では、最後の操作から順番に、それぞれの逆の操作をしていきます。

睡蓮の問題：増え方を逆に見る

池に睡蓮が生えています。睡蓮は毎日、面積がちょうど2倍になり、30日目に池全体を覆い尽くしました。池の半分が覆われたのは何日目でしょうか。

最初から数えると難しそうですが、逆から見ると簡単です。2倍で全体になるのですから、全体の前の日は「半分」です。つまり、29日目に池の半分が覆われていました。「増える」を「戻す」に変えると、一歩で答えが出ます。

逆から考えるとよいのは、どんなとき？

この3つの問題には共通点があります。

• ゴールの状態が、はっきり分かっている。
• スタートから進むと、場合が増えすぎる。
• 1つ前の状態が、一通りに決まる（または簡単に分かる）。

逆にたどるときは、「ゴールの1つ前はどうなっているか」を繰り返し問います。石取りゲームのように、「勝ちの状態」「負けの状態」を、ゴールから順に決めていく方法は、より複雑なゲームを調べるときにも使われる考え方です。

まとめ

逆から考える方法は、ゴールがはっきりしていて、順に進むと場合が増える問題に有効です。石取りゲームでは負けの状態を、計算では操作の逆を、睡蓮では増え方の逆を、それぞれたどりました。問題が行き詰まったら、「ゴールの1つ前はどうなっている？」と、問いの向きを変えてみてください。