面白い問題を見つけたのでメモしておく。
円環状の道路に、ガソリンスタンドが点在している。道路上のすべてのスタンドのガソリンを集めても、ちょうど道路を1周する分のガソリンしかない。今、ガソリンタンクが空っぽの車がある。このとき、あるガソリンスタンドから出発すれば、途中でガス欠することなく道路を1周できることを示せ。
この問題はマーティン・ガードナーの連載記事が由来とも、ラースロー・ロヴァースが作ったとも言われているらしい。自分がこの問題を知ったのは、ピーター・ウィンクラーの『数学パズル』に載っていたからである。
- 作者: ピーターウィンクラー,坂井公,岩沢宏和,小副川健
- 出版社/メーカー: 日本評論社
- 発売日: 2011/07/08
- メディア: 単行本
- 購入: 2人 クリック: 81回
- この商品を含むブログ (5件) を見る
どこでもいいので、適当なガソリンスタンドから(仮想的に)出発して道路を1周し、(そこまでに給油できるガソリンの量) - (そこまでに必要なガソリンの量)を下のようなグラフにしてみる。スタンド2についた時にはガソリンが1余っており、スタンド3についた時には3足りない(のでスタンド3に行く途中でガス欠したはず)、といった感じ。
ここで、グラフが最小値を取る点に対応するスタンドから出発すると、道路を1周できる。なぜなら、グラフが横軸より上にあることと途中でガス欠を起こさないことは等価であり、出発するスタンドを変えることはそこが0になるようにグラフを縦に平行移動することと等価であるからである。