Zbiór zadań, (zadania różne)
Zadanie 134
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ą zjedzeni. Czy cała szóstka może się bezpiecznie przeprawić na drugi brzeg?
Rozwiązanie
Rozważmy wszystkie możliwe stany liczebności misjonarzy i kanibali na
tym brzegu, z którego wyrusza wyprawa. Oznaczmy przez m liczbę
misjonarzy, a przez k - liczbę kanibali. Możliwe wartości m i k to 0, 1,
2, 3, więc łącznie mamy 4 na 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 m i k
są różnymi liczbami niezerowymi. Zostaje dziesięć stanów dopuszczalnych.
Metodą prób i błędów dość szybko odkryjemy, że są cztery układy,
które prowadzą do rozwiązania łamigłówki.
Przewiezienie całej szóstki przez rzekę wymaga
jedenastu kursów łódki.
Oto jedno z rozwiązań:
brzeg lewy: L(k, m)
brzeg prawy: P(k, m)
→ przeprawa z lewego na prawy brzeg
← przeprawa z prawego na lewy brzeg
Stan początkowy: L(3,3) - P(0,0)
1. Łódka → (1, 1): Stan: L(2, 2) - P(1, 1)
2. Łódka ← (0, 1): Stan: L(2, 3) - P(1, 0)
3. Łódka → (2, 0): Stan: L(0, 3) - P(3, 0)
4. Łódka ← (1, 0): Stan: L(1, 3) - P(2, 0)
5. Łódka → (0, 2): Stan: L(1, 1) - P(2, 2)
6. Łódka ← (1, 1): Stan: L(2, 2) - P(1, 1)
7. Łódka → (0, 2): Stan: L(2, 0) - P(1, 3)
8. Łódka ← (1, 0): Stan: L(3, 0) - P(0, 3)
9. Łódka → (2, 0): Stan: L(1, 0) - P(2, 3)
10. Łódka ← (0, 1): Stan: L(1, 1) - P(2, 2)
11. Łódka → (1, 1): Stan: L(0, 0) - P(3, 3)
I tak oto cała szóstka cało dotarła na drugi brzeg rzeki.
Pozostałe trzy rozwiązania niech będą rozrywką dla czytelnika.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>