# Wolves and chicks puzzle

This problem is from the handheld video game, Professor Layton and the Curious Village.

I think the solution is very cool, but more than that, I want to know how to show that the minimum number of moves for a solution has to be 11.

I also want to know how to find the minimal number of moves in a solution for an arbitrary number of wolves and chicks, where the number of chicks is greater than or equal to the number of wolves, and animals can begin on either island (obeying the rule that one side must not have more wolves than chicks).

I asked someone who is a math major, and he told me that this is a linear programming problem. That's too bad, though, because I only have high school calculus under my belt.

Can you explain this to me?

-
This could be done via constructing the game tree (it is rather small). With some smart pruning there are only a few states you need to check, moreover, there is 4*4 states total, so even without pruning it should be quite easy. –  dtldarek Mar 27 '13 at 22:42

Every time you go you can take at most 2 animals with you. When you come back you need to take at least one with you. Therefore after 10 moves at most you will have taken 10 animals on the boat and taken 5 animals back on the boat. Therefore right before the 11th move you will be in the initial side of the river and will have at the least one animal in the side of the river in which you are. This proves that it is not possible to do it in less than 11 moves.

-

(Too long for a remark.) By the way, one can visualize all possible moves by transforming the puzzle into a graph problem:

The $x$ and $y$ axes represent respectively the number of chickens and the number of wolves on the left side of the river. Black arrows signifies a move from the left side to the right side, and red arrows represent trips in opposite direction. We start at $(3,3)$. The goal is to reach $(0,0)$ by a path interlaced by black and red arrows. It is not hard to see that, somehow the path must contain the subpath $(3,1)\to(1,1)\color{red}{\to}(2,2)\to(0,2)$.

-