-1
$\begingroup$

This problem (and solution) with 5 camels each was posted here on Puzzling several years ago:

Two merchants have 5 camels each. One fine day, one of the merchants sells all of his goods in the market and heads back to the village. He has to cross a bridge to reach his destination, and the bridge is only wide enough for 1 camel at a time.

At the same time, the other merchant is heading to the market to sell his goods and must cross the same bridge. Alas! They meet up in the middle of the bridge one camel-length from each other. They are both stubborn and won't back up their camels. Fortunately, the first merchant's camels are spry and unladen and are able to jump over another camel. Can both merchants get their camels across the bridge? (Both merchants' camels can jump)

The accepted answer offers two solutions, the first of which - 'a)' - goes as follows:

XXXXX_OOOOO
XXXX_XOOOOO
XXXXOX_OOOO
XXXXOXO_OOO
XXXXO_OXOOO
XXX_OXOXOOO
XX_XOXOXOOO
XXOX_XOXOOO
XXOXOX_XOOO
XXOXOXOX_OO
XXOXOXOXO_O
XXOXOXO_OXO
XXOXO_OXOXO
XXO_OXOXOXO
X_OXOXOXOXO
_XOXOXOXOXO
OX_XOXOXOXO
OXOX_XOXOXO
OXOXOX_XOXO
OXOXOXOX_XO
OXOXOXOXOX_
OXOXOXOXO_X
OXOXOXO_OXX
OXOXO_OXOXX
OXO_OXOXOXX
O_OXOXOXOXX
OO_XOXOXOXX
OOOX_XOXOXX
OOOXOX_XOXX
OOOXOXOX_XX
OOOXOXO_XXX
OOOXO_OXXXX
OOO_OXOXXXX
OOOO_XOXXXX
OOOOOX_XXXX
OOOOO_XXXXX

Question: Can this solution be extended to arbitrarily many camels?

$\endgroup$

1 Answer 1

1
$\begingroup$

If either kind of camel can jump, then yes:

A*(n+2) _ (AB)*i B*(n+2) (split off 2As from the first group)
A*n A A _ (AB)*i B B B*n (the leftmost Bs jump over an A)
A*n A A (BA)*i _ B B B*n (one B advances a step)
A*n A A (BA)*i B _ B B*n (The rightmost As jump over a B)
A*n A _ (BA)*i B A B B*n (Join a BA to the middle group)
A*n A _ (BA)*(i+1) B B*n (one A advances)
A*n _ A (BA)*(i+1) B B*n (join an A and a B to the middle group)
A*n _ (AB)*(i+2) B*n

Keep following this until you run out of As.

If n is even, at this point the camels will be alternating. Bs can just jump over As until they are off the bridge, then the As can just walk forward.

If n is odd, then all the Bs but the rightmost jump forward once. The rightmost B moves forward once. Now camels are alternating. Bs can jump forward until all are off the bridge.

$\endgroup$

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.