A strange forest
In a strange forest, there are 6 werewolves, 17 unicorns and 55 giant spiders.
-
A werewolf can eat a spider or a unicorn, but it can't eat another werewolf.
-
A spider can eat a unicorn, but it can't eat a werewolf or another spider.
-
A unicorn can eat nothing, be it a spider, a werewolf, or another unicorn.
-
When a werewolf eats a spider, it turns into a unicorn, and when it eats a unicorn, it turns into a spider.
-
When a spider eats a unicorn, it turns into a werewolf.
What is the maximum number of living creatures left in the forest, given that no other creature can be eaten?
Bonus:
How many of each species are left alive in the end?
The answer is 23.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Great explanation of why 23 is an upper bound :)
Using the parity argument, apart from concluding that "all spiders have to be eaten", we can further conclude that "if only 1 species is left, it has to be the werewolves". Do you see why?
Log in to reply
Thank you for the kind words!
As for your question, I'm afraid that I cannot answer it, for I don't see how I can use the parity argument to instantly find the species that will be left alive. Would you please care to explain?
Log in to reply
Note that the parity of werewolves is always going to be different from the parity of unicorns and spiders. If only 1 group is left, the other 2 groups must have the same parity, since they have 0 in them. Thus, the other 2 groups could only be the unicorns and spiders.
This just elaborates on the reasoning/ideas in your first paragraph.
We can see that number of werewolf (w), spider (s) and unicorn (u) can change as following
| w | s | u |
| -1 | -1 | +1 |
| -1 | +1 | -1 |
| +1 | -1 | -1 |
This means that all of them change parity (even or odd) whenever something eats something.
Also, if there are multiple species left , 1 of the 3 cases can always happen which means finally only 1 of each species must live.
Using these 2, we conclude that the 2 species which are reduced to 0 at the end will have equal parity since the start. This means that only werewolves are finally left alive and both unicorns and giant spider will become extinct (As they are both odd at the beginning).
To find how many are actually alive at the end, We shall repeatedly apply the following:
3rd case to maximize number of werewolves.
1st case to reduce number of spiders followed by 3rd case to eat the just created unicorn.
Using this we can deduce that finally only 23 werewolves will be left alive.
First of all we call "move" when an animal eats another one:
-
M 1 : werewolf eats unicorn → W= -1 ; U= -1; S=+1 → n M 1 = n S − n ( W + U )
-
M 2 : werewolf eats spider → W= -1 ; R= -1; U=+1 → n M 2 = n U − n ( W + S )
-
M 3 : spider eats unicorn → W= +1 ; U= -1; S-1 → n M 3 = n W − n ( U + S )
Each move reduces by one the sum of animals.
-
M 1 + M 2 = − 2 W
-
M 1 + M 3 = − 2 U
-
M 2 + M 3 = − 2 S
-
M 1 + M 2 + M 3 = − ( W + U + S )
We can observe U and S remain both even or odd.
In order to have the maximum number of animals, we have to maximize W (reducing U ) and make even S (otherwise with other moves the sum of animals becames 1 ) so:
[ 6 W , 1 7 U , 5 5 S ] , 1 7 ( M 3 ) → [ 2 3 W , 3 8 S ] ; 1 9 M 3 + M 2 → 2 3 W
From the text, we can conclude that only one species can be left alive in the end. After each "meal", the parities of the numbers of unicorns and werewolves stay different, meaning that all spiders have to be eaten.
This would take 55 "meals", meaning that there can be 23 creatures at most.
On the other hand, if 17 spiders eat all of the unicorns immediately, we'll have 23 werewolves and 38 spiders left.
Let the rest of the "meals" go in this flow: a werewolf eats a spider, becomes a unicorn, and gets eaten by another spider. After every one of these meals, the number of werewolves stays the same, while the number of spiders decreases by 2. After 19 of these "meals", there will be only 23 werewolves left, giving us the answers to both the main and bonus questions.