10
$\begingroup$

I was told this problem comes from Poland's biggest math competition for high school students from the year 2014. I am not sure of the answer but I am sharing since someone here can probably shed light on it.

The problem

In a magical forest there are 3 species - rabbits, wolves and lions. Wolves can eat rabbits, lions can eat both rabbits and wolves.

  • Whenever a wolf eats a rabbit, that wolf transforms into a lion.
  • If a lion eats a rabbit, it transforms into a wolf.
  • If a lion eats a wolf, it transforms into a rabbit.

In the beginning, there are 17 rabbits, 55 wolves and 6 lions in the forest.

What is the highest possible number of animals when no more animals can be eaten?

A related problem: the problem is similar to the chameleons of three colors puzzle, but I was not able to adapt the method to prove the answer in this problem.

$\endgroup$
  • 1
    $\begingroup$ What does the rabbit eat? $\endgroup$ – Mr Pie Jul 14 '18 at 3:13
  • $\begingroup$ I am pretty sure they just get eaten in this situation. $\endgroup$ – QuantumTwinkie Jul 14 '18 at 3:50
  • $\begingroup$ @QuantumTwinkie poor rabbits, lol. $\endgroup$ – Mr Pie Jul 14 '18 at 12:31
  • $\begingroup$ Hah, this is probably the only time in my life I have ever said "lol"... apart from just now. $\endgroup$ – Mr Pie Sep 17 '18 at 3:09
12
$\begingroup$

Here follows a somewhat informal proof -- mostly logical parts that made sense to me, if not in particularly specific notation.

Now, note:

To have a set of animals such that no animals can eat any others, there must be only animals of one type -- only rabbits, or only wolves, or only lions.
When any animal eats another animal, the parity of the number of each animal flips -- so if there were an even number of rabbits, it will become odd; or odd, then even, regardless of what animal ate what.
When all parities flip, that means that if the numbers of two animals have different parity, they will always have different parity.

So, from that:

We have to get rid of two animals whose numbers have the same parity. Since that's only possible with rabbits and wolves, we have to get rid of all rabbits and all wolves, leaving everything as lions.
At this point, we know we'll have to eat at least 55 things, to get rid of 55 wolves.

Now, we can do it like this:

First, 17 wolves eat 17 rabbits and become 17 lions, leaving us with 0 rabbits, 38 wolves, and 23 lions.
Then, 19 lions eat 19 wolves and become 19 rabbits, leaving us with 19 rabbits, 19 wolves, and 4 lions.
Finally, 19 wolves eat 19 rabbits and become 19 lions, leaving us with 0 rabbits, 0 wolves, and 23 lions.
Overall, that's 55 animals eaten, with a start of 78 animals, for an end result of $23$ animals left.

This is optimal, because:

We must get rid of all wolves, and to get rid of all wolves, we need to eat at least 55 times. And we have eaten exactly 55 times -- there is no way eat fewer animals and still solve the problem.

So the answer is

$23$

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Persona! I post videos about math puzzles on YouTube. If I post about this puzzle, I will credit you as "user Persona on StackExchange" for the solution, with a link to this thread too. (Or let me know how I can credit you). $\endgroup$ – Presh Jul 16 '18 at 1:42
  • $\begingroup$ That sounds good to me! $\endgroup$ – Persona Jul 16 '18 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.