To obtain the solution, I present three possible ways:
- a non-feasible brute force solution,
- a feasible brute force solution, and
- an elegant, so to say, analytical solution.
When two animals of different species are chosen for a meal, these two animals disappear and an animal of the third species is generated. Therefore, there are finitely many possible states and finitely many ways to achieve these states. Devouring stops when there are animals of only one species left.
Non-feasible brute force algorithm
We can describe every devouring step by the animal that is generated in this step. E.g., if a lion devours a wolf, the resulting animal is a goat, and the step is described by the letter G (goat). Therefore, we could generate all words with fewer than 78 letters (78 is the initial total number of animals) of the three-letter alphabet {G, W, L} and decide which words are the shortest ones leading to the wiping out of two species. In the worst case, this would lead to 3^77 (=5.47 * 10^36) words to be generated. Of course, there are much fewer possibilities (no word can start with "GGGGGGG" (why?)), but far too many to obtain reasonable computing times.
A feasible brute force algorithm
Instead of bookkeeping the possible paths, the next algorithm keeps track of the possible states. So, starting from (17, 55, 6) (78 animals), we could obtain (16,54,7), (16, 56, 5) or (18, 54, 5) (77 animals) and so on, checking for 77,76, 75, .... animals, which combinations are attainable and which not. The algorithm stops as soon as a state is achieved which contains two species wtih 0 animals,
This algorithm needs less than one second on a single core and delivers (0, 0, 23) as the final state. One could also derive the devouring strategy leading to those 23 lions left.
The elegant solution
We know:
(1) the final state must contain two zero-species.
(2) Every meal reduces the number of animals in two species by 1 (each of them) and increases the number in the third species by 1.
(3) Thus (following from (2)), the combined number of any zwo species (goats and wolves, goats and lions, wolves and lions) either remains the same after a meal or is reduced by 2.
(4) If the final state should contain two zeros, then any earlier state of the two species to be wiped out must conatin an even sum for these two species. And the initial state as well.
(5) The only even sum obtained in the inital state is that from goats and wolves (17+55=72), Thus, the surviving species has to be lions.
(6) We know from (3) that goats + lions always stay below the initials number of goats + lions, i.e. 23. Therefore, 23 is an upper bound for the number of lions.
(7) If we can devlop a strategy ending up at (0, 0, 23), we are done. We also know that every devouring step has to contain a wolve. Otherwsie (if a lion ate a goat), 23 could not be achieved.
An optimal devouring strategy
The optimal strategy is not unique. One possibility is:
(1) 17 wolves devour 17 goats: (17, 55, 6) -> (0, 38, 23)
(2) 19 lions devour 19 wolves: (0, 38, 23) ->(19, 19, 4)
(3) 19 wolves devour 19 goats (19,19, 4) -> (0,0,23).
Next week, I will discuss the relevance of this example to computational finance.
