# Camels crossing a bridge

Two merchants have 5 camels each. One fine day, one of the merchants sold 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 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 merchant camels can jump)

• So on the first turn, A or 1 can advance. Let 1 advance. Now 2 can advance or 3 can jump, with 3 jumping being indistinguishable from 2 moving then 3 moving. Then the same deal with 4 move or 5 jump, until all the camels are stuck in the middle. So let's move A on turn 1. 1 jumps A, A advances, 2 jumps A, A advances, etc., until A escapes the jam, but now 1 is pressed up against B and no moves can be made. So it seems impossible to me. – Caleb May 5 '15 at 19:56
• Can you please clarify? Can a camel never move backwards or is it OK so long as they don't move backwards all the way off the bridge? – Engineer Toast May 5 '15 at 20:05
• @JonTheMon and Engineer, I suppose we should wait for the original author to edit it himself. – ghosts_in_the_code May 5 '15 at 20:06
• Are you sure it can be done? Or are youasking just that "can it be done" – Spencerkatty May 5 '15 at 20:10
• Correct me if I'm being stupid, but didn't it say that the first merchant had already sold all of his camels? In that case, getting the second man's camels over would be easy. – AJL May 5 '15 at 23:00

Depending on how well I understood the question it is possible.

It is possible if either a) any camel can jump over any other camel (based on "Both merchant camels can jump") or b) if the camels can walk backwards as long as they never end up behind where they started.

### a:

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


### B (X can jump):

XXXXX_OOOOO
XXXXXO_OOOO
XXXX_OXOOOO
XXXXOXO_OOO
XXXXO_OXOOO
XXX_OXOXOOO
XXXOXOXO_OO
XXXOXO_OXOO
XXXO_OXOXOO
XX_OXOXOXOO
XXOXOXOXO_O
XXOXOXO_OXO
XXOXO_OXOXO
XXO_OXOXOXO
X_OXOXOXOXO
XOXOXOXOXO_
XOXOXOXO_OX
XOXOXO_OXOX
XOXO_OXOXOX
XO_OXOXOXOX
_OXOXOXOXOX
OXOXOXOXOX_
OXOXOXOXO_X
OXOXOXO_OXX
OXOXO_OXOXX
OXO_OXOXOXX
O_OXOXOXOXX
OOXOXOXO_XX
OOXOXO_OXXX
OOXO_OXOXXX
OO_OXOXOXXX
OOOXOXO_XXX
OOOXO_OXXXX
OOO_OXOXXXX
OOOOXO_XXXX
OOOO_OXXXXX
OOOOO_XXXXX


It would all have been easier if they'd just backed up a bit.

• I like the wave pattern the empty space makes. – Lopsy May 6 '15 at 10:15
• But the problem says only the 1st merchant's camels can jump. This solution would at least require moving the load from one camel to the other. PS: OK, not with the last update. – Florian F May 6 '15 at 10:58
• @FlorianF, yes for case a it does need the update and case b needs for them to be able to back up after moving forwards. – Holloway May 6 '15 at 11:08

Yes, if you can switch materials between adjacent camels allowing others to jump. Call Merchant 1 Camels A-E Merchant 2 Camels F-J. F moves forward. A jumps him. Repeat with F moving forward and B through E jumping when needed. Then G materials moved onto B. G is now unladen and can jump B. Move materials back onto G then move B forward. Repeat process with every camel. Otherwise you just get stuck after trying to move forward in any way.

• IMO, being able to transfer goods seems an unwarranted assumption of the trust level of these merchants, considering they won't even back up for each other. – Set Big O May 5 '15 at 20:16
• Only the unladen merchant has anything he can steal and this can be prevented. When you reach camels E and J E jumps J. The other goods would of already been transfered else J refuses to move until that happens since the camel with the stolen goods cant move on until he gives them up. – user2389345436357 May 5 '15 at 20:33
• This transferring action doesn't seem to be given in the original post, but it seems like the most realistic way to get the camels across given what we know (plus, the fairly crucial jumper camel tidbit was originally presented as a hint, so who knows what kind of skills we are supposed to derive here). – Caleb May 6 '15 at 0:56
• they may be unladen, but they are not spry – Vic May 6 '15 at 2:46

I'm pretty sure it cannot be done. At best, one of the two merchants can get one of his camels across the bridge. This leaves the other 9 camels at a standstill on the bridge though.

• If both camels can jump, they can all cross the bridge. – Holloway May 6 '15 at 8:58

There are 2 ways of thinking of this: either the light camels can "switch" with a heavy camel, or they have to jump over a heavy camel to an empty space.

In the former case, all the camels can get across to the other sides.

In the latter case, only 1 heavy camel can get across as is. It would take 4 starting spaces between the groups to get all the camels across.
Effectively, the heavy group needs to be able to spread out with a space between each (4 spaces for 5 camels).

Yes, they can get their camels across, assuming that the camels can jump straight up without having to move forward. All they have to do it have the first camel jump while camel the across from it moves forward.

ie. [12345_ABCDE] becomes

[1234_5ABCDE] turns into 1234_(5/A)_BCDE where 5 is jumping upwards, while A is moving forward

[123_A5BCDE] where A has passed under 5

[123A_(5/B)CDE] etc...

Only way this can be done is if we don't think of it as a "one move per turn" problem.

If the unladen camel can jump to position where the pack-loaded camel is currently standing and at the same time the pack loaded camel must move with haste to the former position of the jumping camel.

This will switch their positions and becomes sort of bubble-sort.

Edit:

It has been edited so both merchant's camels can jump now. This changes the puzzle completely.

This solution takes the problem as it is with no additional assumptions.

From the given information, camels can only move forward and can jump over one camel, given that they will have at least a camel sized space to land on.

O First merchant's camel X Second merchant's camel

        OOOOO XXXXX
OOOOOX XXXX
OOOO XOXXXX
OOO OXOXXXX
OOOXO OXXXX
OOOXOXO XXX
OOOXOXOX XX
OOOXOX XOXX
OOOX XOXOXX
OO XOXOXOXX
O OXOXOXOXX
OXO OXOXOXX
XO O OXOXOXX

at this point the leftmost X camel has crossed and can
walk forward any number of times to make space.

X    O OXO OXOXX
X    OXO O OXOXX
X    OXO OXO OXX
X    OXO OXOXO X
X    OXO OXOX OX
X    OXOXO OX OX
X    OXOXOXO  OX
X    OXOXOXO XO       Same goes for this right most O camel.
X    OXOXOXOX     O
X   XO OXOXOX     O
XX   O OXOXOX     O
XX   OXO OXOX     O
XX  XO O OXOX     O
XXX  O OXO OX     O
XXX  OXO O OX     O
XXX XO O O OX     O
XXXX O O O OX     O
XXXX O O OXO      O
XXXX O OXO O      O
XXXX OXO O O      O
XXXXXO O O O      O
XXXXX         OOOOO

• This still relies on both camels being able to jump – Holloway May 7 '15 at 13:32
• @trengot the last bit of information enclosed in parentheses states that both sets of camels have the ability to jump. – nzdrml May 7 '15 at 19:17
• Yeah, it's just a bit unclear as it contradicts itself. – Holloway May 7 '15 at 19:27