Zagadka przeprawy przez rzekę
Puzzle z przeprawą przez rzekę to rodzaj układanki, w której celem jest przenoszenie przedmiotów z jednego brzegu rzeki na drugi, zwykle w jak najmniejszej liczbie wycieczek. Trudność łamigłówki może wynikać z ograniczeń, jakie lub ile przedmiotów można przewieźć jednocześnie lub które lub ile przedmiotów można bezpiecznie pozostawić razem. Oprawa może różnić się kosmetycznie, na przykład poprzez zastąpienie rzeki mostem. Najwcześniejsze znane problemy z przeprawą przez rzekę pojawiają się w rękopisie Propositiones ad Acuendos Juvenes (angielski: Problemy z wyostrzeniem młodych ), tradycyjnie uważanym za napisany przez Alkuin . Najstarsze kopie tego rękopisu pochodzą z IX wieku; zawiera trzy problemy z przeprawą przez rzekę, w tym zagadkę z lisem, gęsią i workiem fasoli oraz problem zazdrosnego męża .
Do znanych zagadek związanych z przeprawą przez rzekę należą:
- Układanka z lisem, gęsią i workiem fasoli , w której rolnik musi przetransportować lisa, gęś i worek fasoli z jednego brzegu rzeki na drugi za pomocą łodzi, która może pomieścić tylko jeden przedmiot oprócz rolnika, pod warunkiem że ograniczenia, zgodnie z którymi lisa nie można zostawić samego z gęsią, a gęsi nie można zostawić samego z fasolą. Stwierdzono również równoważne łamigłówki z udziałem lisa, kurczaka i worka zboża lub wilka , kozy i kapusty itp.
- Problem zazdrosnych mężów , w którym trzy pary małżeńskie muszą przeprawić się przez rzekę łodzią mogącą pomieścić co najwyżej dwie osoby, pod warunkiem, że żadna kobieta nie może przebywać w obecności innego mężczyzny, jeśli nie jest obecny także jej mąż. Przypomina to problem misjonarzy i kanibali , w którym trzech misjonarzy i trzech kanibali musi przeprawić się przez rzekę, z zastrzeżeniem, że w dowolnym momencie, gdy zarówno misjonarze, jak i kanibale stoją na którymkolwiek brzegu, liczba kanibali na tym brzegu nie może przewyższać liczebnie misjonarzy .
- mostu i latarki .
- Propositio de viro et muliere ponderantibus plaustrum . W tym problemie, występującym także w Propositiones ad Acuendos Juvenes , mężczyzna i kobieta o jednakowej wadze oraz dwójka dzieci, każde o połowie masy ciała, chcą przeprawić się przez rzekę łodzią, która może unieść ciężar tylko jednej osoby dorosłej.
Problemy te można analizować za pomocą metod teorii grafów , programowania dynamicznego lub programowania liczb całkowitych .