szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Ciężki dowod
PostNapisane: 7 mar 2016, o 11:24 
Użytkownik

Posty: 3
Lokalizacja: Wroclaw
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 p_{i}, a odległość od i-tej stacji do następnej wynosi d_{i}. Udowodnij, że dla dowolnej liczby stacji n warunek \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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
 Tytuł: Ciężki dowod
PostNapisane: 7 mar 2016, o 12:38 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
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ć.
Góra
Mężczyzna Offline
 Tytuł: Ciężki dowod
PostNapisane: 7 mar 2016, o 12:58 
Użytkownik

Posty: 3
Lokalizacja: Wroclaw
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ć
Góra
Mężczyzna Offline
 Tytuł: Ciężki dowod
PostNapisane: 7 mar 2016, o 13:03 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
na pierwszej tankujesz
Góra
Mężczyzna Offline
 Tytuł: Ciężki dowod
PostNapisane: 7 mar 2016, o 13:08 
Użytkownik

Posty: 3
Lokalizacja: Wroclaw
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?
Góra
Mężczyzna Offline
 Tytuł: Ciężki dowod
PostNapisane: 7 mar 2016, o 13:26 
Administrator

Posty: 22627
Lokalizacja: Wrocław
Tankujesz na stacji startowej.

JK
Góra
Mężczyzna Online
 Tytuł: Ciężki dowod
PostNapisane: 7 mar 2016, o 16:24 
Użytkownik

Posty: 15103
Lokalizacja: Bydgoszcz
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 --

Gouranga napisał(a):
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.
Góra
Mężczyzna Offline
 Tytuł: Ciężki dowod
PostNapisane: 8 mar 2016, o 01:44 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
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.
Góra
Mężczyzna Online
 Tytuł: Ciężki dowod
PostNapisane: 8 mar 2016, o 06:27 
Użytkownik

Posty: 15103
Lokalizacja: Bydgoszcz
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.
Góra
Mężczyzna Offline
 Tytuł: Ciężki dowod
PostNapisane: 8 mar 2016, o 21:10 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
a4karo napisał(a):
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 p_i\ge d_i, to możemy zlikwidować stację nr i+1 i przełożyć z niej paliwo do stacji i, a następnie powołać się na założenie indukcyjne dla n-1 stacji.
Góra
Mężczyzna Online
 Tytuł: Ciężki dowod
PostNapisane: 8 mar 2016, o 21:13 
Użytkownik

Posty: 15103
Lokalizacja: Bydgoszcz
No to napisz ten dowód od początku do końca, zamiast mamic jakimiś ideami.
Góra
Mężczyzna Offline
 Tytuł: Ciężki dowod
PostNapisane: 8 mar 2016, o 21:38 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
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 takiej książeczce, ale chyba już ciężko ją dostać.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 ciężki dowód  tukanik  0
 Dowód osobisty  Nati071188  3
 dowód z liczbami Stirilinga  manduka  2
 Wyznaczanie drzewa z kodu Prüfera - dowód na brak cyklu  wildzins  1
 Dowód zachowania stopnia wierzchołka w izomorfizmie grafów  Renq77  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl