TSP-Traveling gas Statoin Problem（巡回ガソリンスタンド問題）

環状の道路に，軒のガソリンスタンドが時計回りに1からまで番号づけられて並んでいる．燃料タンクが空の状態から出発し，途中でガソリンが不足することなく車でこの環状道路を時計回りに一周したい．ガソリンスタンドではリットルのガソリンが補給される．ガソリンスタンドから次のガソリンスタンドまで移動するのにリットルのガソリンを消費する．ここで

が成り立っているとする．ガソリンスタンドから時計回りにガソリンスタンドに至る経路上のガソリンスタンドの集合(ただしは含みは含まない) をとし，

とおく．このとき，以下の(1), (2) に答えよ．

(1) ガソリンスタンド1から出発して，一周して出発点まで戻れるための必要十分条件をを用いて表せ．

(2) 適当なガソリンスタンドが存在し，そこを出発点として一周できることを示せ．

(1)まず、

であるから、は1から出発してもしに行けるとするならば、にも行ける、ことの必要十分条件。

また、であるから、1から出発して、に行ければ一周できる。従って

一周できる 1からに到達できる

である。

(2)示すべきは

背理法を用いる。つまり、

を仮定して、矛盾を導く。

まず、として、に（時計回りで）一番近くを満たすをとする。

以下同様にして、に一番近くを満たすものをとする。

すると、あるが存在して、

となる。このとき、であるから、あるが存在して

となる。以下との二通りの場合に分けて考える。

(ァ)の場合

このときはの和を考えると、矛盾が生じる。つまり、

であるが、左辺は負であるが、右辺は問題の前提より零。これは矛盾。

(イ)の場合

ここで、はを満たす一番近いものを選んできているのでである。

よって、であるが、これはに反する。

（はを満たす一番近いもののはずである。）

したがって、矛盾。

以上より、

であることが分かった。