Answer to Problem of the Month for April 2009

The dragon has seven heads and five tails.

If you chop off one tail, a new one immediately grows back in its place.

If you chop off two tails, nothing grows back.

If you chop off one head, two new heads grow back.

If you chop off two heads, one new tail grows back.

You can either chop on the side of the heads or the side of the tails, and you can chop a maximum of two heads or two tails with one strike.

When the dragon has no heads and no tails left, it dies.

How many blows will it take to kill the dragon? Explain.

Solution to the Problem:

It will take at least 13 strikes to kill the dragon.
There are several ways to do this. Here is one method:

Tail	Head	Blow
5	7	Chop off 2 tails.
3	7	Chop off 2 tails.
1	7	Chop off 2 heads.
2	5	Chop off 2 tails.
0	5	Chop off 2 heads.
1	3	Chop off 2 heads.
2	1	Chop off 2 tails.
0	1	Chop off 1 head.
0	2	Chop off 1 head.
0	3	Chop off 2 heads.
1	1	Chop off 1 head.
1	2	Chop off 2 heads.
2	0	Chop off 2 tails.
0	0	Victory!

James Alarie took this to the next level. Here is his analysis of the original problem and the more general solution:
The original situation is a dragon with seven heads and five tails. I like shorthand, so I list this as (7H,5T).

Cutting off a single tail gives a new tail; no change; worthless action! Whacking off any number of heads always adds something, so this can not be our final action. Our last move(s) must be to lop off pairs of tails.

With the above items in mind, I see that I must have an even number of tails just before killing the dragon. And I must have an even number of heads to remove just before choping tails.

I chose to clip a single head three times in a row "(-H)*3" to give (10H,5T).

Next, I zap two heads at a time, five times "(-2H)*5" to give (0H,10T).

As a final step, I'll truncate a pair of tails at a time in five easy swipes "(-2T)*5" to give (0H,0T) and a dead dragon.

I really like general solutions, so:

1. define K=Mod(Heads,4)
2. define L=Mod(Tails,2)
3. define A=(Heads-K)/4
4. define B=(Tails-L)/2

Then cut off one head at a time (4+2*L-K) times.
Next lop off two heads at once (2*A+2+L) times.
Finally, snip two tails at a time (A+B+1+L) times.

The above works fine except when there are no heads and an odd number of tails. You have to begin by cutting off a head which doesn't exist, resulting in negative one heads, and two more grow back giving a total of one. Hmmm; very strange dragon!

Correctly solved by:

1. Josey Pitts	Mountain View High School Mountain View, Wyoming
2. Cami Micheli	Mountain View High School Mountain View, Wyoming
3. JD Pitts	Mountain View High School Mountain View, Wyoming
4. Morgan Vercimak	Mountain View High School Mountain View, Wyoming
5. Jacquelyn Heltz	Mountain View High School Mountain View, Wyoming
6. Stephanie Graham	Mountain View High School Mountain View, Wyoming
7. David & Judy Dixon	Bennettsville, South Carolina
8. Michelle Johnson	Mountain View High School Mountain View, Wyoming
9. Cherish Register	Mountain View High School Mountain View, Wyoming
10. James Alarie	Flint, Michigan
11. Les Walker	Ventura, California
12. Cole Glazner	Mountain View High School Mountain View, Wyoming
13. Jacob Harmon	Mountain View High School Mountain View, Wyoming
14. Philipp Heise	----------
15. Richard K. Johnson	La Jolla, California

April 2009 Problem of the Month

Correctly solved by:

April 2009
Problem of the Month