# 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

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)$.