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 |