sobota 26 września 2020 imieniny Cypriana i Justyny 1888 - Urodził się Thomas Stearns Eliot
Do końca roku pozostało: 0 dni
Matematyka
Interaktywna mapa szkół
Język polski Historia WOS Sztuka (plastyka i muzyka) Języki obce Religia i etyka
Matematyka Fizyka i astronomia Chemia Biologia Przyroda Geografia Technika Informatyka
Przedmioty zawodowe WF Ścieżki edukacyjne Wychowanie przedszkolne Nauczanie zintegrowane Więcej
Przeprawy

Jeszcze o kanibalach i misjonarzach

Zapytajmy teraz, czy w podobnych warunkach, dysponując dwuosobową łódką, przez rzekę może się przeprawić czterech kanibali i czterech misjonarzy. Odpowiedź tym razem jest przecząca: bezpiecznej przeprawy nie ma. Spróbujmy się przekonać o prawdziwości tego twierdzenia.

Jak poprzednio, zaznaczmy kropkami w układzie współrzędnych dopuszczalne stany liczebności kanibali i misjonarzy na jednym z brzegów rzeki (rysunek 3).

Przypuśćmy, że przeprawa jednak jest możliwa. Rozważmy przeprawę, która wymaga najmniejszej liczby kursów łódki przez rzekę i wyobraźmy sobie układ strzałek odpowiadający takiej przeprawie. Przypatrzmy się bliżej pierwszej strzałce, która kończy się w jednej z kropek oznaczonych kolorem (tzn. rozważmy pierwszy moment, gdy wszyscy misjonarze znaleźli się na drugim brzegu rzeki).

Nietrudno stwierdzić, że musiałaby to być jedna z trzech strzałek zaznaczonych na rysunku 4. Gdyby była to strzałka S1, łącząca punkty (1,1) i (0, 0), to poprzednia strzałka musiałaby mieć początek w punkcie (1, 0). Wtedy jednak na linii kolorowych kropek musielibyśmy znaleźć się po raz pierwszy już wcześniej - mamy więc sprzeczność. Gdyby pierwszą strzałkę, kończącą się w kolorowym punkcie, była strzałka S2, to wówczas zamiast niej moglibyśmy równie dobrze narysować strzałkę Sl i od razu zakończyć przeprawę, zmniejszając liczbę kursów łódki. Znów mamy sprzeczność, bo rozważana przeprawa miała być najkrótsza.


Gdyby wreszcie pierwsza strzałką z kolorowym końcem była strzałka S3, to poprzednie dwa kursy łódki musiałyby odpowiadać strzałkom, które na rysunku 5 są zaznaczone kolorem. Wtedy jednak obie kolorowe strzałki, tworzące zamkniętą pętelkę, moglibyśmy z zaplanowanego schematu przeprawy usunąć i zmniejszyć liczbę kursów łódki o 2, co kłóci się z tym, że rozważamy przeprawę najkrótszą z możliwych. Po raz trzeci trafiliśmy więc na sprzeczność, a to oznacza, że najkrótsza bezpieczna przeprawa nie istnieje. Nie istnieje więc żadna bezpieczna przeprawa.

Czy jest na to rada? Okazuje się, że tak. Trzeba zwiększyć łódkę. Jeśli łódka może pomieścić trzech pasażerów i przyjmiemy, że ani w łódce, ani na brzegu kanibale nie mog~ przewyższyć liczebności misjonarzy, to cała ósemka zdoła się bezpiecznie przeprawić (rysunek 6).

Pięciu kanibali i pięciu misjonarzy również może się bezpiecznie przeprawić, dysponując łódką, która mieści trzech pasażerów, lecz sześciu kanibali i sześciu misjonarzy - nie może. Wskazanie rozwiązania w pierwszym przypadku i uzasadnienie, że w drugim przypadku bezpiecznej przeprawy nie ma, pozostawiamy Czytelnikowi.

Żeby bezpiecznie przewieźć przez rzekę sześciu kanibali i sześciu misjonarzy, trzeba mieć łódkę czteroosobową. I nie ma już co rozważać większych wycieczek: dowolna grupa złożona z jednakowej liczby kanibali i misjonarzy może się bezpiecznie przeprawić przez rzekę za pomocą łódki, która mieści czterech lub więcej pasażerów. Musimy po prostu wybrać jednego kanibala i jednego misjonarza, którzy zasiądą przy wiosłach, spluną w dłonie i będą przewozić całą resztę parami - za każdym razem jednego kanibala i jednego misjonarza - tak długo, aż cel zostanie osiągnięty.





Autor: Paweł STRZELECKI
Komentarze + Dodaj komentarz
Zapraszamy do wyrażania opinii, redakcja portalu Interklasa.
 
Nasi partnerzy:
MEN SchoolNet eTwinning Związek Powiatów Polskich PCSS
Cisco OFEK Przyjazna Szkoła Fundacja Junior FIO CEO
Parafiada net PR Orange IMAX Cinema City WSP TWP
IMAGE PPI-ETC ArcaVir Master Solution Device


Projekt Polski Portal Edukacyjny Interkl@sa
powstał i był realizowany w latach 2000-2011 dzięki wsparciu
Polsko-Amerykańskiej Fundacji Wolności.

W ramach naszej witryny stosujemy pliki cookies w celu świadczenia Państwu usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Państwa urządzeniu końcowym. Możecie Państwo dokonać w każdym czasie zmiany ustawień dotyczących cookies. Więcej szczegółów w naszej "Polityce Prywatności".


Pytania i uwagi: portal@interklasa.pl

Regulamin portalu /  Polityka prywatności /  Ochrona własności intelektualnej /  Zasady korzystania / 
Wyłączenie odpowiedzialności /  Biuro prasowe /  Zasady współpracy /  Redakcja /  Kontakt

Przejdź na stronę ucznia Przejdź na stronę nauczyciela Przejdź na stronę rodzica Certyfikat sieciaki.pl Przyjazna strona kidprotect.pl