Question

King Vikramaditya has two magic swords. With one, he can cut off 19 heads of a dragon, but after that the dragon grows 13 heads. With the other sword, he can cut off 7 heads, but 22 new heads grow. If all heads are cut off, the dragon dies. If the dragon has originally 1000 heads, can it ever die? (Hint: The number of heads mod 3 is invariant.)

Answer 1

No. of heads of dragon = 1000

sword 1 : cuts 19 heads but 13 heads grow back. 

sword 2 : cuts 7 heads but 22 heads grow back.

Let n be the number of heads of the dragon at initial state.

Case 1 : King uses Sword 1

Sword 1 cuts off 19 heads but 13 heads grow back. 

n : = n – 19 + 13 = n – 6 No. of heads are reduced by 6.

Case 2 : King uses Sword 2

Sword 2 cuts 7 heads but 22 heads grow back.

n : = n – 7 + 22 = n + 15

No. of heads are increased by 15.

Note:

In the above two cases either 6 heads are removed or 15 heads added. Both 6 and 15 are multiples of 3.

Therefore repeating case 1 and case 2 recursively will either reduce or increase dragon heads in multiples of 3.

That is the invariant is n mod 3.

If n mod 3 = 0 then there is a possibility that the dragon dies.

But 1000 is not a multiple of 3 1000 mod 3 = 1 ≠ 0 

It is not possible to kill the dragon. The dragon never dies.