Prince Valiant went to fight a 3-headed, 3-tailed dragon.

He has a magic sword that can, in one stroke, chop off either one head, two heads, one tail, or two tails.

This dragon is of a type related to the hydra; if one head is chopped off, a new head grows. In place of one tail, two new tails grow; in place of two tails, one new head grows; if two heads are chopped off, nothing grows.

What is the smallest number of strokes required to chop off all the dragon's heads and tails, thus killing it?

Hi guys, I believe 9 is indeed the minimum, and here's why:

Eventually we want to be left with an even number of heads (and no tails) to finish off the beast.

Since we start off with an odd number of heads, and chopping off either one or two heads always leaves us with the same parity of heads, we need to use the tails to change the parity of the heads.

So we need to use the tails to make an odd number of heads. Cutting two tails to get a head means we need to get 2*(an odd number) of tails before we start turning them into heads.* Positive odd numbers can be defined as 2n-1 where n is a positive integer. So 2*(an odd number) = 2*(2n-1) = 4n-2.

So the smallest number of tails that satisfies this rule is when n=1 making the number of tails = 2. But we already have 3 to start with. The only way to get two tails is to cut two tails, turn them into a head (and then cut the last tail to get two tails), but I said we wouldn't start turning tails into heads until we had 4n-2 tails.*

Therefore I need to get the next smallest number of tails to satisfy my rule. So when n=2, the number of tails = 6. In order to get 6 tails, Prince Valiant must cut one tail three times.

Then he can cut two tails three times to turn them into heads.
Then he can cut two heads three times to kill off the beast. So the minimum number of cuts is 9.

* Ok, the rule about not turning tails into heads until we had 2*(an odd number) of tails doesn't have to be followed strictly. The only reason I made that rule was because if you cut two tails to make a head, now the parity of the heads has changed (we have an even number of them), which changes my strategy a bit. Now instead of working on having 2*(an odd number) of tails, we have to work towards having 2*(an even number) of tails. In order to keep myself from changing strategy a lot and getting really confusing, I made this rule. This rule does not effect my outcome of 9 cuts being the minimum, but I'm guessing someone will want me to argue that more clearly. I'll only do that upon request though =)

Edited on December 10, 2004, 3:54 pm

Posted by nikki on 2004-12-10 15:51:46