Problem link :
Difficulty : CakeWalk
Pre-requisites : Basic programming language constructions
Problem : Determine whether it is possible to solve the generalized version of the Wolf-Sheep-Cabbage puzzle
Explanation
This is the easiest problem, and its’ solution is fairly easy. At first, it is easy to see that we can safely throw away from our consideration all the creatures that don’t eat anybody and don’t get eaten by anybody. It can be reasoned in the following way: in case there is a solution, you can move some part of creatures to the opposite shore in such a way that on the both shores nobody eats anybody. After this is done, you can move all these “isolated” creatures to the opposite shore.
So now let’s solve the version of the problem, where there are not any “isolated” creatures. Let’s consider all the particular cases:
- There is one creature. Obviously, the answer is “YES”;
- There are two creatures. First, you move the first one, then you move the second one. There is also no problem at all, so the answer is also “YES”;
- There are three creatures. One can simply prove that the answer is “YES” only in case the number of pairs where one creature eats another one is 2. Otherwise you will always obtain the case when one creature will eat another after you’ve made the first boat trip.
- There are four and more creatures. By simply writing out all the possible cases for 4 creatures, and even 3 edges, it is easy to convince that it is impossible to move all the creatures to the opposite shore.
So the solution is no more than throwing away all the “isolated” creatures and checking these four statements for the remaining ones.
