4
$\begingroup$

There are three dogs and three cats that have to be transported across a river: a big dog, a medium dog and a small dog, a big cat, a medium cat, and a small cat.

Rules:

  1. The raft can carry two animals, and all of the animals can row.
  2. The medium animal of each kind (darker color), cannot be left alone with either of the other animals of his kind, nor can the medium animal be transported with another animal of his kind.
  3. The big animal of each kind will not fight with the small animal.
  4. If ever there are more dogs than cats together on the shore, the dogs will fight with the cats.
  5. the raft can not be empty.

All of these has to be crossed within minimum possible shifts.

$\endgroup$
  • $\begingroup$ The big animal of each kind will not fight with the small animal. Small animal of its kind or any kind? $\endgroup$ – CodeNewbie Jun 29 '15 at 7:36
  • $\begingroup$ Also, If ever there are more dogs than cats together on the shore, the dogs will fight with the cats. Does this mean that if an animal is in the boat, he won't count as being on shore, so that you can have 3 dogs and 2 cats on the same side, as long as one dog is in the boat? $\endgroup$ – CodeNewbie Jun 29 '15 at 8:06
  • 1
    $\begingroup$ I don't think it's possible! I'm posting a big answer as we speak. Unless a dog remains on the boat without going on shore and take a cat with it, it's not possible. So can you clarify this point?? $\endgroup$ – CAS Jun 29 '15 at 8:15
  • $\begingroup$ the bigger once doesn't fight with smaller , this means they both can be on either shore together, but the darker colored Medium animal cant stay alone with the animals that are of same kind. or they even can't be commuted together (ex : Medium dog and [Big dog or small dog] can't commute or stay together alone on either shore.) $\endgroup$ – KRU Jun 29 '15 at 8:23
  • $\begingroup$ I'm finishing my answer, you'll understand at which point I'm referring to $\endgroup$ – CAS Jun 29 '15 at 8:24
10
$\begingroup$

It is possible.

Start: BD MD SD BC MC SC X on left, none on right (X is the boat)

  1. MD MC go to the right.

BD SD BC SC on left, MD MC X on right

  1. MC returns to the left.

BD SD BC MC SC X on left, MD on right

  1. BD SD go to the right.

BC MC SC on left, BD MD SD X on right

  1. MD returns to the left.

MD BC MC SC X on left, BD SD on right

  1. BC SC go to the right.

MD MC on left, BD SD BC SC X on right

  1. BD BC return to the left together.

BD MD BC MC X on left, SD SC on right

  1. MD MC go to the right.

BD BC on left, MD SD MC SC X on right

  1. SD SC return to the left together.

BD SD BC SC X on left, MD MC on right

  1. BC SC go to the right.

BD SD on left, MD BC MC SC X on right

  1. MD returns to the left.

BD MD SD X on left, BC MC SC on right

  1. BD SD go to the right.

MD on left, BD SD BC MC SC X on right

  1. MC returns to the left.

MD MC X on left, BD SD BC SC on right

  1. MD MC go to the right.

none on left, BD MD SD BC MC SC X on right

And they're done.


A crucial part of this solution is how to proceed when two dogs, two cats, and the boat are on the left. It is possible to send two cats, but we need to make sure that those two cats are the big one and the small one, and the same for the two dogs remaining. This is what steps 6-8 are doing.

$\endgroup$
  • 1
    $\begingroup$ On you're 14th line BD MD BC MC X on left, SD SC on right, it's not possible because The medium animal of each kind (darker color), cannot be left alone with either of the other animals of his kind, nor can the medium animal be transported with another animal of his kind $\endgroup$ – CAS Jun 29 '15 at 9:33
  • 1
    $\begingroup$ I added step numbers, so this is the situation after step 6. $\endgroup$ – f'' Jun 29 '15 at 9:38
  • 1
    $\begingroup$ I think your definition of "alone" is wrong. The dogs are not alone, because there are also two cats there. The same applies for the cats. $\endgroup$ – f'' Jun 29 '15 at 9:39
  • 1
    $\begingroup$ I think the question was unclear. $\endgroup$ – PirateSoul Jun 29 '15 at 9:40
  • 1
    $\begingroup$ I dont think the question is unclear; "alone" has a precise meaning. For example, if someone leaves his cat alone with his dog it means there is only a cat and a dog in his house. If the owner is at home the cat is not "alone with the dog". $\endgroup$ – Noel Jun 29 '15 at 10:01
2
$\begingroup$

I don't think it's ever possible that ALL the animals will be able to cross that river

Proof

I'll name them BD, MD, SD / BC, MC, SC (big dog, medium dog, small dog / big cat, medium cat, small cat) and Sh1 and Sh2 (Shore 1 and 2)

Sh1 contains: BD, MD, SD / BC, MC, SC
Sh2 contains: no one
Out of the 15 possible combinations:
- BC,MC / BC,SC / MC,SC: 2 cats cannot go together since Sh1 will be left with more dogs than cats. - BD,BC / BD,MD / BD,SC / MD,BC / MC,MC / MD,SC / SD,BC / SD,MC / SD,SC: only MD,MC is possible because at least one of the other animal kind will be left with a middle animal of the same kind
- BD,MD / MD,SD: Not possible since the middle dog will start the fight
- BD,SC: Seems possible at first, but when one of them return with the raft, they wil remain the middle dog and start a fight
So the only possible solution is MD,MC

Sh1 contains: BD, SD / BC, SC
Sh2 contains: MD, MC
Only MC can return the craft because if MD return it, Sh1 will contain more dog than cat

Sh1 contains: BD, SD / BC, MC, SC
Sh2 contains: MD
1 cat and 1 dog is not possible because Sh2 will have more dogs than cat
2 cats (BC,SC) also not possible because Sh1 will have more dogs than cat
Only solution here is BD,SD

Sh1 contains: BC, MC, SC
Sh2 contains: BD, MD, SD
Only MD can return the raft because if BD or SD return it, the other one will remain with the middle dog and start a fight

Sh1 contains: MD / BC, MC, SC
Sh2 contains: BD, SD
MD with any of the cat is not possible because Sh2 will have more dogs than cat
MC,BC / MC, SC also not possible because a fight will start with the middle cat
Only BC, SC is possible

Sh1 contains: MD / MC
Sh2 contains: BD, SD / BC, SC
Here it ends because no dog can return the shaft (Sh1 will have more dog than cat) and no cat can return it neither (a fight will start with the middle cat)

$\endgroup$
  • $\begingroup$ In my last point: unless a dog (let's say BD) can go and take the MC and return to Sh2 without 'steping' on Sh1 (since they'll be more dog than cat), it's not possible $\endgroup$ – CAS Jun 29 '15 at 8:37
  • $\begingroup$ You have went wrong some point then , please can you reduce your explanation and keep the points direct. $\endgroup$ – KRU Jun 29 '15 at 8:40
  • 1
    $\begingroup$ @KRU I agree with Chadi, I have posted an answer which I think is simpler. $\endgroup$ – Taemyr Jun 29 '15 at 8:42
  • $\begingroup$ Thanks @Taemyr! My answer is more detailed and contains all the possible combination and their problem(s) in each case but yours is more direct to the point $\endgroup$ – CAS Jun 29 '15 at 8:44
  • $\begingroup$ So can you clarify @KRU where we went wrong? $\endgroup$ – CAS Jun 29 '15 at 8:45
2
$\begingroup$

It is Possible without an empty boat: (at least if there is a Person with the boat "have to be transported" would imply that to be the case and animals don't fight and aren't alone if the person is there. Or they can at least restrain from fighting while changing seats in the boat)

my animals:

(s = small cat, m = medium cat, b = big cat,
 S = small dog, M = medium dog, B = big dog)

and here the boat:

- __ > 

rules:

allways more or equal cats(smb) then dogs(SMB)
never a medium animal with another of the same kind on a shore (except beginning and end)
and never two animals of a kind together on the boat (an even stronger one that no Medium animal with another of his kind)

and here the solution with 11 crossings:

smb SMB
sb  SB  - mM >
sb  SB  < m  -     M
sb  S   - mB >     M
sb  S   < M  - m   B
s   S   - Mb > m   B
s   S   < Mm > b   B
m   S   - Ms > sb  B
m   S   < M  - sb  B
    M   - mS > sb  B
    M   < m  - sb  SB
        - mM > sb  SB
               smb SMB
$\endgroup$
2
$\begingroup$

Initially every animal to the left.
STEP 1: Medium dog & Medium cat rows to right side. Medium cat comes back to left side.
STEP 2: Big dog & Small dog rows to right side. Medium dog comes back to left side.
STEP 3: Big cat & Small cat rows to right side. Big dog & Big cat comes back to left side.
STEP 4: Medium dog & Medium cat rows to right side. Small dog & Small cat comes to left.
STEP 5: Big cat & Small cat rows to right side. Medium dog comes back to left side.
STEP 6:Big dog & Small dog rows to right side. Medium cat comes back to left side.
STEP 7: Medium dog & Medium cat rows to right side.
Finally all animals are on the right bank.

$\endgroup$
0
$\begingroup$

It isn't impossible after all.

(B = big, M = medium, S = small)
(D = dog, C = cat)

I divide the area into 3 parts - the left shore on the left, river in the centre and right shore on the right.

1) LD LC MD MC SD SC |       |
2) LD LC SD SC       | MD MC |
3) LD LC SD SC       | MD    | MC          (drop MC on Right shore, MD stays in raft)
4) LD MD SD          | LC SC | MC          (drop MD on Left shore, pick up LC SC)
5) LD MD SD          |       | LC MC SC
6) LD MD SD          |       | LC MC SC    (Send the empty raft back to Left shore)
7) MD                | LD SD | LC MC SC
8) MD                | MC    | LC SC LD SD (drop LD SD on Right shore, pick up MC)
9)                   | MC MD | LC SC LD SD (pick up MD from Left shore)
10)                  |       | LD LC MD MC SD SC

Complete.

$\endgroup$
  • 1
    $\begingroup$ raft can't be commuted empty $\endgroup$ – KRU Jun 29 '15 at 10:13
  • 1
    $\begingroup$ That rule was not stated in the question. $\endgroup$ – Alex Walker Jun 29 '15 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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