エレガントな証明はありませんか？

質問

サーキット上にｎ台の車(燃費は同じ）が止まっている。全ての車のガソリンを合計するとちょうどサーキットを１周できる量である。今、１台の車を選んで走らせます。途中で別の車に達したらその車のガソリンを自車に移すことができるとします。（別の車に到達する前にガソリンが切れたらそこで終わりです。）
問題：ｎ>=１で初期の車の位置関係およびガソリンの量の配分がどんな場合であっても、１週することができる車を選ぶことができる事を示せ。
私の答え：（１）初期状態でｎ台の車のうち必ず次の車に到達できる車が１台はある。（でないと合計ガソリンが１周分とならない）
（２）その車をＡ、次の車をＢとして、最初からＡにはＡ＋Ｂのガソリンがあったものとして、Ｂは最初からなかったものと考える事ができる。
（３）すると問題はｎ－１台の問題に還元される。これを続けるとｎ＝１台の問題となり。この１台が選ぶべき車。
（還元させていく過程で複数候補がありうるので最終的な車は１台とは限らないが）

この証明に穴はないでしょうか？　背理法とか用いたエレガントな証明はありませんか？

回答No.2

Mandheling · ベストアンサー

（2）が微妙。
　AとBのガソリンの合計で、さらに次の車まで到達できるかどうかはわからないと思います。

自分なりの回答
サーキットに並んでいる車の順番に1，2，3、・・・、nとします。
　a(i)　i番目の車に積まれているガソリンの量
　b(i)　i番目から(i+1)番目まで進むときに消費するガソリンの量
とします。
　c(i)＝a(i)-b(i)　
とし、
　S(i)＝c(1)+c(2)+・・・+c(i)
としたとき、S(i)は、（i+1）番目の車に到達したときのガソリンの残量を意味します。
そして　S(i)＜0であれば、ガソリンが切れ一周できないということになります。
また、すべての車のガソリンで1週できるのですからS(n)＝０です。
サーキットを一周するためには、S(1)～S(n)全てにおいて0以上であることが必要です。

そこで

S(1)・・・S(k)・・・S(n)　と並べて比べたとき、最小値をS(k)とします。
S(k)＝0なら、この順番で走行可能
S(k)＜0のとき、
　　i<=n-kのとき　T(i)＝c(k+1)+c(k+2)+・・・+c(k+i)
　　i>n-kのとき　 T(i)＝c(k+1)+c(k+2)+・・・+c(n)+c(1)+・・・+c(k+i-n)　　
　　とすればT(1)～T(n)すべてにおいて0以上になるので、
　　（k+1）番目の車からスタートすれば走行可能。

お礼

回答ありがとうございます。提示された回答はただいま検証中です。
＞AとBのガソリンの合計で、さらに次の車まで到達できるかどうかはわからないと思います。

A+Bのガソリンで次の車まで進めるかどうかは関係ないのです。Bの車を問題から消すことができ、n-1台の問題に縮小されるというのが私の考え方です。別の車Cから初めてAに到達できたとすると、Bまでいくことができますよね。なのでAにA+BのガソリンがありBは最初からないものとして考えられるというのが趣旨です。

補足

i<=n-kのとき　T(i)=c(k+1)+c(k+2)+...+c(k+i)=s(k+i)-s(k)
i>n-kのとき T(i)=c(k+1)+c(k+2)+...+c(n)+c(1)+...+c(k+i-n)=s(n)-s(k)+s(k+i-n)=s(k+i-n)-s(k)
上記2式ともs(m)-s(k)の形になりs(k)が最小という仮定なので0以上になるわけですね。納得しました。
残量をのこぎりグラフで書くと残量最小のところを始点とすると0以上になりますね。

回答No.8

hrsmmhr

ｈにmを含めるかどうかの件ですが、含めてもいいと思いだしました

d(am,am)=f(am,am)が分かっているのに敢えて違う仮定を置くのが
私の頭の中では考えにくく、つまりそうすることで整理ができるんだと思います
（結局何行か追加して書くかどうかの問題ですし）

理解の仕方の問題ですので、分かりやすいほうでご理解ください

回答No.7

hrsmmhr

＞同様にa2からa3,a3からa4に…と試行していくうちにもとのa1までたどり着けるamが存在する
＞は自明なのでしょうか？
ここでいっているのは
an→an+1→...→a(n+1)-1-×-a(n+1)
のようにa(n+1)-1までで燃料が付きa(n+1)にたどり着けないのなら、次はa(n+1)から始めることを言ってます。なので
★a1-1=a(m-1)でd(a(m-1),a1(=am))>f(a(m-1),a1)
（これはa(m-2)からの試行がa(m-1)-1で終わっているときです）
だったり
★a1=amでa(m-1)からの試行がam-1＝a1-1で終わる
としても、その次はam=a1としてa1から距離0でたどり着いていると考えています
そうすることで以後の証明でのamの取り扱いに何の変更も必要無いと思います

＞あるh(a<=h<m)が存在してd(am,ah)>f(am,ah)
＞ここはh(1<=h<=m)　ｍも含める　ので良いのでは？
mを含めるとd(am,ah)>f(am,ah)の仮定の式も等号が必要になってきますので
記述上の問題としてmは除きました
h(1<=h<m)でたどり着けないということを仮定しているので、
たどり着けないのだからd(am,ah)>f(am,ah)と仮定を式にしてます
そう仮定したら矛盾するからd(am,ah)<=f(am,ah)なのだと言うのがここでの結論なのですから
こう書かざるを得ません
等号を入れたら論理を正しく書くのにスッキリとは書けそうに無いと思います

＞hがmのときはam-1までは辿り着け、最後は必ず辿り着けるのは問題の前提から明らか
＞ここが理解できません。
上で書いたように、h=mでは等号で終わることを書いています
a1、a3、…a(m-1)が存在するということは、各地点から始めて一周出来ない場合なので
これらの試行で終わらないのならam－a1の間の車しか起点に出来ないはずです
（ちょうど距離分の燃料が、各am,am+1,am+2…にあるのなら、その間のどこからでも始められます）
a(m-1)から始めるとam-1までで途切れてしまいますが、
amから始めると、a(m-1)までたどり着き、当然am-1までたどり着けますが
そこまでたどり着けるなら、全ての車の燃料を回収しているのだから、問題の条件により
最後のam-1→amは必ずたどり着けてd(am,am(+n))=f(am,am(+n))
で終わるはずだということを書いています。

結論になってしまいます。

お礼

詳細な説明ありがとうございます。理解できたようです。

回答No.6

noname#149523

質問文にある解法でよいと思います。以下は背理法です。選ぶことはできるけれどどれを選べばよいのかまでは分からないのでエレガントとはいえないかもしれません。

どの車から始めても1周できないとする。
少なくとも1台は自身のガソリンだけでは次の車までたどりつけない車がある。その車の次の車の位置をp(0)=0とする。n台についてp(0)<...<p(n-1)
1周の長さをL、燃費はガソリン1に対して距離1とする。
ガソリンをp(i)+α使ってp(i)とp(i+1)の間で止まったとする。p(i)+α<p(i+1)
i+1からn-1の車について
残りの距離　　L-p(i+1)
ガソリンの和　L-(p(i)+α)
残りの距離 < ガソリンの和
i<n-1に注意してp(i+1)=p(n-1)になるまで上のプロセスを繰り返す。
するとp(n-1)においても上の不等式が成り立つことになってしまう。

お礼

ありがとうございます。検証してみます。

回答No.5

Tacosan

本質的にはこれで OK. 帰納法ですね. まあ, この筋が最もシンプルじゃないかな.

お礼

ありがとうございます。安心しました。

回答No.4

hrsmmhr

補足読みました。そして質問者さんの証明も再確認しました。

よく読むと質問者さんの証明であっていると思います

私のよりシンプルでよりエレガントではないでしょうか？

回答No.3

hrsmmhr

すみません。勝手に均等にガソリンを積んでいるという問題に変えてしまっていました

以下修正です
---------------------------------------------------------------------

適当に周回の順番に番号を振り、ある車a1番目から始める。また一周の長さを1とする
a1=1から初めて一周できないとき、到達できなかった車a2から再度始める
このとき少なくともa1番目の車からa2番目の車までの距離d(a1,a2)は
a1番目からa2-1番目までの燃料で走れる距離の総和f(a1,a2)よりおおきい
同様にa2からa3,a3からa4に…と試行していくうちに
もとのa1までたどり着けるamが存在するが
am番目の車とa1の車の距離d(am,a1)は
d(am,a1)=1-d(a1,am)
あるh(a<=h<m)が存在してd(am,ah)>f(am,ah)としたなら
d(am,ah)=d(am,a1)+d(a1,ah)=1-d(a1,am)+d(a1,ah)=1-d(ah-am)>f(am,ah)
d(ah,am)<1-f(am,ah)=f(ah,am)
これは各d(ak,a(k+1))(h<=k<m)がf(ak,a(k+1))おりおおきいことに反する
従ってすべてのh(a<=h<m)についてd(am,ah)<=f(am,ah)
hがmのときはam-1までは辿り着け、最後は必ず辿り着けるのは問題の前提から明らか

補足

ありがとうございます。私の回答がエレガントかどうかはおいといて、いくつか質問があります。
＞同様にa2からa3,a3からa4に…と試行していくうちにもとのa1までたどり着けるamが存在する
　は自明なのでしょうか？
＞あるh(a<=h<m)が存在してd(am,ah)>f(am,ah)
　ここはh(1<=h<=m)　ｍも含める　ので良いのでは？
＞hがmのときはam-1までは辿り着け、最後は必ず辿り着けるのは問題の前提から明らか
　ここが理解できません。

全体的には背理法を使っており方向としてOKな気がします。

回答No.1

hrsmmhr

(3)はいえないかもしれません。選ぶ車はそこまで乗ってきた車にしかできないのでは？
（そういう問題ですよね？）

適当に周回の順番に番号を振り、ある車a1番目から始める。また一周の長さを１とする
a1=1から初めて一周できないとき、到達できなかった車a2から再度始める
このとき少なくともa1番目の車からa2番目の車までの距離d(a1,a2)は(a2-a1)/nよりおおきい
同様にa2からa3,a3からa4に…と試行していくうちに
もとのa1までたどり着けるamが存在するが
am番目の車とa1の車の距離d(am,a1)は
d(am,a1)=1-d(a1,am)
あるh(a<=h<m)が存在してd(am,ah)>(n+ah-am)/nとしたなら
d(am,ah)=d(am,a1)+d(a1,ah)=1-d(a1,am)+d(a1,ah)>(n+ah-am)/n
d(ah,am)<(am-ah)/n
これは各d(ak,a(k+1))(h<=k<m)がa((k+1)-ak)/nおりおおきいことに反する
従ってすべてのh(a<=h<m)についてd(am,ah)<=(n+ah-am)/n
hがmのときはam-1までは辿り着け、最後は必ず辿り着けるのは問題の前提から明らか

お礼

回答ありがとうございます。提示された回答はただいま検証中です。
＞(3)はいえないかもしれません。選ぶ車はそこまで乗ってきた車にしかできないのでは？

説明が難しいのですが、私の考え方は１台数が減った時点で（Bをないものとした時点）で新たに問題を見直してみると、n-1台の問題となっているのでは、そして最初と同様にAとB（最初のAとBとは違う）となる車を選び、再びBの車を消していく。この手順を繰り返していくと1台に還元されるという考え方です。