Zadania przewozowe (ang. river-crossing problems) po raz pierwszy pojawiły się w formie spisanej w dziele średniowiecznego anglosaskiego mnicha Alkuina "Propositiones ad acuendos iuvenes" (problemy dla wyostrzenia umysłu młodzieży) w VIII wieku. Były to trzy słynne zadania (znane do dziś w wielu wariantach) polegające na przeprawieniu przez rzekę wilka, kozy i kapusty, trzech par zazdrosnych braci z siostrami i rodziny z dwójką dzieci.
Możesz spróbować rozwiązać zadanie za pomocą poniższej symulacji. (źródło)
(ur. 730 York, zm. 804 Tours)
Błogosławiony katolicki, mnich anglosaski, uczony, poeta, filozof, pedagog, teolog i teoretyk muzyki, reformator oświaty, wydawca Biblii, autor podręczników siedmiu sztuk wyzwolonych (w tym do arytmetyki, geometrii i astronomii). Jeden z największych umysłów w epoce Karolingów. Sam pobierał nauki w szkole katedralnej w Yorku. Był szeroko wykształcony w zakresie programu trivium (gramatyka, logika, retoryka) i quadrivium (geometria, arytmetyka, astronomia , muzyka) oraz prawa i literatury. Doskonale znał łacinę i grekę.
Od 782 roku na dworze Karola Wielkiego w Akwizgranie kierował Szkołą Pałacową (zwaną na wzór starożytny Akademią), na której wzorowały się późniejsze o 200 lat pierwsze uniwersytety cywilizacji łacińskiej. Był osobistym nauczycielem i doradcą władcy w sprawach nauki i wychowania, a także w sprawach kościelnych i politycznych.
Przeprowadził szeroko zakrojoną reformę szkolną, przywrócił metody nauczania stosowane w Akademii Platońskiej, propagował zastąpienie trudnej w czytaniu majuskuły merowińskiej bardziej czytelną minuskułą karolińską, na wzór której powstały późniejsze czcionki drukarskie.
Alkuin był wybitnym pedagogiem i autorem wielu podręczników. Przyczynił się do rozwoju średniowiecznej metodyki nauczania i stworzył rozmaite mnemotechniki. Widział ścisłe powiązanie etyki i pedagogiki z logiką (zwaną wówczas dialektyką). W swoim dziele "De dialectica" podkreślał ważne funkcje, jakie logika pełni w wychowaniu człowieka światłego, prawego, o erudycyjnej wiedzy. Takie wykształcenie wymaga wyćwiczenia sprawnego umysłu, a to najłatwiej osiągnąć przez rozwiązywanie zagadek i problemów logicznych. Z tego przekonania powstał pierwszy w historii zbiór łamigłówek logicznych "Propositiones ad acuendos iuvenes", którego celem było (jak wskazuje tytuł) wyostrzenie umysłu młodzieńców.
To najstarszy znany zestaw 56 zagadek logicznych (propositiones). Pochodzi z VIII wieku, ale Alkuin spisał w nim prawdopodobnie zadania znane już znacznie wcześniej. Wśród nich są trzy słynne zadania przewozowe.
proposition 17
Trzej zazdrośni bracia i ich trzy siostry muszą przeprawić się przez rzekę za pomocą łódki, która mieści najwyżej dwie osoby. Żadna z kobiet nie może przebywać w towarzystwie innych mężczyzn bez swojego brata. Jak dokonać przeprawy?
proposition 18
Farmer wraca z targu, gdzie kupił wilka, kozę i kapustę. Po drodze musi przemierzyć rzekę. Łódź oprócz farmera może zmieścić tylko jedną rzecz. Oczywiście nie można zostawić kozy i kapusty ani wilka z kozą. W jaki sposób farmer powinien przeprawić się z dobytkiem przez rzekę?
proposition 19
Rodzice z dwójką dzieci muszą przeprawić się przez rzekę. Ojciec i matka ważą tyle samo, a dzieci ważą połowę. Łódka może unieść ciężar jednej osoby dorosłej. W jaki sposób rodzina może przedostać się na drugą stronę rzeki?
Rozwiąż zadania przewozowe Alkuina. W każdym z nich podaj najmniejszą liczbę potrzebnych ruchów (przepłynięć łódką na drugą stronę rzeki). Ile jest możliwie najkrótszych rozwiązań?
Wskazówki
- Rozwiązywanie zadań przewozowych ułatwia odpowiednia notacja. Na przykład każdy stan (na obu brzegach rzeki) zakodujemy podając, kto znajduje się po tej samej stronie rzeki, co łódka.
- Zacznij rozwiązywanie od wypisania wszystkich stanów, które nie są zabronione.
- Połącz linią te stany, w których można przejść bezpośrednio z jednego do drugiego (przez jedno przepłynięcie łódką). Zauważ, że każde takie połączenie "działa w obie strony".
- Jeśli dwa stany są na diagramie połączone ciągiem linii, to można w skończonej liczbie ruchów przejść z jednego z nich do drugiego.
- Jeśli dwa stany łączy droga, o parzystej liczbie linii, to oba są po tej samej stronie rzeki, a jeśli o nieparzystej - to są po przeciwnych stronach.
- Zadanie jest rozwiązane, gdy w otrzymanym diagramie istnieje droga od stanu początkowego do niego samego (pętla) o nieparzystej długości. Dlaczego?
- Wystarczy zatem znaleźć w diagramie dowolną pętlę o nieparzystej długości i połączyć ja drogą (dowolnej długości) ze stanem początkowym. Dlaczego?
- W szczególności wystarczy znaleźć pętlę z jakiegoś stanu do niego samego, o ile stan ten można połączyć ze stanem wyjściowym.
- Z diagramu, w którym zaznaczono wszystkie możliwe połączenia między stanami, można odczytać wszystkie możliwe rozwiązania i wskazać najkrótsze z nich.
Poniżej zamieszczamy diagram przewozowy do zadania o kozie (K), wilku (W) i kapuście (C).
Na podstawie diagramu odpowiedz na pytania:
- W ilu co najmniej ruchach można dokonać przeprawy?
- Ile jest sposobów najkrótszego rozwiązania zadania?
- Które zwierzę jest przewożone najwięcej razy? Ile?
Poniżej zamieszczamy diagram przewozowy do zadania o przeprawie rodziny przez rzekę. W tej wersji rozróżniamy wszystkich członków rodziny (M - mama, T - tato, C - córka, S - syn).
Odpowiedz na pytania:
- Jakiej parzystej długości pętle występują w diagramie?
- Czy są pętle o nieparzystej długości?
- W ilu najmniej ruchach można dokonać przeprawy?
- Ile jest sposobów najkrótszego rozwiązania zadania?
- Ile najmniej razy dzieci muszą płynąć wspólnie?
Ułóż dalsze pytania do tego zadania. Spróbuj wykonać diagram przewozowy w wersji, w której nie rozróżniamy ani rodziców, ani dzieci.
1. Misjonarze i ludożercy. Trzej misjonarze i trzej ludożercy chcą przedostać się na drugą stronę rzeki. Mają do dyspozycji łódź, która może zmieścić tylko dwie osoby. Na jednym brzegu nigdy nie może zostać więcej ludożerców niż misjonarzy. Jak przeprawić wszystkich bezpiecznie na drugą stronę?
Przeprowadź analizę diagramu przewozowego tego zadania.
Odpowiedz na pytania:
- Czy potrafisz wskazać w diagramie pętlę długości parzystej i nieparzystej?
- Ile kroków ma najkrótsze rozwiązanie?
- Ile jest takich rozwiązań?
- Czy trzej misjonarze w najkrótszej przeprawie mogą znaleźć się samotnie na jednym brzegu? A na jednym brzegu razem z łódką?
- Czy można uniknąć sytuacji, gdy dwóch ludożerców płynie razem? A dwóch misjonarzy? A misjonarz z ludożercą?
Ułóż dalsze pytania do tego zadania. Rozwiąż zadanie w wersji, gdy dwóch ludożerców nie ma rąk (kolegów z plemienia dopadł niegdyś kompulsywny głód?), więc tylko jeden z nich może wiosłować.
2. Ludzie i małpy. Troje ludzi, szympans i dwie małe małpy trzeba przeprawić przez rzekę dwuosobową łodzią, według następujących zasad: tylko ludzie i duża małpa mogą wiosłować, liczba ludzi na brzegu musi być większa lub równa liczbie małp.
3. Rodzina, policjant i złodziej. Na drugi brzeg rzeki trzeba przetransportować osiem osób: mamę, ojca, dwóch synów, dwie córki, policjanta i złodzieja, przestrzegając następujących reguł: łódź może przewieźć nie więcej niż dwoje ludzi, tylko dorośli mogą wiosłować, ale nie złodziej, bo ma kajdanki. Tato nie może pozostać w obecności córek bez mamy, a mama w obecności synów bez taty. Złodziej nie może pozostać z członkami rodziny bez policjanta.
4. Małe zoo. Zadanie polega na przeprawieniu dwuosobową łodzią na drugi brzeg rzeki dzikich zwierząt, wśród których są: duży i mały tygrys, duży i mały lew oraz duży i mały niedźwiedź. Uciekają z powodu braku pożywienia i są tak wygłodniali, że w desperacji mogą zjeść siebie nawzajem, dlatego nie wolno pozostawić na brzegu samotnego małego zwierzątka bez dorosłego osobnika tego samego gatunku, bo zostanie zagryzione przez inne zwierzęta. Tylko duże zwierzęta i mały niedźwiadek mogą wiosłować.
5. Wymyśl własne zadania przewozowe.
