Problem z mostkiem i pochodnią
mostu i pochodni (znany również jako Pociąg o północy i Niebezpieczne przejście ) to logiczna łamigłówka , która dotyczy czterech osób, mostu i pochodni . Należy do kategorii łamigłówek związanych z przekraczaniem rzeki , w których pewna liczba obiektów musi poruszać się po rzece, z pewnymi ograniczeniami.
Fabuła
Cztery osoby przychodzą nocą nad rzekę. Jest tam wąski most, ale mogą na nim przebywać tylko dwie osoby na raz. Mają jedną pochodnię, a ponieważ jest noc, trzeba jej używać podczas przechodzenia przez most. Osoba A może przejść przez most w ciągu 1 minuty, B w 2 minuty, C w 5 minut, a D w 8 minut. Kiedy dwie osoby razem przechodzą przez most, muszą poruszać się w tempie osoby wolniejszej. Pytanie brzmi, czy wszyscy mogą przejść przez most, jeśli pochodnia świeci tylko przez 15 minut?
Rozwiązanie
Oczywistym pierwszym pomysłem jest to, że koszt zwrotu pochodni osobom czekającym na przejście jest nieuniknionym wydatkiem, który należy zminimalizować. Ta strategia sprawia, że A jest nosicielem pochodni, przewożącym każdą osobę przez most:
| Czas, który upłynął | Strona startowa | Działanie | Końcowa strona |
|---|---|---|---|
| 0 minut | ABCD | ||
| 2 minuty | płyta CD | A i B krzyżują się do przodu, co zajmuje 2 minuty | AB |
| 3 minuty | Płyta CD | A powraca, co zajmuje 1 minutę | B |
| 8 minut | D | A i C krzyżują się do przodu, co zajmuje 5 minut | ABC |
| 9 minut | A D | A powraca, co zajmuje 1 minutę | pne |
| 17 minut | A i D krzyżują się do przodu, co zajmuje 8 minut | ABCD |
Ta strategia nie pozwala na przejście w 15 minut. Aby znaleźć właściwe rozwiązanie, należy zdać sobie sprawę, że zmuszanie dwóch najwolniejszych osób do przejścia pojedynczo to strata czasu, który można zaoszczędzić, jeśli oboje przejdą razem:
| Czas, który upłynął | Strona startowa | Działanie | Końcowa strona |
|---|---|---|---|
| 0 minut | ABCD | ||
| 2 minuty | płyta CD | A i B krzyżują się do przodu, co zajmuje 2 minuty | AB |
| 3 minuty | Płyta CD | A powraca, co zajmuje 1 minutę | B |
| 11 minut | A | C i D krzyżują się do przodu, co zajmuje 8 minut | BCD |
| 13 minut | AB | B powraca, co zajmuje 2 minuty | płyta CD |
| 15 minut | A i B krzyżują się do przodu, co zajmuje 2 minuty | ABCD |
Drugie równoważne rozwiązanie zamienia podróże powrotne. Zasadniczo dwie najszybsze osoby krzyżują się podczas pierwszej i piątej podróży, dwie najwolniejsze osoby krzyżują się podczas trzeciej podróży, a KAŻDA z najszybszych osób wraca podczas drugiej podróży, a druga najszybsza osoba wraca podczas czwartej podróży.
Tak więc minimalny czas dla czterech osób jest określony następującymi równaniami matematycznymi: Kiedy ,
Podejście półformalne
Załóżmy, że rozwiązanie minimalizuje całkowitą liczbę skrzyżowań. Daje to w sumie pięć skrzyżowań - trzy skrzyżowania par i dwa przejścia solo. Załóżmy również, że zawsze wybieramy najszybszego do krzyżowania solo. Najpierw pokazujemy, że jeśli dwie najwolniejsze osoby (C i D) przejdą osobno, łączny czas przejścia wynosi 15. Dokonuje się tego, biorąc osoby A, C i D: C+A+D+A = 5+ 1+8+1=15. (Tutaj używamy A, ponieważ wiemy, że użycie A do osobnego przekroczenia zarówno C, jak i D jest najbardziej efektywne.) Jednak czas upłynął, a osoby A i B nadal znajdują się po początkowej stronie mostu i muszą przejść. Nie jest więc możliwe, aby dwa najwolniejsze (C i D) przecinały się oddzielnie. Po drugie, pokazujemy, że aby C i D mogły się skrzyżować, muszą się skrzyżować na drugiej parze: tzn. nie C i D, więc A i B muszą się najpierw skrzyżować. Przypomnijmy sobie nasze początkowe założenie, że powinniśmy zminimalizować skrzyżowania i tak mamy pięć skrzyżowań - 3 skrzyżowania parami i 2 skrzyżowania pojedyncze. Załóżmy, że C i D przecinają się jako pierwsze. Ale wtedy C lub D musi przejść z powrotem, aby przenieść pochodnię na drugą stronę, więc każdy, kto przeszedł samotnie, musi przejść ponownie. Dlatego przejdą osobno. Ponadto niemożliwe jest, aby przeszli razem jako ostatni, ponieważ oznacza to, że jeden z nich musiał przejść wcześniej, w przeciwnym razie po stronie startowej byłyby łącznie trzy osoby. Tak więc, ponieważ są tylko trzy możliwości krzyżowania par, a C i D nie mogą krzyżować się jako pierwsze ani ostatnie, muszą krzyżować się razem podczas drugiego lub środkowego krzyżowania par. Łącząc to wszystko razem, A i B muszą najpierw się skrzyżować, ponieważ wiemy, że C i D nie mogą i minimalizujemy skrzyżowania. Następnie A musi się przeciąć jako następne, ponieważ zakładamy, że powinniśmy wybrać najszybszego, który wykona samodzielną krzyżówkę. Następnie jesteśmy na drugim lub środkowym skrzyżowaniu par, więc C i D muszą odejść. Następnie decydujemy się odesłać najszybszego z powrotem, czyli B. A i B są teraz po stronie startowej i muszą krzyżować się w celu ostatniego skrzyżowania par. To daje nam B+A+D+B+B = 2+1+8+2+2 = 15.
Odmiany i historia
Istnieje kilka odmian, z kosmetycznymi różnicami, takimi jak ludzie o różnych nazwach lub różnice w czasach przekraczania lub limicie czasowym. Sama pochodnia może wygasnąć w krótkim czasie i służyć jako limit czasu. [ potrzebne dalsze wyjaśnienia ] Na przykład w odmianie zwanej The Midnight Train osoba D potrzebuje 10 minut zamiast 8, aby przejść przez most, a osoby A, B, C i D, zwane teraz czterema braćmi Gabrianni, mają 17 minut na przejście przez most złapać pociąg o północy.
Wiadomo, że łamigłówka pojawiła się już w 1981 roku w książce Super Strategies For Puzzles and Games . W tej wersji łamigłówki przejście A, B, C i D zajmuje odpowiednio 5, 10, 20 i 25 minut, a limit czasu wynosi 60 minut. We wszystkich tych odmianach struktura i rozwiązanie zagadki pozostają takie same.
W przypadku, gdy istnieje dowolna liczba osób z dowolnymi czasami przejazdu, a przepustowość mostu pozostaje równa dwóm osobom, problem został całkowicie przeanalizowany metodami grafowo- teoretycznymi .
Martin Erwig z Oregon State University wykorzystał odmianę tego problemu, aby argumentować za przydatnością języka programowania Haskell zamiast Prologu do rozwiązywania problemów z wyszukiwaniem .
Zagadka jest również wspomniana w książce Daniela Dennetta From Bacteria to Bach and Back jako jego ulubiony przykład rozwiązania sprzecznego z intuicją.
Zobacz też
Linki zewnętrzne
- Slajdy problemu z palnikiem C [1]
- Artykuł omawiający problem palnika o pojemności C [2]
- Film i ćwiczenia Teda Eda oparte na problemie z mostem i pochodnią [3]
- Artykuł omawiający systematyczne rozwiązanie zagadki mostu przy użyciu kombinatoryki [4]