EDIT: This puzzle originates from the "International Mathematics Tournament of the Towns", and was published in the book "S.M.A.R.T circle overview" by Professor Andy Liu. The author has (albeit a little retroactively) granted us the permission to use the puzzle.
Ten thieves, ranked A to J, are trying to cross a river in a boat requiring two rowers. Unfortunately, if the ranks of any two in the boat differ by more than 1, those two will refuse to stay in the boat. This constraint means they can’t get across the river. Their leader, with a rank of A, asks Ali Baba for help and Ali Baba replies, “If you give me a rank of A, equal to yours, we can all cross the river.” The leader agrees.
How many one-way crossings are the least required to get Ali Baba and the 10 thieves across the river?
NOTE:
More than 2 people can accumulate in the boat. Boat is operated by 2 rowers. So a single person cannot row it on his own.
Answer
Here’s my quadruple-checked, optimality-guaranteed solution with
33 crossings.
(Glorfindel’s initial answer had the same crossing count earlier, but UselessInfoMine discovered an error in that method. The updated version of that method works, but uses 4 crossings more than the optimal method.)
You can get any 2 consecutive thieves over like this
+Aab, -ab, +bc, -Ab, +Aab, -bc, +XY, -Aa (8 moves)
Repeat four times, always bringing the two lowest ranked thieves over. Bring the rest over with the final move.
If there’s a quicker way to do it, it must be Very Clever Indeed, since
The only move that adds a thief on the opposite shore is the +Aab, which cannot happen more often than every fourth move. (Barring the silly -Aab waste of move, of course.)
Given that the final +Aab will bring 3 guys, a total of 9 +Aab’s are required, and in between them, there will have to be at minimum 8x3 other crossings. This sums up to a minimum of 33 moves.
Therefore, barring lateral thinking and other trick answers, this solution is optimal.
No comments:
Post a Comment