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

学問

環状の道路に，N軒のガソリンスタンドが時計回りに1からNまで番号づけられて並んでいる．燃料タンクが空の状態から出発し，途中でガソリンが不足することなく車でこの環状道路を時計回りに一周したい．ガソリンスタンドiではp_iリットルのガソリンが補給される．ガソリンスタンドiから次のガソリンスタンドまで移動するのにq_iリットルのガソリンを消費する．ここで
\sum_{i=1}^Np_i = \sum_{i=1}^Nq_i
が成り立っているとする．ガソリンスタンドiから時計回りにガソリンスタンドjに至る経路上のガソリンスタンドの集合(ただしiは含みjは含まない) をS_{ij}とし，
{\rm gain}(i,j) = \sum_{k\in S_{ij}}(p_k-q_k)
とおく．このとき，以下の(1), (2) に答えよ．
(1) ガソリンスタンド1から出発して，一周して出発点まで戻れるための必要十分条件を{\rm gain}を用いて表せ．
(2) 適当なガソリンスタンドが存在し，そこを出発点として一周できることを示せ．

(1)まず、
{\rm gain}(1,k+1) \geq 0 \Longleftrightarrow {\rm gain}(1,k)+p_k-q_k \geq 0
であるから、{\rm gain}(1,k+1) \geq 0は1から出発してもしkに行けるとするならば、k+1にも行ける、ことの必要十分条件。
また、\sum_{i=1}^Np_i = \sum_{i=1}^Nq_iであるから、1から出発して、Nに行ければ一周できる。従って
一周できる \Longleftrightarrow 1から2,3,\ldots,Nに到達できる \Longleftrightarrow \forall i=1,2,\ldots,N \ {\rm gain}(1,i) \geq 0
である。
(2)示すべきは
\exists i \in \{1,2,\ldots,N} \ \forall j \in \{1,2,\ldots,N} {\rm s.t.}\ \ {\rm gain}(i,j)\geq 0
背理法を用いる。つまり、
\forall i \in \{1,2,\ldots,N} \ \exists j \in \{1,2,\ldots,N} {\rm s.t.} \ \ {\rm gain}(i,j) < 0
を仮定して、矛盾を導く。
まず、i_0 = 1として、i_0に（時計回りで）一番近く{\rm gain}(i_0,j) < 0を満たすjをi_1 = jとする。
以下同様にして、i_kに一番近く{\rm gain}(i_k,j) <0を満たすものをi_{k+1}=jとする。
すると、あるjが存在して、
i_{j-1} \leq N,\ 1 \leq i_j
となる。このとき、i_0=1であるから、あるkが存在して
i_k \leq i_j < i_{k+1}
となる。以下i_k=i_jとi_k < i_jの二通りの場合に分けて考える。
(ァ)i_k=i_jの場合
このときは{\rm gain}の和を考えると、矛盾が生じる。つまり、
{\rm gain}(i_k,i_{k+1}) +{\rm gain}(i_{k+1},i_{k+2}) + \cdots +{\rm gain}(i_{j-1},i_k) = \sum_{i=1}^N(p_i-q_i)
であるが、左辺は負であるが、右辺は問題の前提より零。これは矛盾。
(イ)i_k < i_jの場合
ここで、i_jは{\rm gain}(i_{j-1},i_j) < 0を満たす一番近いものを選んできているので{\rm gain}(i_{j-1},i_k) \geq 0である。
よって、{\rm gain}(i_k,i_j) < 0であるが、これはi_j < i_{k+1}に反する。
（i_{k+1}は{\rm gain}(i_k,i_{k+1}) < 0を満たす一番近いもののはずである。）
したがって、矛盾。
以上より、
\exists i \in \{1,2,\ldots,N} \ \forall j \in \{1,2,\ldots,N} {\rm s.t.}\ \ {\rm gain}(i,j)\geq 0
であることが分かった。