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.

Improve this question
$\endgroup$
7
  • $\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, 2015 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, 2015 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, 2015 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, 2015 at 8:23
  • $\begingroup$ I'm finishing my answer, you'll understand at which point I'm referring to $\endgroup$
    – CAS
    Jun 29, 2015 at 8:24

5 Answers 5

Reset to default
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.

Improve this answer
$\endgroup$
7
  • 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, 2015 at 9:33
  • 1
    $\begingroup$ I added step numbers, so this is the situation after step 6. $\endgroup$
    – f''
    Jun 29, 2015 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, 2015 at 9:39
  • 1
    $\begingroup$ I think the question was unclear. $\endgroup$
    – PirateSoul
    Jun 29, 2015 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, 2015 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)

Improve this answer
$\endgroup$
9
  • $\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, 2015 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, 2015 at 8:40
  • 1
    $\begingroup$ @KRU I agree with Chadi, I have posted an answer which I think is simpler. $\endgroup$
    – Taemyr
    Jun 29, 2015 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, 2015 at 8:44
  • $\begingroup$ So can you clarify @KRU where we went wrong? $\endgroup$
    – CAS
    Jun 29, 2015 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
Improve this answer
$\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.

Improve this answer
$\endgroup$
0
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.

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

Your Answer

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

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