Pregunta de entrevista de Tyler Technologies
three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board. Move all missionaries and cannibals from one river bank to the other.
Respuestas de entrevistas
That is an incorrect answer. The boat can not hold more than 2.
1M + 1C take the boat and leave 1C on the other side.
1M (left in the boat) goes back and takes 1C. They cross and 1M stays on the other side.
1C (left in the boat) goes back and takes 1M and drops him off on the other side.
1C (left in the boat) goes back and takes the last 1M and drops him off on the other side.
1C (left in the boat) goes back and takes the last 1C and cross the river.
The correct answer to this question is a bit more complicated than the ones currently posted. DeerJohn's answer fails to solve the problem because it violates the constraints of the boat. Henry's answer unfortunately leaves us with a situation where 1 Missionary and 1 Cannibal are in a boat together headed to the opposite shore where 1 cannibal is already waiting. Thus when they arrive the two cannibals eat the outnumbered missionary in the boat. The boat does not provide any sort of invincibility or defense.
To correctly solve this problem it will take 11 total trips from bank to bank.
I'll try and diagram it below, A trip will be defined as any attempt to cross the river.
START:
BANK1: mmm ccc | BOAT: | BANK2:
TRIP1(crossing):
BANK1: mm cc | BOAT: mc | BANK2:
TRIP2(returning):
BANK1: mm cc | BOAT: m | BANK2: c
TRIP3(crossing):
BANK1: mmm | BOAT: cc | BANK2: c
TRIP4(returning):
BANK1: mmm | BOAT: c | BANK2: cc
TRIP5(crossing):
BANK1: m c | BOAT: mm | BANK2: cc
TRIP6(returning):
BANK1: m c | BOAT: mc | BANK2: m c
TRIP7(crossing):
BANK1: cc | BOAT: mm | BANK2: m c
TRIP8(returning):
BANK1: cc | BOAT: c | BANK2: mmm
TRIP9(crossing):
BANK1: c | BOAT: cc | BANK2: mmm
TRIP10(returning):
BANK1: c | BOAT: c | BANK2: mmm c
TRIP11(crossing):
BANK1: | BOAT: cc | BANK2: mmm c
END:
BANK1: | BOAT: | BANK2: mmm ccc
All 3 missionaries should go across, leaving two on the opposite bank. One missionary returns to retrieve 2 cannibals, leaving then with the two missionaries already on the opposite bank, then returns for the last cannibal.