Autobus, który mieści dwudziestu pasażerów
-
- 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
Całkiem możliwe. Masz jakiś pomysł, jak naprawić ten mankament? Czy ponumerowanie przystanków wystarczy?
- Slup
- Użytkownik
- Posty: 794
- Rejestracja: 27 maja 2016, o 20:49
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 23 razy
- Pomógł: 156 razy
Autobus, który mieści dwudziestu pasażerów
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.
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.
-
- 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
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}}\)
- 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}}\)
-
- 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
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.
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.
- Slup
- Użytkownik
- Posty: 794
- Rejestracja: 27 maja 2016, o 20:49
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 23 razy
- Pomógł: 156 razy
Re: Autobus, który mieści dwudziestu pasażerów
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.
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.
-
- 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
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
- Slup
- Użytkownik
- Posty: 794
- Rejestracja: 27 maja 2016, o 20:49
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 23 razy
- Pomógł: 156 razy
Re: Autobus, który mieści dwudziestu pasażerów
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.
- kinia7
- 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
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ść
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ść
-
- 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
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:
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ąść.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ść
- Slup
- Użytkownik
- Posty: 794
- Rejestracja: 27 maja 2016, o 20:49
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 23 razy
- Pomógł: 156 razy
Re: Autobus, który mieści dwudziestu pasażerów
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.