Armed with a sword and a shield, a proud knight combats a monstrous hydra with 100 heads.

Question

Hi so I am battling with this question at the moment.

"Armed with a sword and a shield, a proud knight combats a monstrous hydra with 100 heads. When he slashes, he removes 17 heads and 5 heads grow back. When he slices, he removes 6 heads and 33 grow back. When he cuts, 14 heads fall and 8 grow back. When he stabs, 2 heads fall and 23 grow back.

In order to kill the hydra, all its heads must be removed at some point, in which case no heads will grow back.

Can the knight’s sword and courage triumph against this mythological monster?"

I am assuming the hydra cannot grow more than the original 100 heads, and that you must cut off the exact amount (you can't slash 9 times).

My current working consists of:

rule a = shrink 6
rule b = shrink 12
rule c = grow 21
rule d = grow 27

b can be discounted as it's just aa

as 100 is the start point, and 6 is the minimum reduction some sum of 100 + c(x) + d(y) = a(z), or 100 + (21 * x) + (27 * y) must equal a multiple of 6.

100 + (21 * x) + (27 * y) = 6 * z where x, y, z are positive integers

simplifies to z = (7x/2) + (9y/2) + (50/3). For all positive integers x, y, there is no integer solution for z

I am not convinced this is enough proof.

Answer 1

Yes it is enough proof. Another way to say it is that

1. $21x=3\cdot 7 \cdot x$ is always divisible by 3
2. $27y=3\cdot 9 \cdot y$ is always divisible by 3
3. $6z = 3\cdot 2 \cdot z$ is always divisible by 3
4. $100=3\cdot 33+1$ gives rest 1 when divided by 3

And if you add something not divisible by 3 to something which is divisible by three you can never get something divisible by 3.

Another way to say it is left hand side will always be 1 modulo 3 and right hand side will always be 0 modulo 3. Numbers which have different modulos cannot be the same numbers.

Answer 2

The proof here is similar in spirit to the arbuzoid problem.

The net change of each operation to the number of heads is always a multiple of 3. Furthermore, the final operation must leave 0 heads before new heads grow back, which means that the number of heads before this operation must be the number of heads the operation removes in its first phase.

Together these two constraints imply that any successful strategy must end with an operation where 100 minus the number of heads removed in that operation is a multiple of 3. We check those differences: $$100-17=83$$ $$100-6=94$$ $$100-14=86$$ $$100-2=98$$ None of these is a multiple of 3. Thus there is no winning strategy.

There remains no winning strategy if we assume that heads die and grow at the same time, since 100 itself is not a multiple of 3.