Delta
  Wiw.pl   Na bieżąco:  Informacje   Co nowego   Matematyka i przyroda:  Astronomia   Biologia   Fizyka   Matematyka   Modelowanie rzeczywistości   Humanistyka:  Filozofia   Historia   Kultura antyczna   Literatura   Sztuka   Czytaj:  Biblioteka   Delta   Wielcy i więksi   Przydatne:  Słowniki   Co i gdzie studiować   Wszechświat w obrazkach    
  Jesteś tutaj:  Wirtualny Wszechświat > Delta > Matematyka - spis artykułów >  PRZEPRAWY  
  Jesteś tutaj
Wybór artykułów z miesięcznika "Delta"
"Delta" to miesięcznik popularyzujący matematykę, fizykę i astronomię na bardzo wysokim poziomie, wydawany od 1974 roku.
Wirtualny Wszechświat prezentuje wybór tekstów publikowanych w "Delcie" od pierwszego numeru po początek XXI wieku.
  Szukacz
Delta 07/1999
Paweł STRZELECKI
PRZEPRAWY

Wiele starych łamigłówek ma za temat różne przeprawy przez rzekę. Chyba najsłynniejszą z nich jest - pochodzące z ósmego wieku - zadanie mnicha Alkuina: należy przewieźć na drugi brzeg rzeki wilka, kozę i kapustę łodzią, w której (oprócz wiosłującego) mieści się tylko jedno z nich; nie można przy tym zostawić wilka sam na sam z kozą ani kozy sam na sam z kapustą.

Przyjemność rozwiązania zadania Alkuina pozostawimy tym Czytelnikom, którzy go wcześniej nie znali, a sami zajmiemy się inną - również nieźle znaną - łamigłówką: o kanibalach i misjonarzach.

Sytuacja jest następująca: trzej misjonarze i trzej kanibale chcą przeprawić się na drugi brzeg rzeki. Mają łódkę, która za jednym razem może przewieźć najwyżej dwie osoby. Jeśli w pewnym momencie na którymkolwiek brzegu rzeki kanibali będzie więcej od misjonarzy, to misjonarze zostaną zabici i zjedzeni. Czy cała szóstka może się bezpiecznie przeprawić na drugi brzeg?

Rozważmy wszystkie możliwe stany liczebności misjonarzy i kanibali na tym brzegu, z którego wyrusza wyprawa. (Każdemu takiemu stanowi odpowiadają - jednoznacznie wyznaczone! - liczba kanibali i liczba misjonarzy na drugim brzegu, więc nie musimy oddzielnie rozważać, co dzieje się u celu przeprawy). Oznaczmy przez m liczbę misjonarzy, a przez k - liczbę kanibali. Możliwe wartości mk to 0, 1, 2, 3, więc łącznie mamy 4 x 4 = 16 różnych stanów. Trzeba jednak wykluczyć stany, odpowiadające sytuacjom, w których na jednym z brzegów rzeki kanibali jest więcej od misjonarzy, a więc stany, w których mk są różnymi liczbami niezerowymi. Zostaje dziesięć stanów dopuszczalnych; każdy z nich jest na rysunku 1 oznaczony kropką w układzie współrzędnych.

Rys. 1

Zamiast planować przeprawę, będziemy łączyć kropki strzałkami. Każda strzałka odpowiada jednemu kursowi łódki przez rzekę. Zaczynamy od prawego górnego rogu (m = 3, k = 3). Każda strzałka musi obrazować przewiezienie jednej lub dwóch osób przez rzekę. Trzeba też pamiętać, że po każdej strzałce skierowanej w lewo lub w dół musi następować strzałka w prawo lub w górę (czyli powrót łódki z drugiego brzegu).

Metodą prób i błędów dość szybko odkryjemy, że są cztery układy strzałek, które prowadzą do rozwiązania łamigłówki. Jedno z rozwiązań przedstawia rysunek 2. Przewiezienie całej szóstki przez rzekę wymaga jedenastu kursów łódki. Pozostałe trzy rozwiązania Czytelnik z łatwością narysuje sam.

Rys. 2

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).

Rys. 3

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ę S1 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.

Rys. 4

Gdyby wreszcie pierwszą 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.

Rys. 5

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).

Rys. 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.




[góra strony]
Wiw.pl  |  Na bieżąco  |  Informacje  |  Co nowego  |  Matematyka i przyroda  |  Astronomia  |  Biologia  |  Fizyka  |  Matematyka  |  Modelowanie rzeczywistości  |  Humanistyka  |  Filozofia  |  Historia  |  Kultura antyczna  |  Literatura  |  Sztuka  |  Czytaj  |  Biblioteka  |  Delta  |  Wielcy i więksi  |  Przydatne  |  Słowniki  |  Co i gdzie studiować  |  Wszechświat w obrazkach