Ciężki dowod

[adriannnn69]

Znalazlem bardzo problematyczne dla mnie zadanie, nie wiem z której strony je ugryźć i jak się zabrać, a nigdzie nie mogę znaleźć pomocy więc prosiłbym jakąś dobrą duszę o pomoc. Treść zadania jest nastepujaca:

Na zamkniętym torze wyścigowym (petli) znajduje się n stacji benzynowych. Na i-tej stacji znajduje się paliwo potrzebne do przejechania dystansu \(\displaystyle{ p_{i}}\), a odległość od i-tej stacji do następnej wynosi \(\displaystyle{ d_{i}}\). Udowodnij, że dla dowolnej liczby stacji n warunek \(\displaystyle{ \sum^{n}_{i=1} p_{i} > \sum^{n}_{i=1} d_{i}}\) zapewnia, że istnieje taka stacja, że rozpoczynając od niej podróż z pustym bakiem będzie w stanie objechac tor dookoła.

[Gouranga]

suma całego paliwa jest większa niż potrzebna na przejechanie całego toru. Rozkładając na każdą stację tyle paliwa, żeby wystarczyło akurat na dojechanie do następnej zostajemy z pewną rezerwą, którą trzeba gdzieś dołożyć. Jeśli z którejś ze stacji zabierzemy teraz część paliwa, tzn. tankując tylko na niej nie dojedziesz do następnej, to gdzieś będzie tego paliwa więcej, zawsze możesz zacząć od tej konkretnej, na której jest więcej, niż na dojazd na kolejną i potem do tego nadmiaru uzupełniać.

[adriannnn69]

No ok, dzięki Tobie zrozumiałem chociaż treść zadania. Jak mam dojechać na inną stacje mając pusty bak? Czy po prostu na tej startowej stacji mam pusty ale na niej także tankuje? Jak to matematyczne zapisać

[Gouranga]

na pierwszej tankujesz

[adriannnn69]

Odpowiedź na moje pytanie może jest trywialna ale nie mam wystarczająco utworzonych oczu na to zadania najwyraźniej stąd pytanie jakim cudem dojadę że stacji startowej na stację pierwsza w kolejności o pustym baku?

[Jan Kraszewski]

Tankujesz na stacji startowej.

JK

[a4karo]

No to niestety nie sa rozwiązania: na stacji startowej może nie być tyle paliwa, żeby dojechac do najbliższej.

Zadanie jest klasyczne, a piękne rozwiązanie znajdujemy u Martina Gardner:

Umieszczamy samochód z ogromnym bakiem i dużą ilością paliwa na dowolnej stacji i objeżdżamy trasę zabierając za każdym razem paliwo. W ten sposób objedziemy cała trasę, i paliwa będziemy mieli w baku co najmniej tyle ile na poczatku.

Popatrzmy na wykres wskazujący ilość paliwa: będzie skłądał się on z kawałków malejących i miał skoki na każdej stacji.

Wybierzmy jako stację początkową tę, na której wskaźnik pokazał najmniejszą wartość

-- 7 mar 2016, o 15:26 --

suma całego paliwa jest większa niż potrzebna na przejechanie całego toru. Rozkładając na każdą stację tyle paliwa, żeby wystarczyło akurat na dojechanie do następnej zostajemy z pewną rezerwą, którą trzeba gdzieś dołożyć. Jeśli z którejś ze stacji zabierzemy teraz część paliwa, tzn. tankując tylko na niej nie dojedziesz do następnej, to gdzieś będzie tego paliwa więcej, zawsze możesz zacząć od tej konkretnej, na której jest więcej, niż na dojazd na kolejną i potem do tego nadmiaru uzupełniać.

Dowcip polega na tym, że nie możesz przekładać paliwa z jednej stacji do drugiej.

[Gouranga]

a4karo, chyba się nie zrozumieliśmy. Chodziło mi o to, że jeśli na którejś stacji nie ma dość paliwa, żeby dojechać do kolejnej, to na pewno na innej stacji jest tego paliwa aż w nadmiarze i to od niej należy zacząć.
W zadaniu jest mowa o tym, że istnieje co najmniej jedna taka stacja, a nie, że startując z dowolnej przejedziemy.

[a4karo]

Zrozumiałem co chciałeś powiedzieć. Tyle, że może się zdarzyć, że do pierwszej i drugiej dojedziesz, a co trzeciej już nie. Zatem argument : startuj że stacji, z której dojedziesz do następnej jest niewystarczający.

[norwimaj]

Tyle, że może się zdarzyć, że do pierwszej i drugiej dojedziesz, a co trzeciej już nie. Zatem argument : startuj że stacji, z której dojedziesz do następnej jest niewystarczający.

To prawda, ale stwierdzenie, że istnieje stacja, z której można dojechać do następnej, można wykorzystać w dowodzie indukcyjnym. Jeśli \(\displaystyle{ p_i\ge d_i,}\) to możemy zlikwidować stację nr \(\displaystyle{ i+1}\) i przełożyć z niej paliwo do stacji \(\displaystyle{ i,}\) a następnie powołać się na założenie indukcyjne dla \(\displaystyle{ n-1}\) stacji.

[a4karo]

No to napisz ten dowód od początku do końca, zamiast mamic jakimiś ideami.

[norwimaj]

Tu sobie możesz przypomnieć, co to indukcja. Myślę że w bieżącym temacie udało mi się udzielić wystarczającej wskazówki dla tych, którzy chcą pogłówkować. Ten sposób rozwiązania jest szczegółowo opisany w książeczce, ale chyba już ciężko ją dostać.