Problema misionarilor și canibalilor

Problema misionarilor și canibalilor, sau canibalilor și misionarilor , este o problemă clasică de trecere a râului. Strâns legată de aceasta este problema soţilor geloşi , care este şi problema cavalerilor şi scutierilor .

Formulări

• Problemă despre misionari și canibali. Trei misionari și trei canibali trebuie să traverseze râul într-o barcă care nu poate transporta mai mult de doi oameni. În același timp, mai mulți canibali decât misionari nu pot rămâne pe o parte (altfel misionarii vor fi mâncați). De asemenea, barca nu poate traversa râul fără oameni la bord.

Opțiune mai complexă:

• Problemă cu soții geloși. Trei cupluri căsătorite trebuie să treacă râul cu o barcă în aceleași condiții și cu restricția că niciuna dintre soții nu poate rămâne fără soț în prezența altui bărbat.

Rețineți că nu pot fi mai multe femei pe o bancă decât bărbați. Astfel, prin înlocuirea bărbaților cu misionari și a femeilor cu canibali, orice soluție la problema soților geloși va deveni și o soluție la problema misionarilor și canibalilor.

Ultima sarcină este cunoscută și în formularea despre cavaleri și scutieri - un scutier în absența cavalerului său este jignit de alți cavaleri.

Istorie

Prima mențiune cunoscută a soților geloși într-o variantă este în textul medieval Propositiones ad Acuendos Juvenes , atribuit lui Alcuin , care a murit în 804. Există trei perechi de frați în această formulare, dar factorul limitativ rămâne același: nicio femeie nu poate fi în compania altui bărbat fără fratele ei. Același text conține problema despre lup, capră și varză .

Din secolele al XIII-lea până în secolele al XV-lea, sarcina a devenit faimoasă în toată Europa de Nord, având deja soți și soții în formulare. Într-o formulare ulterioară, apar trei perechi de stăpâni și servitori sau cavaleri și scutieri. O versiune simplificată cu misionari și canibali apare la sfârșitul secolului al XIX-lea.

Variante

O generalizare evidentă este o modificare a numărului de cupluri geloase, a capacității navei sau a ambelor.

• Dacă barca poate găzdui două persoane, atunci
  • două perechi necesită cinci călătorii,
  • pentru patru sau mai multe perechi, problema nu are soluție.

• Dacă barca poate găzdui trei, atunci pot fi transportate până la 5 perechi.

• Dacă barca poate transporta patru persoane, atunci orice număr de cupluri poate fi transportat.

• Dacă se adaugă o insulă în mijlocul râului, atunci orice număr de cupluri pot traversa râul într-o barcă cu două locuri.

Vezi și

• Lup, capră și varză