コンテンツへスキップ

たまには…

  • by

こんにちは。新4年の林です。

先日、学校である演習の時間にこんな問題が出ました。

『一列に並んだn個の荷物があり、前から順に1からnまで番号が振られている。また、それらの重さは相異なり、順に w_1, w_2, …, w_n であるとする。これを軽い順に並び替えたいが、荷物 i と荷物 j ( 1 ≦ i , j ≦ n ) を交換するには w_i + w_j のコストがかかる。並び終わるまでにかかるコストの合計としてあり得る最小の値を求めよ。』

たとえば、荷物の重さが[4, 1, 2]と並んでいたとします。まず4と1を交換し、次に4と2を交換すると軽い順に並び替えられて、そのときのコストは11です。([4, 1, 2] → [1, 4, 2] → [1, 2, 4]) 一方、まず1と2を交換し、次に1と4を交換するという方法だとコストは8で、こちらの方が低コストです。 ([4, 1, 2] → [4, 2, 1] → [1, 2, 4]) このように、交換の仕方によってかかるコストが異なるわけなのですが、そのコストを最小化したいというのがこの問題です。実際、今回の場合はこのコスト8が最小となります。

実はこの問題、答え自体は簡単に見つかるのですが、それが答えだという正当性を証明するのは結構難しいのです。つまり、「こういう交換の仕方が最善なのではないだろうか」ということは直感的にすぐに気づき、実際それが答えとなるのですが、「あらゆる交換の仕方の中でその交換の仕方が最善である」ということを厳密に証明するのが大変なのです。厳密に、です。

詳しい経緯は省略しますが、僕はこの問題にあたり、その次の演習の時間に発表しなければならなくなりました。そこで、その正当性の証明に割と苦労しました。食事中も考え、電車の中でも駅から艇庫まで歩く間も考え、60分エルゴのメニュー中も考えました。最後のは嘘です。そして5日ほど考えたところでやっとその厳密な証明を完成させることができたのです。

ところがですね、発表当日、時間の都合で正当性の証明の部分は発表することができなかったのです。先生自身も厳密な正当性までは求めていなかったようでした。結局、答えについてだけ解説したあと、正当性の厳密な証明は長くなるので省きます、と残して僕は発表を終えました。(まあ、最初から分かっていたことなんですがね!そもそも厳密な証明を発表すると少なくとも40分はかかる計算だったので。)

この問題に限りませんが、数学的な証明を考える過程にはストーリーがあると僕は思うのです。具体的に実験してみたり、同値な表現を見つけたり、必要な補題を示したり、「ここさえ示すことができたら証明が完結するのに!」というような部分の証明に苦労したり…。無機的な推論規則のように見える記述でも、こういう試行錯誤の末に完成したものは多いと思います。そして、ほとんどの場合それは多くの時間を必要とすると思います。何時間、何日間、何ヶ月、あるいは何年と考える場合もあるでしょう。フェルマーの最終定理を証明した数学者ワイルズは、証明のプロセスについて次のような言葉を残しています。

【ある部屋に入るが、そこで何か月も、ときには数年も家具にぶつかって足踏みしていなければならない。ゆっくりとだが、全部の家具がどこにあるかがわかってくる。そして明りのスイッチを探す。明りをつけると部屋全体が照らし出される。それから次の部屋へ進んで、同じ手順を繰り返すんだ。(アンドリュー・ワイルズ)】

頭の片隅に問題をストックしておき、長い時間かけて考え諦めずに突き詰めることで、ある日突然ひらめいたり良いアイディアが浮かんだりすることは、きっと数学だけに限った話ではないでしょう。それは漕ぎに関して言えることでもあり、そしてボート以外のことに関しても言えることだと思います。

長々と書きましたが結局何が言いたかったのかというと、あらゆる問題解決には時間をかけて考え抜くことが大切だろうということと、あと、誰か上の問題に対する僕の証明の40分の発表を聞いてください、ということです。

\ 最新情報をチェック /

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

PAGE TOP