とけない もんだいも あるの?

ばあいの かずが ばくはつ

一人が いくつもの まちを
ぜんぶ 一かいずつ まわります。
いちばん みじかい みちを さがしたい。
まちが 三つなら
まわる じゅんばんは わずかです。
でも まちを 一つずつ ふやすと、
しらべる じゅんばんの かずが
あっという まに ものすごく なります。
下の ボタンで まちを ふやしてみて。

まちを ふやすと まわる じゅんばんの かずが ばくはつします。(まち +1 → ばあいの かず かけざん)

まちが ふえる たびに
じゅんばんの かずが かけざんで ふくらみます。
これが ビッグオーで 見た
「ばくはつする そだち」です。
まちが 十いくつ あるだけで
じゅんばんが おおすぎて、
一つずつ ぜんぶ しらべる みちは
すぐに ふさがります。

とくのは むずかしいが かくにんは かんたん

でも おもしろい ところが あります。
こたえを 見つけるのは むずかしくても、
だれかが こたえを もってくれば
それが あっているかの かくにんは すぐです。
スドクを おもいだして。
ますを ぜんぶ うめるのは あたまが いたい。
でも うまった ばんを 見て
ルールに あっているか しらべるのは
目で さっと 見れば おわりです。

こたえ こうほを おすと かくにんは すぐです。(さがすのは むずかしい · けんさは ひと目)

さがすのは むずかしく
かくにんは かんたん。
この 二つが べつべつなのが
こういう もんだいの とくちょうです。
セールスマンの みちも おなじ。
いちばん みじかいのを さがすのは むずかしいが、
あたえられた みちを はかって
「この みちの ぜんたいの きょりは いくつ」と だすのは
ただの たしざん 何かいかで すみます。

はやい とき方は あるの?

ここで 大きな しつもんが でます。
「かくにんが はやい もんだいは
とくのも はやい?」
もしかすると わたしたちが まだ
かしこい ほうほうを 見つけていない だけかも。
それとも、ほんとうに
はやい とき方が ない のかも。
下で 二つの たちばを おしてみて。

二つの たちばを おして。(かくにん はやい = とくのも はやい? · まだ だれも 知らない)

おどろくことに この しつもんは
まだ だれも こたえを 知りません。
せかいじゅうの すうがくしゃや かがくしゃが
ながく とりくみましたが、
「はやい とき方が ある」も
「ない」も しょうめい できていません。
これが コンピュータかがくで
いちばん ゆうめいな みかいけつ もんだいです。
だから だれかが「かんたん」と いったら
すこし うたがっても いいです。

むずかしい もんだいたち

こういう もんだいは 一つだけでは ありません。
いくつもの まちを いちばん みじかく まわる みち、
おもさの かぎりの なかで
いちばん ねうちの ある にもつを えらぶ ナップサック、
となりどうし いろが かさならないように
ちずを ぬる もんだい。
みかけは ちがっても
なかを 見れば にています。
ばあいの かずが ばくはつし、
かくにんは かんたんだ、という てんが。
下で れいを かえてみて。

れいを おして かえて。(セールスマン · ナップサック · ぬりわけ — どれも おなじ たぐいの むずかしさ)

こんなに にた もんだいが
なん百も あつまっています。
ふしぎなことに この なかの 一つでも
はやく とく ほうほうが 見つかれば、
のこりも ぜんぶ はやく とけます。
たがいに 手を つないでいる わけです。
だから もっと おもしろい。
一つ とけば ぜんぶ とけるのです。

まとめ

一行に あつめましょう。
ある もんだいは 入力が すこし 大きく なるだけで
ばあいの かずが ばくはつするので、
はやい とき方が まだ 知られていません。
でも こたえを 見つけるのは むずかしくても
かくにんは かんたんな ことが おおい。
なら かくにんが はやければ とくのも はやい?
これは まだ だれも 知らない
大きな なぞです。
下で じゅんに おして まとめます。

かなめを じゅんに おして まとめます。(ばくはつ → かくにんは かんたん → まだ みかいけつ)

すべての もんだいが おなじく かんたん では ありません。
ある もんだいは ほんとうに てごわい。
でも てごわいで おわり では ありません。
つぎの はなしでは
かんぺきな こたえを あきらめる かわりに
「じゅうぶん よい こたえ」を はやく 見つける
かしこい ほうほうに であいます。