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 »

Całkiem możliwe. Masz jakiś pomysł, jak naprawić ten mankament? Czy ponumerowanie przystanków wystarczy?
Awatar użytkownika
Slup
Użytkownik
Użytkownik
Posty: 778
Rejestracja: 27 maja 2016, o 20:49
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 23 razy
Pomógł: 155 razy

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

Post autor: Slup »

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: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

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

Post autor: arek1357 »

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 »

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}}\)
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

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

Post autor: matemix »

Załóżmy, że pasażerowie mogą wsiadać od \(\displaystyle{ 1}\) do \(\displaystyle{ 12}\) przystanku, a wysiadać - w rozumieniu zwalniać miejsce dla innych - od \(\displaystyle{ 2}\) do \(\displaystyle{ 12}\) przystanku (zakładam, że na \(\displaystyle{ 13}\) ostatnim przystanku już nikt nie wsiądzie).

Załóżmy, że na każdym przystanku wsiada zawsze \(\displaystyle{ 5}\) pasażerów. Stąd przez kolejne \(\displaystyle{ 5}\) przystanków może wysiadać po jednym pasażerze, którzy wsiedli kolejno na \(\displaystyle{ 1,2,3,...}\) przystanku. Wsiadający będą zatem opisani takim ciągiem \(\displaystyle{ 5,5,5,...}\), a wysiadający będą \(\displaystyle{ 1,2,3,4,5,5,5,...}\). Po pierwszym przystanku wysiada jeden pasażer, po drugim - dwóch pasażerów, z pierwszego i drugiego przystanku, po trzecim wysiada trzech. Po \(\displaystyle{ 5}\) przystankach nie może wysiąść więcej niż \(\displaystyle{ 5}\) pasażerów, bo wszyscy, którzy wsiedli na pierwszym przystanku już wysiedli, zaś inni nie mogą wysiadać dwójkami, gdy wsiedli na tym samym przystanku. Więc przez resztę trasy wysiada ich zawsze \(\displaystyle{ 5}\).

Łatwo wykazać, rozpisując sumę zajętych miejsc, że liczba miejsc nigdy nie przekroczy \(\displaystyle{ 15}\) w tym scenariuszu. Nie jest to więc rozwiązanie maksymalne. Rzecz w tym, że w teście wyboru, ponoć na inteligencję, podają, że maksymalnie pasażerów może wsiąść w czasie przejazdu całej trasy:
a) 20
b) 55
c) 56



Tymczasem mój przykład pokazuje, że może to być więcej. Albo źle mi się wydaje i to wskazuje, że "nie dostałbym się do Mensy" :)

PS Tak wiem odkopałem wątek, ale natknąłem się na to zadanie przed chwilą, a solidnego, niebudzącego wątpliwości rozwiązania w tym wątku chyba nie ma.
Awatar użytkownika
Slup
Użytkownik
Użytkownik
Posty: 778
Rejestracja: 27 maja 2016, o 20:49
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 23 razy
Pomógł: 155 razy

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

Post autor: Slup »

matemix pisze: 13 gru 2021, o 05:49 Wsiadający będą zatem opisani takim ciągiem \(\displaystyle{ 5,5,5,...}\)
Wydaje mi się, że nie mogą być opisani takim ciągiem. Wynika to na przykład stąd, że na przedostatnim czyli 12 przystanku może wsiąść tylko jedna osoba. Generalnie mogą być opisani zmodyfikowanym ciągiem
$$\underbrace{5,5,...,5}_{8\,razy},4,3,2,1,0$$
co daje łącznie
$$5\cdot 8 + 4 + 3 + 2 + 1 = 40 + 10 = 50$$
pasażerów.
matemix pisze: 13 gru 2021, o 05:49 PS Tak wiem odkopałem wątek, ale natknąłem się na to zadanie przed chwilą, a solidnego, niebudzącego wątpliwości rozwiązania w tym wątku chyba nie ma.
Poprawna odpowiedź to 56 pasażerów, a poprawne rozwiązanie znajduje się we wpisie Ameliniowego (o ile nie pomylił się w rachunkach). Jest ono dokładnie tym samym rozwiązaniem, co to z mojego postu, z tą różnicą, że ja błędnie zrozumiałem, że wszystkich przystanków jest \(\displaystyle{ 14}\). Myślę, że idea rozwiązania, która znajduje się z moim poście jest poprawna, ale chętnie na ten temat podyskutuję i przyznam do potencjalnego błędu.
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

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

Post autor: matemix »

Slup pisze: 13 gru 2021, o 17:12Wydaje mi się, że nie mogą być opisani takim ciągiem. Wynika to na przykład stąd, że na przedostatnim czyli 12 przystanku może wsiąść tylko jedna osoba.
Dlaczego może tam wsiąść tylko jedna osoba? Ja to widzę tak:

I przystanek: wsiada 5 osób

II przystanek: wsiada 5 osób, wysiada 1 osoba z I przystanku

III przystanek: wsiada 5 osób, wysiada 1 osoba z I przystanku + 1 osoba z II przystanku

IV przystanek: wsiada 5 osób, wysiada 1 osoba z I przystanku + 1 osoba z II przystanku + 1 osoba z III przystanku

V przystanek: wsiada 5 osób, wysiada 1 osoba z I przystanku + 1 osoba z II przystanku + 1 osoba z III przystanku + 1 osoba z IV przystanku

VI przystanek: wsiada 5 osób, wysiada 1 osoba z I przystanku (ostatnia, która tam wsiadła) + 1 osoba z II przystanku + 1 osoba z III przystanku + 1 osoba z IV przystanku + z osoba z V przystanku

VII przystanek: wsiada 5 osób, wysiada 1 osoba z II przystanku (ostatnia, która tam wsiadła) + 1 osoba z III przystanku + 1 osoba z IV przystanku + 1 osoba z V przystanku + 1 osoba z VI przystanku

VIII przystanek: wsiada 5 osób, wysiada 1 osoba z III przystanku + 1 osoba z IV przystanku + 1 osoba z V przystanku + 1 osoba z VI przystanku + 1 osoba z VII przystanku

IX przystanek: wsiada 5 osób, wysiada 1 osoba z IV przystanku + 1 osoba z V przystanku + 1 osoba z VI przystanku + 1 osoba z VII przystanku + 1 osoba z VIII przystanku

X przystanek: wsiada 5 osób, wysiada 1 osoba z V przystanku + 1 osoba z VI przystanku + 1 osoba z VII przystanku + 1 osoba z VIII przystanku + 1 osoba z IX przystanku

XI przystanek: wsiada 5 osób, wysiada 1 osoba z VI przystanku + 1 osoba z VII przystanku + 1 osoba z VIII przystanku + 1 osoba z IX przystanku + 1 osoba z X przystanku

XII przystanek: wsiada 5 osób, wysiada 1 osoba z VII przystanku + 1 osoba z VIII przystanku + 1 osoba z IX przystanku + 1 osoba z X przystanku + 1 osoba z XI przystanku
Awatar użytkownika
Slup
Użytkownik
Użytkownik
Posty: 778
Rejestracja: 27 maja 2016, o 20:49
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 23 razy
Pomógł: 155 razy

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

Post autor: Slup »

Na 13 czyli ostatnim przystanku musiałyby wysiąść wtedy wszystkie osoby, które wsiadły na 12 przystanku. Tych osób byłoby 5, a to jest niezgodne z warunkami zadania.
Awatar użytkownika
kinia7
Użytkownik
Użytkownik
Posty: 704
Rejestracja: 28 lis 2012, o 11:58
Płeć: Kobieta
Lokalizacja: Wrocław
Podziękował: 89 razy
Pomógł: 94 razy

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

Post autor: kinia7 »

na kolejnych przystankach licząc pętlę początkową jako przystanek P a końcową jako K
P - wsiada +7, w autobusie jest 7 osób
01 - wysiada -1, wsiada +7, w autobusie jest 13
02 - -2, +6, 17
03 - -3, +5, 19
04 - -4, +5, 20
05 - -5, +5, 20
06 - -6, +6, 20
07 - -7, +6, 19
08 - -6, +5, 18 nie może wsiąść więcej, gdyż do pętli zostało 5 przystanków
09 - -6, +4, 16
10 - -5, +3, 14
11 - -5, +2, 11
12 - -6, +1, 6
K -- -6, 0

razem autobus przewiózł +7+7+6+5+5+5+6+6+5+4+3+2+1=62 pasażerów

jest to maksymalna ilość
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

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

Post autor: matemix »

Slup pisze: 13 gru 2021, o 17:48 Na 13 czyli ostatnim przystanku musiałyby wysiąść wtedy wszystkie osoby, które wsiadły na 12 przystanku. Tych osób byłoby 5, a to jest niezgodne z warunkami zadania.
Faktycznie, zapomniałem o tym, że na ostatnim muszą wysiąść wszyscy. W takim razie również uzyskuję wynik \(\displaystyle{ 56}\).

Dodano po 9 minutach 51 sekundach:
kinia7 pisze: 14 gru 2021, o 21:28 na kolejnych przystankach licząc pętlę początkową jako przystanek P a końcową jako K
P - wsiada +7, w autobusie jest 7 osób
01 - wysiada -1, wsiada +7, w autobusie jest 13
02 - -2, +6, 17
03 - -3, +5, 19
04 - -4, +5, 20
05 - -5, +5, 20
06 - -6, +6, 20
07 - -7, +6, 19
08 - -6, +5, 18 nie może wsiąść więcej, gdyż do pętli zostało 5 przystanków
09 - -6, +4, 16
10 - -5, +3, 14
11 - -5, +2, 11
12 - -6, +1, 6
K -- -6, 0

razem autobus przewiózł +7+7+6+5+5+5+6+6+5+4+3+2+1=62 pasażerów

jest to maksymalna ilość
Masz o jeden przystanek za dużo. Suma nie może się składać z \(\displaystyle{ 13}\) elementów, bo na \(\displaystyle{ 13}\) ostatnim przystanku nikt już nie wsiada, wszyscy muszą wysiąść.
Awatar użytkownika
Slup
Użytkownik
Użytkownik
Posty: 778
Rejestracja: 27 maja 2016, o 20:49
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 23 razy
Pomógł: 155 razy

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

Post autor: Slup »

Niech \(\displaystyle{ n}\) będzie liczbą przystanków (łącznie z końcowym i początkowym). Dla \(\displaystyle{ n=14}\) maksymalna liczba pasażerów to 62. Dla \(\displaystyle{ n=13}\) maksymalna liczba pasażerów to 56. Oczywiście trzeba uzasadnić, że to są maksima dla tych wartości \(\displaystyle{ n}\). Kilka lat temu udowodniłem to rozważając autobus z nieograniczoną liczbą miejsc oraz obliczając, ile maksymalnie będzie pasażerów w tym samym momencie w takim autobusie. Metoda jest zresztą szczegółowo opisana w moim pierwszym wpisie w tym temacie. Ta metoda jest też efektywna w tym sensie, że można za jej pomocą wyznaczyć (każdy) z optymalnych rozkładów osób wsiadających dla autobusu 20-osobowego. Taką samą metodę zastosował Ameliniowy. Jej inną zaletą jest to, że uogólnia się na inne wielkości autobusu.
ODPOWIEDZ