Lähetyssaarnaajien ja kannibaalien ongelma

Lähetyssaarnaajien ja kannibaalien tai kannibaalien ja lähetyssaarnaajien ongelma on klassinen joen ylitysongelma. Siihen liittyy läheisesti mustasukkaisten aviomiesten ongelma , joka on myös ritarien ja oraajien ongelma .

Formulaatiot

• Ongelma lähetyssaarnaajista ja kannibaaleista. Kolmen lähetyssaarnaajan ja kolmen kannibaalin on ylitettävä joki veneessä, johon mahtuu enintään kaksi henkilöä. Samaan aikaan kannibaaleja enemmän kuin lähetyssaarnaajia ei voi jäädä toiselle puolelle (muuten lähetyssaarnaajat syödään). Vene ei myöskään voi ylittää jokea ilman ihmisiä.

Monimutkaisempi vaihtoehto:

• Ongelma mustasukkaisista miehistä. Kolmen avioparin on ylitettävä joki veneellä samoin edellytyksin ja sillä rajoituksella, että yksikään vaimo ei saa olla ilman miestä toisen miehen läsnä ollessa.

Huomaa, että yhdessä pankissa ei voi olla enempää naisia ​​kuin miehiä. Siten korvaamalla miehet lähetyssaarnaajilla ja naiset kannibaaleilla mistä tahansa ratkaisusta mustasukkaisten aviomiesten ongelmaan tulee ratkaisu myös lähetyssaarnaajien ja kannibaalien ongelmaan.

Viimeinen tehtävä tunnetaan myös ritareita ja orjia koskevassa sanamuodossa - orava ritarinsa poissa ollessa loukkaantuu toisista ritareista.

Historia

Ensimmäinen tunnettu maininta mustasukkaisista aviomiehistä muunnelmassa on keskiaikaisessa tekstissä Propositiones ad Acuendos Juvenes , joka johtuu Alcuinista , joka kuoli vuonna 804. Tässä koostumuksessa on kolme sisarusparia, mutta rajoittava tekijä on silti sama: kukaan nainen ei voi olla toisen miehen seurassa ilman veljeään. Sama teksti sisältää suden, vuohen ja kaalin ongelman .

1200-1400-luvuilla tehtävästä tuli kuuluisa koko Pohjois-Euroopassa, kun aviomiehet ja vaimot olivat jo muotoilussa. Myöhemmässä muotoilussa esiintyy kolme paria herroja ja palvelijoita tai ritareita ja orjia. Yksinkertaistettu versio, jossa on lähetyssaarnaajia ja kannibaaleja, ilmestyy 1800-luvun lopulla.

Muunnelmia

Ilmeinen yleistys on muutos mustasukkaisten parien lukumäärässä, laivan kapasiteetissa tai molemmissa.

• Jos veneeseen mahtuu kaksi henkilöä, niin
  • kaksi paria vaativat viisi matkaa,
  • neljän tai useamman parin kohdalla ongelmalla ei ole ratkaisua.

• Jos veneeseen mahtuu kolme, voidaan kuljettaa jopa 5 paria.

• Jos veneeseen mahtuu neljä henkilöä, niin pareja voidaan kuljettaa mikä tahansa määrä.

• Jos saari lisätään joen keskelle, niin monta paria voi ylittää joen kaksipaikkaisella veneellä.

Katso myös

• Susi, vuohi ja kaali