Autobus, który mieści dwudziestu pasażerów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Autobus, który mieści dwudziestu pasażerów

Post autor: norwimaj » 24 kwie 2013, o 21:45

Całkiem możliwe. Masz jakiś pomysł, jak naprawić ten mankament? Czy ponumerowanie przystanków wystarczy?

Slup
Użytkownik
Użytkownik
Posty: 381
Rejestracja: 27 maja 2016, o 20:49
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 5 razy
Pomógł: 122 razy

Autobus, który mieści dwudziestu pasażerów

Post autor: Slup » 2 cze 2016, o 16:27

Przystanki numeruję liczbami \(\displaystyle{ i=0,1,...,13}\).
Załóżmy najpierw, że w autobusie jest nieskończona liczba miejsc. Na przystanku nr. 0 może wsiąść \(\displaystyle{ 13}\) osób, na przystanku nr. 1 może wsiąść \(\displaystyle{ 12}\) osób i ogólnie na przystanku o numerze \(\displaystyle{ i}\) może wsiąść \(\displaystyle{ 13-i}\) osób. Zatem autobus przewiezie maksymalnie:
\(\displaystyle{ \sum_{i=0}^{13}(13-i)=14\cdot 13-\frac{13\cdot 14}{2}=13\cdot 7=91}\) osób.
Na \(\displaystyle{ 0}\) przystanku wysiada \(\displaystyle{ 0}\) osób, na \(\displaystyle{ 1}\) przystanku wysiada \(\displaystyle{ 1}\) osoba i ogólnie na \(\displaystyle{ i}\)-tym przystanku wysiada \(\displaystyle{ i}\) osób. Zatem liczba pasażerów autobusu na \(\displaystyle{ i}\)-tym przystanku zwiększa się o \(\displaystyle{ 13-i}\) osób, bo tyle wsiada na tym przystanku i zmniejsza się o \(\displaystyle{ i}\) osób, bo tyle osób wysiada. Ogólnie liczba pasażerów na \(\displaystyle{ i}\)-tym przystanku zmienia się o \(\displaystyle{ 13-i-i=13-2i}\) osób. Z tego, że:
\(\displaystyle{ 13-2i\geq 0}\)
dla \(\displaystyle{ i\leq 6}\) wynika, że maksymalna liczba pasażerów, którzy w danym momencie będą podróżowali nieskończonym autobusem wynosi:
\(\displaystyle{ \sum_{i=0}^6(13-2i)=7\cdot 13-2\frac{6\cdot 7}{2}=91-42=49}\)
Stąd można autobus z nieskończoną liczbą miejsc zastąpić autobusem, który ma 49 miejsc. Teraz powstaje pytanie:
Jak to się ma do przypadku autobusu, w którym jest 20 siedzeń?
Weźmy autobus z \(\displaystyle{ 49}\) miejscami i podzielmy go na dwa przedziały. W pierwszym przedziale będzie \(\displaystyle{ 20}\) miejsc, a w drugim przedziale będzie \(\displaystyle{ 29}\) miejsc. Zakładamy, że nikt się nie przesiada z jednego przedziału do drugiego podczas jazdy. Maksymalna liczba pasażerów, którzy mogą przejechać całą trasę wynosi \(\displaystyle{ 91}\). Ponadto w pewnym momencie w obu przedziałach będzie \(\displaystyle{ 49}\) osób. W szczególności w drugim przedziale będzie wtedy \(\displaystyle{ 29}\) osób. Tzn. że spośród wszystkich \(\displaystyle{ 91}\) osób \(\displaystyle{ 29}\) na pewno nie będzie podróżowało pierwszym tj. \(\displaystyle{ 20}\) osobowym przedziałem. Stąd maksymalna liczba osób, które odbyło kurs w \(\displaystyle{ 20}\) osobowym przedziale nie przekracza:
\(\displaystyle{ 91-29=62}\)
Zatem \(\displaystyle{ 20}\)-osobowy przedział może przewieźć maksymalnie \(\displaystyle{ 62}\) osoby. Teraz wysadzamy w powietrze przedział \(\displaystyle{ 29}\) osobowy(najlepiej przed całym kursem, żeby nikomu nic się nie stało). Uzyskujemy \(\displaystyle{ 20}\) osobowy autobus. Mogą zatem nim przejechać maksymalnie \(\displaystyle{ 62}\) osoby.
Taki kurs można zrealizować:
6, 6, 5, 5, 4, 8, 7, 6, 5, 4, 3, 2, 1
Są to liczby osób wsiadających na tych kolejnych przystankach. Jest ich \(\displaystyle{ 13}\), bo tyle jest przystanków, na których można wsiadać. Można sprawdzić, że jest to poprawny kurs.

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3722
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 85 razy
Pomógł: 359 razy

Autobus, który mieści dwudziestu pasażerów

Post autor: arek1357 » 3 cze 2016, o 06:44

aleście tu namiszali

Ameliniowy
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 6 wrz 2018, o 17:45
Płeć: Mężczyzna
Lokalizacja: Polska

Autobus, który mieści dwudziestu pasażerów

Post autor: Ameliniowy » 6 wrz 2018, o 21:11

Założenia:
- jest 13 przystanków
- na końcowym przystanku muszą wysiąść wszyscy pasażerowie

Poniżej jest rozpisany przypadek w którym pomijamy limit pasażerów autobusu:
\(\displaystyle{ \begin{tabular}{rccccccccccccccc} Przystanek & & & & & & & & & & & & & & & \\ 1 & {\green 12} & {\blue 12} & & & & & & & & & & & & & \\ 2 & -1 & {\green 11} & {\blue 22} & & & & & & & & & & & & \\ 3 & -1 & -1 & {\green 10} & {\blue 30} & & & & & & & & & & & \\ 4 & -1 & -1 & -1 & {\green 9} & {\blue 36} & & & & & & & & & & \\ 5 & -1 & -1 & -1 & -1 & {\green 8} & {\blue 40} & & & & & & & & & \\ 6 & -1 & -1 & -1 & -1 & -1 & {\green 7} & {\blue 42} & & & & & & & & \\ 7 & -1 & -1 & -1 & -1 & -1 & -1 & {\green 6} & {\blue 42} & & & & & & & \\ 8 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & {\green 5} & {\blue 40} & & & & & & \\ 9 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & {\green 4} & {\blue 36} & & & & & \\ 10 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & {\green 3} & {\blue 30} & & & & \\ 12 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & {\green 2} & {\blue 22} & & & \\ 12 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & {\green 1} & {\blue 12} & & {\green Suma}\\ 13 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & {\green 0} & {\blue 0} & {\green 78}\\ \end{tabular}}\)

\(\displaystyle{ -1}\) oznacza pasażera który opuścił autobus na danym przystanku. Przykładowo: na pierwszym przystanku wsiada \(\displaystyle{ {\green 12}}\) pasażerów, którzy wysiadają z autobusu na \(\displaystyle{ 12}\) kolejnych przystankach.
\(\displaystyle{ {\green zielony}}\) oznacza ilość pasażerów wsiadających do autobusu na danym przystanku
\(\displaystyle{ {\blue niebieski}}\) oznacza ilość pasażerów w autobusie na danym przystanku (po odjęciu pasażerów którzy wysiedli z autobusu i dodaniu tych, którzy do niego wsiedli).

Jeżeli pominiemy limit pasażerów widzimy, że maksymalna ilość pasażerów jaką może przewieźć autobus to \(\displaystyle{ {\green 78}}\) (suma pasażerów którzy wsiedli do autobusu na wszystkich przystankach). Na przystankach numer \(\displaystyle{ 6}\) i \(\displaystyle{ 7}\) została osiągnięta maksymalna ilość pasażerów jadących w autobusie: \(\displaystyle{ 42}\). Mając te dane możemy wyliczyć rozwiązanie biorąc pod uwagę faktyczny limit wynoszący \(\displaystyle{ 20}\):
\(\displaystyle{ 78 - (42-20) = 56}\)

Poniżej rozpiska dla przypadku z limitem:
\(\displaystyle{ \begin{tabular}{rccccccccccccccc} Przystanek & & & & & & & & & & & & & & & \\ 1 & {\green 10} & {\blue 10} & & & & & & & & & & & & & \\ 2 & -1 & {\green 7} & {\blue 16} & & & & & & & & & & & & \\ 3 & -1 & -1 & {\green 5} & {\blue 19} & & & & & & & & & & & \\ 4 & -1 & -1 & -1 & {\green 4} & {\blue 20} & & & & & & & & & & \\ 5 & -1 & -1 & -1 & -1 & {\green 4} & {\blue 20} & & & & & & & & & \\ 6 & -1 & -1 & -1 & -1 & -1 & {\green 5} & {\blue 20} & & & & & & & & \\ 7 & -1 & -1 & -1 & -1 & -1 & -1 & {\green 6} & {\blue 20} & & & & & & & \\ 8 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & {\green 5} & {\blue 18} & & & & & & \\ 9 & -1 & -1 & & & -1 & -1 & -1 & -1 & {\green 4} & {\blue 16} & & & & & \\ 10 & -1 & & & & & -1 & -1 & -1 & -1 & {\green 3} & {\blue 14} & & & & \\ 12 & -1 & & & & & -1 & -1 & -1 & -1 & -1 & {\green 2} & {\blue 10} & & & \\ 12 & & & & & & & -1 & -1 & -1 & -1 & -1 & {\green 1} & {\blue 6} & & {\green Suma}\\ 13 & & & & & & & -1 & -1 & -1 & -1 & -1 & -1 & {\green 0} & {\blue 0} & {\green 56} \\ \end{tabular}}\)

ODPOWIEDZ