Cut off one head, two more shall take its place

Logic Level 3

There is a creature with many heads, one knight wants to kill it. He can cut 1, 7 or 11 heads off.

If there is any head left:
I) After cutting 1 head off, 4 heads will grow.
II) After cutting 7 heads off, 1 head will grow.
III) After cutting 11 heads off, 5 heads will grow.

Creature dies when there isn't any head left.

Can knight kill it
1. If it has got 100 heads?
2. If it has got 99 heads?

Image Credit: Flickr Leo Saldaña .

No 2. No

Yes 2. Yes

Yes 2. No

No 2. Yes

3 solutions

Brian Charlesworth
Aug 23, 2015

If the creature has $100$ heads, then one way the knight can proceed is as follows. Go through the $(7,1)$ process, (i.e., $7$ heads cut off, $1$ head grows back), a total of $16$ times, which will leave the creature with $100 - 16*(7 - 1) = 4$ heads remaining. Now go through the $(1,4)$ process once to end up with $7$ heads remaining, which the knight can then cut off to finally kill the creature.

If the creature has $99$ heads, then first note that as long as the creature is alive, the $(1,4)$ process will increase the number of its heads by $3$ , and both the $(7,1)$ and $(11,5)$ processes will decrease the number of its heads by $6.$ Since the creature starts with $99$ heads, which is divisible by $3,$ and can only have its number of heads change (after one of the processes) by $3$ or $6$ while remaining alive, then while it is alive the number of heads it has after any of the three processes will always be divisible by $3.$ But since none of $1,7$ or $11$ is divisible by $3,$ the knight will never be able to deliver the final blow to kill the creature.

Thus the knight can kill a $100$ -headed creature but not a $99$ -headed one.

In the first part of your solution, after the knight goes through the( $1,4$ ) process once, the creature ends up with just 7 heads. After cutting off these 7, wouldn't one more grow? It seems logical that a head must replace the lost 7 as stated in the question.

Nehemiah Osei - 5 years, 9 months ago

Good point, but note that in bold print we have "If there is any head left ....". So how I read this was, for example, "If there is any head left after cutting $7$ heads off, $1$ head will grow." So after cutting off the last $7$ heads, since no heads remain, the creature is finally dead and no head will grow back.

Brian Charlesworth - 5 years, 9 months ago

In that case I get you. Thanks.

Nehemiah Osei - 5 years, 9 months ago

Read the question again.

Anelize Theron van Biljon - 5 years, 9 months ago

You can also notice that on a cutting where the creature hasn't died yet, the number of heads remains invariant mod three.

Therefore, you can kill it when it has 100 heads because you can cut off 1 mod 3 heads.

However you can't cut off a multiple of three number of heads therefore 99 is impossible.

Then you just find a possible cutting for 100 and you are done.

Alan Yan - 5 years, 9 months ago

when it reaches to 4 heads,how cutting with (1,4) gives 7 heads ? Should not it again come back to 16 heads.

Aditya Duhan - 5 years, 9 months ago

When it reaches 4 heads, cutting off a head will leave 3 heads intact, which combined with the 4 new heads that grow back leaves the creature with 7 heads.

Brian Charlesworth - 5 years, 9 months ago

fine,i was cutting all the heads once. Thanks. But still out approach is sort of trail based , I mean i am not sure whether i will be able to solve further questions like this with different set of data .

Aditya Duhan - 5 years, 9 months ago

@Aditya Duhan – It does depend on the specific data given, and there isn't any formula that works in all cases. However, for this problem, we know that a creature with a multiple of $3$ heads can't be killed, but a creature with any other number of heads can be. When the number of heads is $1 \pmod{3}$ then you can either first get to $7$ heads left and then make the kill, or to $4$ heads left and then follow the same method as outlined in the $100$ head case.

When the number of heads is $2 \pmod{3}$ then you can either get to $8$ heads left, use a $(1,4)$ step to get to $11$ heads left and then make the kill, or get to $5$ heads left and make two $(1,4)$ steps to get to $11$ heads left and then make the kill.

I would think that any question like this would be set up in a similar way, so that one could use modular arithmetic to make a full analysis of all the possible cases.

Brian Charlesworth - 5 years, 9 months ago

Anelize Theron van Biljon
Sep 7, 2015

From 100: Whether you use (-11+5) or (-7+1) does not matter. Eventually you will get down to 4 (since 16 x 6 = 96). Then 4-1+4 = 7 and 7-7 = 0. From 99: Get down to 3 (one less than for the 100 case). Now, 3-1+4=6 and 6-1+4=9, 9-7+1=3 and the cycle will just repeat.

Debashish Saha
Sep 7, 2015

100 heads, so taking (11,5) function -> we continue until 16 times until we are left with 2 + 5 heads to which we apply (7,1) function once which gives 7 heads in the last stage which is finally carried out using function (7,1) .

Cut off one head, two more shall take its place

Image Credit: Flickr Leo Saldaña .

3 solutions

0 pending reports