6
$\begingroup$

A farmer and his $n$ cats and $m$ dogs are on one side of a river. There is a boat that can carry the farmer and at most $k$ animals at once. The boat doesn't move without a person operating it. The animals can't swim across the river.

If at least one dog and at least one cat are left on one side of the river without the farmer, they will start fighting. The objective is to move the farmer and all the animals to the other side using only the boat while avoiding such situation.

Assume $2 \le n \le m$. What is the minimum value of $k$ that will let the farmer and his animals cross the river, and what is the minimum number of one-way crossings with that value of $k$? Describe both values in terms of $n$ and $m$.

$\endgroup$

2 Answers 2

3
$\begingroup$

I want to improve on Tim's answer, as I feel not all cases are covered.

We have $n$ cats, $m$ dogs, $1 \leq n \leq m$. We want to minimize $k$ = the capacity of the boat.

First let's find the minimal $k$.

If $k < n$, we cannot leave the shore without leaving at least a cat and a dog on the side, which would cause a fight. So $k < n$ is not possible. We must have $k \geq n$.

On the other side, if $k = n+1$, we can load all cats in the boat and ferry one dog at a time until all animals are on the other side. So, $k = n+1$ is always enough.

This means that in all cases, $k$ must be $n$ or $n+1$.

More about $k$:

When $m \leq 2n$, there is a way to carry all animals in 7 crossings with $k = n$.
1. Carry all cats over, 2. go back, 3. carry half of the dogs over, 4. carry the cats back, 5. carry the rest of the dogs to the destination, 6, go back, 7. carry the cats to the destination.
So, for $m \leq 2n$, $k = n$ is possible.

But if $m > 2n$, $k = n$, we need to carry the dogs in at least 3 batches. At the time we carry the 2nd batch we have dogs on both sides of the river. The only way for it to work is if all cats are in the boat. But to carry all cats plus at least one dog, we must have k = n+1.

More rigorously, we can show that $m > 2n$ and $k=n$ is not possible regardless how we shuffle the animals around.
Under these conditions there must be a crossing after which we have for the first time more than $n$ dogs on the destination side. Before that crossing, there must have been a dog already at the destination. After the crossing, we have less than $2n$ dogs on the destination side, so there are still dogs on the starting side. This means that during this crossing there were dogs on both sides of the river, and as explained before, we must have all cats in the boat at that time plus one dog. So with $m > 2n$, we need $k = n+1$.

Now the number of trips or crossings:

One special case is $n = m$. In that case, $k = n$ and we can do the job in 3 crossings:
1. ferry over all cats, 2. go back, 3. ferry over all the dogs.

If $n < m <= 2n$, we also have $k = n$, we can ferry all animals in 7 trips in the way already explained.

If $n > 2m$, we must have $k = n+1$.

If $2n < m <= 2n+2$, we still can apply the 7-step strategy since we have one more place in the boat.
- ferry all cats over
- go back
- ferry $n+1$ dogs over
- bring the cats back
- ferry the remaining dogs over
- go back
- ferry the cats to destination

If $m > 2n+2$, we still have $k = n+1$. But we have too many dogs for 2 batches. We need to improve the strategy above.
Just after step 4 "bring the cats back", we add the steps "ferry over the cats and one dog" and "bring the cats back". These 2 steps are repeated for each dog in excess of the 2n+2 dogs that are already taken care of. This adds $2\times(m-2n-2)$ steps to the program.

So, this case requires $7 + 2\times(m-2n-2) = 2m - 4n + 3$ trips.

In summary:

- if $m = n$, then $k = n$ and we need 3 trips.
- if $n < m \leq 2n$, then $k = n$ and we need 7 trips.
- if $2n < m \leq 2n+2$, then k = n+1 and we need 7 trips.
- if $2n+2 < m$, then $k = n+1$ and we need $2m - 4n + 3$ trips.

$\endgroup$
2
  • 1
    $\begingroup$ Accepting this answer because it solves the exact question asked in the puzzle. Note that I put $2 \le n$ because there is one exceptional case (spoiler). $\endgroup$
    – Bubbler
    Jan 28 at 23:29
  • $\begingroup$ Indeed! I was wondering why you said n>=2. $\endgroup$
    – Florian F
    Jan 29 at 20:55
4
$\begingroup$

As far as I can tell, there are multiple possible strategies the farmer can take, depending on the size of her boat relative to the number of animals. The final number of trips depends on the strategy used, and different strategies are optimal at different points.

Strategy 0

The simplest possible strategy requires

$k \geq n + m$

Given this, the farmer can:

Load all the animals into the boat and take them across in a single trip.

Strategy 1

The next strategy requires:

$n \lt k$

And is very simple:

Load all the cats into the boat, then use the remaining space to take dogs across, taking as many trips as necessary. Keep the cats in the boat until all the dogs are across. Since the cats are always with the farmer, they will never fight. Furthermore, as long as there is space for at least one dog along with all of the cats, the farmer will eventually be able to move all of the dogs.

This strategy takes

$2\lceil\frac{m}{k-n}\rceil - 1$ trips

Strategy 1.1

In some circumstances, this strategy can be made slightly more efficient by

Taking only the cats across in the first trip and leaving them on the far shore briefly in order to take a full boat full of dogs, then picking them back up afterward.

With this optimization, this strategy will take

$4 + 2\lceil\frac{m-k}{k-n}\rceil - 1$ trips

And is optimal whenever that number is larger than the length of the unmodified strategy 1, which I believe happens when:

The cats take up more than half the boat, e.g. $\frac{n}{k} > \frac{1}{2}$

Strategy 2

If there are too many cats to perform the strategy above, the farmer can still get all the animals across as long as

$k = n$
$2k \geq m$

Using the following strategy, which takes a fixed number of moves.

1. Take the $n$ cats to the far shore.
2. Return to the near shore empty.
3. Take $k$ dogs to the far shore.
4. Take the $n$ cats back to the near shore.
5. Take the remaining $m - k$ dogs to the far shore.
6. Return to the near shore empty
7. Take the $n$ cats to the far shore.

Too many cats

If there are too many cats, described by the inequality:

$n > k$

Then the farmer cannot take even a single move without causing a fight.

Too many dogs

If there are too many dogs, described by the inequalities:

$k = n$
$m > 2k$

Then there is no sequence of moves which moves the animals across.

1. From the initial position, the farmer can only move all of the cats (go to 2). Any other move results in a fight.
2. Now the farmer can only either take the cats back (go to 1) or return empty (go to 3).
3. Now the farmer can only either return empty (go to 2) or take some dogs across (go to 4).
4. Now the farmer can only take the dogs back (go to 3) or take all the cats back (go to 5).
5. Now the farmer can only take all the cats back (go to 4). There is no other move that does not result in a fight.

$\endgroup$
4
  • $\begingroup$ Nice analysis, though I didn't ask for all possible combinations of $(n, m, k)$. Also a few formulas seem off, including the ones in the last box of strategy 1.1 and the first of strategy 2. $\endgroup$
    – Bubbler
    Jan 26 at 2:15
  • $\begingroup$ It should be k/n > 2 and 2k >= m, indeed. $\endgroup$
    – justhalf
    Jan 26 at 2:54
  • $\begingroup$ Strategy 2 requires $2k\ge m$ and too many dogs should be $2k<m$. $\endgroup$ Jan 26 at 2:55
  • 1
    $\begingroup$ Strategy 1.1 could also optimize the end game by leaving the cats on the starting shore as soon as you can load all remaining dogs. $\endgroup$
    – Florian F
    Jan 26 at 15:29

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.