20
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ There is a need to have 2 rowers to move the boat ? Or can it be moved by only one ? $\endgroup$
    – Sanea
    Commented Dec 29, 2017 at 13:44
  • 3
    $\begingroup$ Is there some lateral-thinking ? I can't think how H-I-J can be on the same boat whatsoever $\endgroup$
    – Sanea
    Commented Dec 29, 2017 at 13:57
  • 3
    $\begingroup$ I have the feeling that there may be also some Hanoï tower problem variant in here... $\endgroup$
    – Keelhaul
    Commented Dec 29, 2017 at 14:14
  • 7
    $\begingroup$ How very clever of Ali Baba. By symmetry, rank of J would have worked just as well. $\endgroup$
    – Bass
    Commented Dec 29, 2017 at 14:22
  • 1
    $\begingroup$ @Bass any rank works but some works better then others, for example if Ali baba would be ranked as E, the answer was going to be shorter. Since he can both travel with D , E and F, instead of just A and B. $\endgroup$
    – ifyalciner
    Commented Dec 30, 2017 at 0:30

7 Answers 7

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ This is the right answer,. But I have 2 questions: How do you guarantee optimality? And if you are sure that this is optimal, why do you say that "if there is a quicker way,... it must be very clever". If this is optimal shouldn't there be no shorter way? $\endgroup$
    – ifyalciner
    Commented Dec 30, 2017 at 0:40
  • $\begingroup$ @ifyalciner, I added the remaining two sentences to the optimality proof. I thought they were self-evident, but of course I failed to appreciate the fact that anyone reading the answer probably didn’t just spend a couple of hours on this puzzle. Should be clearer now. $\endgroup$
    – Bass
    Commented Dec 30, 2017 at 0:57
12
$\begingroup$

Here is a solution with

37 crossings.

Explanation:

AAB, AB return
BC, AB return
C has now crossed.
AAB, BC return
CD, AA return
AAB, AA return
BCD have now crossed.
EF, BC return
AAB, AB return
BC, AB return
CDEF have now crossed, after 16 crossings.

GH, CD return
IJ, EF return
GHIJ have now crossed.

Repeat the procedure in the first block.
CDEFGHIJ have now crossed, after 2x16 + 4 = 36 crossings.
The final crossing is by AAB.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @Bass when I started working on a solution, I counted two-way crossings. I had to edit my original solution and was still counting that way. But now it's correct (I think). $\endgroup$
    – Glorfindel
    Commented Dec 29, 2017 at 18:00
  • $\begingroup$ I finally spotted the reason you upped the move count. Pesky B jumping over the river, confusing honest people like that. Kind of interesting that the error resulted in exactly the optimal (by my reasoning, at least) crossing count though. $\endgroup$
    – Bass
    Commented Dec 29, 2017 at 19:13
  • 1
    $\begingroup$ This seems to be turning into a rather interesting social experiment: as of late, this answer has been getting more upvotes than the correct one right below it. Someone even bruteforced the problem and posted the same solution without looking at any of the other answers than the highest voted one. $\endgroup$
    – Bass
    Commented Dec 30, 2017 at 12:54
  • $\begingroup$ @Bass it's some kind of FGITW. I agree your answer is better but there's not much I can do about it. $\endgroup$
    – Glorfindel
    Commented Dec 30, 2017 at 18:02
  • $\begingroup$ Oh, there’s even an acronym for that effect, I thought I was on to something new and interesting. :-) $\endgroup$
    – Bass
    Commented Dec 30, 2017 at 18:59
7
$\begingroup$

UPDATE: UselessInfoMine noticed that Glorfindel’s seemingly optimal solution didn’t actually work. Here’s a working version with the same crossing count.

—————

Glorfindel’s approach seems good. Here’s a lateral-thinking solution within the established parameters of the story. First, observe that

1. The leader can change Ali Baba’s rank at will.
2. The other thieves will accept Ali’s new rank, no matter high Ali is promoted.

Abusing those observations,

give Ali Baba a new rank for each crossing. Each trip over the river will take 2 thieves+Ali, the other thief will return with Ali.

This allows everybody to cross in mere

17 crossings. Each round-trip deposits a thief on the other shore. After 8 round trips, there are only two thieves left, so everyone fits on the boat.

Improve this answer
$\endgroup$
6
  • $\begingroup$ If you really want to abuse those observations, why would they apply just to Ali Baba, and not to the rest of the thieves? $\endgroup$
    – Acccumulation
    Commented Dec 29, 2017 at 16:29
  • 2
    $\begingroup$ @Acccumulation, well, sure, but it wasn’t established in the flavour story that the leader can give new ranks to the other thieves. $\endgroup$
    – Bass
    Commented Dec 29, 2017 at 16:37
  • 1
    $\begingroup$ If you are going to Loophole Abuse with "lateral thinking", you might as well take it Up To Eleven and finish it off in one crossing: Alibaba and the leader beat up all the other thieves one by one, tie them up with a big rope and throw them on the boat, or even "better" Alibaba and the leader kill all the other thieves ... because the puzzle doesn't state that the thieves have to make it alive across the river. $\endgroup$
    – Masked Man
    Commented Dec 30, 2017 at 12:07
  • 1
    $\begingroup$ @maskedman, I’d like to think there’s a marked difference between (ab)using the elements that are already established as being possible within the story, and inventing a boat long enough to serve as a bridge. $\endgroup$
    – Bass
    Commented Dec 30, 2017 at 16:21
  • 2
    $\begingroup$ @maskedman, I’m not absolutely certain which universe I’m from, either, but I’m pretty sure it isn’t the one that has Ali Baba in it. $\endgroup$
    – Bass
    Commented Dec 31, 2017 at 15:30
2
$\begingroup$

I make it

57 - and I think @Glorfindel has managed to leave B on the wrong bank in his first block.

I'm sat at work, so my brain isn't fully on this, but

Ali, the leader and one other would make it in one crossing, AAB.
Ali, the leader and two thieves make it in 5, adding four to the original single crossing.
Adding a third thief adds another four to make 9 crossings.
The fourth and fifth both add six crossings each for 15 and 21, the sixth and seventh both add eight for 29 and 37, and the ninth and tenth each add ten for 47 and 57.

The Crossing list is:

1) CDEFGHIJ AAB _ Out
2) CDEFGHIJ AB A Back
3) ADEFGHIJ BC A Out
4) ADEFGHIJ AB C Back
5) DEFGHIJ AAB C Out
6) DEFGHIJ BC AA Back
7) BEFGHIJ CD AA Out
8) BEFGHIJ AA CD Back
9) EFGHIJ AAB CD Out
10) EFGHIJ CD AAB Back
11) CFGHIJ DE AAB Out
12) CFGHIJ AB ADE Back
13) AFGHIJ BC ADE Out
14) AFGHIJ AB CDE Back
15) FGHIJ AAB CDE Out
16) FGHIJ DE AABC Back
17) DGHIJ EF AABC Out
18) DGHIJ BC AAEF Back
19) BGHIJ CD AAEF Out
20) BGHIJ AA CDEF Back
21) GHIJ AAB CDEF Out
22) GHIJ EF AABCD Out
23) EHIJ FG AABCD Back
24) EHIJ CD AABFG Back
25) CHIJ DE AABFG Out
26) CHIJ AB ADEFG Back
27) AHIJ BC ADEFG Out
28) AHIJ AB CDEFG Back
29) HIJ AAB CDEFG Out
30) HIJ FG AABCDE Back
31) FIJ GH AABCDE Out
32) FIJ DE AABCGH Back
33) DIJ EF AABCGH Out
34) DIJ BC AAEFGH Back
35) BIJ CD AAEFGH Out
36) BIJ AA CDEFGH Back
37) IJ AAB CDEFGH Out
38) IJ GH AABCDEF Back
39) GJ HI AABCDEF Out
40) GJ EF AABCDHI Back
41) EJ FG AABCDHI Out
42) EJ CD AABFGHI Back
43) CJ DE AABFGHI Out
44) CJ AB ADEFGHI Back
45) AJ BC ADEFGHI Out
46) AJ AB CDEFGHI Back
47) J AAB CDEFGHI Out
48) J HI AABCDEFG Back
49) H IJ AABCDEFG Out
50) H FG AABCDEIJ Back
51) F GH AABCDEIJ Out
52) F DE AABCGHIJ Back
53) D EF AABCGHIJ Out
54) D BC AAEFGHIJ Back
55) B CD AAEFGHIJ Out
56) B AA CDEFGHIJ Back
57) _ AAB CDEFGHIJ Out

Improve this answer
$\endgroup$
3
  • $\begingroup$ If I could get the interface to list in a spoiler, I'd list the crossings. $\endgroup$
    – UselessInfoMine
    Commented Dec 29, 2017 at 15:01
  • $\begingroup$ Aha! It actually tells you on the editing page. :) $\endgroup$
    – UselessInfoMine
    Commented Dec 29, 2017 at 15:46
  • $\begingroup$ Thanks for spotting my mistake. Fortunately, it's easily corrected, requiring only 4 extra crossings. $\endgroup$
    – Glorfindel
    Commented Dec 29, 2017 at 17:58
1
$\begingroup$

Lateral thinking answer: It can be done in

One trip. AAB in the boat, the other 8 in the water holding on to the sides, since they refuse to stay in the boat together.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This particular solution might be implicitly forbidden, though: If this solution works, then it would also have worked without promoting Ali Baba. This contradicts the question, which states that the constraint originally prevents them from crossing the river. $\endgroup$
    – Bass
    Commented Dec 30, 2017 at 18:50
  • $\begingroup$ @Bass ah, but only Ali is strong enough to row a boat with so many thieves hanging on it. $\endgroup$
    – Sneftel
    Commented Dec 31, 2017 at 5:42
0
$\begingroup$

33 steps

To be honest, I was trying to validate @Glorfindel answer with logic programming, but it came up with a shorter one

Everyone is on the left initially, trying to cross to the right side, the rightmost parameter is time step

cross(AAB,right,0)
cross(AB,left,1)
cross(BC,right,2)
cross(AB,left,3)
//C crossed

cross(AAB,right,4)
cross(AA,left,5)
cross(IJ,right,6)
cross(BC,left,7)
//IJ crossed, C crossed back

cross(AAB,right,8)
cross(AB,left,9)
cross(BC,right,10)
cross(AB,left,11)
//C crossed

cross(AAB,right,12)
cross(BC,left,13)
cross(CD,right,14)
cross(AA,left,15)
//D crossed

cross(AAB,right,16)
cross(BC,left,17)
cross(GH,right,18)
cross(AA,left,19)
//GH crossed, C crossed back

cross(AAB,right,20)
cross(AB,left,21)
cross(BC,right,22)
cross(AB,left,23)
//C crossed

cross(AAB,right,24)
cross(BC,left,25)
cross(EF,right,26)
cross(AA,left,27)
//EF crossed, C back

cross(AAB,right,28)
cross(AB,left,29)
cross(BC,right,30)
cross(AB,left,31)
//C crossed

cross(AAB,right,32)
//All crossed

Improve this answer
$\endgroup$
-3
$\begingroup$

It can all be done in

a single crossing

By

putting all the thieves in the boat in one trip. Ali Baba just wanted to be head thief for a little while.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Very clever, I suppose. How did they work around the limitation that B refuses to share a boat with D,E,F etc.? $\endgroup$
    – Bass
    Commented Dec 29, 2017 at 16:55
  • $\begingroup$ Well, not really, since C won’t go with either of the As. $\endgroup$
    – Bass
    Commented Dec 29, 2017 at 17:52
  • $\begingroup$ Drat. Thought I was being cute by exploiting the fact that there's no maximum on the boat's capacity, but it turns out there is a maximum on the boat's capacity thanks to the rank rule. $\endgroup$
    – chif-ii
    Commented Dec 29, 2017 at 17:54
  • $\begingroup$ @Bass I noticed my mistake just after the time limit on editing that comment expired. $\endgroup$
    – chif-ii
    Commented Dec 29, 2017 at 17:55
  • $\begingroup$ The rules are not well expressed- the OP never says that A and C are 2 ranks apart and similar- he really should have said the ranks are from 1, 2...11 and show the numerical separation. $\endgroup$
    – user2617804
    Commented Dec 30, 2017 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.