Minimum Number of Cuts to Slay the Dragon?

Date: 01/14/2007 at 12:38:29
From: Camille
Subject: Smallest number of slices

A certain knight is the champion of the King, so he seeks out a dragon 
to kill.  The dragon has 3 heads and 3 tails and all must be removed 
(and stay that way) for him to gain his reward.  Our knight has a 
magic sword that is capable of 4 types of cuts: one head, two heads, 
one tail, or two tails.  The problem is that the dragon is also 
magical and can regrow one head for each single head cut, regrow two 
tails for each single tail cut, or grow a head for a double tail 
whack.  Nothing is regrown for a double head cut.  What is the 
smallest number of slices that our knight can use to oust the beast?

I mostly need help reading it through because even though I've read it
many times myself, I still don't get everything that is going on.  And
what kind of problem is it (equations, ratio, probability, ...)?

Date: 01/14/2007 at 13:38:33
From: Doctor Douglas
Subject: Re: Smallest number of slices

Hi Camille.

Thanks for submitting a good problem.  If the dragon regrows 
(something) most of the time, the knight can't win.  But since
"nothing is regrown for a double head cut", the knight can be
victorious if (by some complicated means) the dragon can be reduced to 
a two-headed-and-no-tailed beast.  Do you see that?

The type of mathematics used here has to do with discrete math.  My 
suggestion would actually be to draw a diagram (on graph paper) 
representing what choices the knight has on each slice.  Maybe you can 
figure out how to proceed with this hint, but if you're still stuck, 
feel free to write back.

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/14/2007 at 23:51:08
From: Camille
Subject: Smallest number of slices

Thank you for that comment it was very helpful!  This is what I ended 
up getting.  First he cuts off 3 tails one at a time.  Which would 
make the dragon end up having 6 tails.  Then he would cut all the 
tails off in double cuts.  Which would make the dragon end up with 6 
heads.  He would then double cut each of them!  That's nine slices,
but I'm not sure if that's the least possible.  Am I right?

Date: 01/15/2007 at 13:24:06
From: Doctor Douglas
Subject: Re: Smallest number of slices

Hi again, Camille.

Well done.  You've found a solution, and now your task is to 
demonstrate that (except for reordering the steps), the solution that
you found is indeed the minimum number of steps.

How could you do that?  Well, you could do the following:  treat the
dragon as a point in the Cartesian plane [hence my earlier hint about
using graph paper], where each point (x,y) represents the "current
condition" or "state" of the dragon:  x = # of heads and y = # of 
tails.  The point Z = (0,0) is of course the final goal of the
knight, starting with the dragon originally at A = (3,3):
    y
    |
  5 + - . - . - . - . - . -
    |   |   |   |   |   |
  4 + - . - . - . - . - . -
    |   |   |   |   |   |
  3 + - . - . - A - . - . -
    |   |   |   |   |   |
  2 + - . - . - . - . - . -
    |   |   |   |   |   |
  1 + - . - . - . - . - . -
    |   |   |   |   |   |
  0 Z - . - . - . - . - . - x
    0   1   2   3   4   5 

Now, what can the knight accomplish with the first cut?  Cutting off
a single head accomplishes nothing--the  cut head is simply regrown
(and wastes a slice).  Other choices lead to the points labeled 
B in the diagram below:
    y
    |
  5 + - . - . - . - . - . -
    |   |   |   |   |   |      This B from a single-tail-cut, after
  4 + - . - . - B - . - . -    regrowing 2 tails, net gain = 1 tail.
    |   |   |   |   |   |      
  3 + - B - . - A - . - . -    After a double-head-whack, nothing is
    |   |   |   |   |   |      regrown, so we move left two spaces.
  2 + - . - . - . - . - . -
    |   |   |   |   |   |
  1 + - . - . - . - B - . -    This B from a double-tail-cut, after
    |   |   |   |   |   |      regrowing one head, net gain = (1,-2).
  0 Z - . - . - . - . - . - x
    0   1   2   3   4   5 

The diagram above shows where the knight starts from (A) and what can 
be accomplished after one slice (B).  Now, you can keep going with the 
next slice--use the letter C to label all of the points that can be 
reached with one slice from any point labeled B.  Here's what we get:

    y
    |
  5 + - . - . - C - . - . -
    |   |   |   |   |   |
  4 + - C - . - B - . - . -
    |   |   |   |   |   |
  3 + - B - . - A - . - . -
    |   |   |   |   |   |
  2 + - . - . - . - C - . -
    |   |   |   |   |   |
  1 + - . - C - . - B - . -
    |   |   |   |   |   |
  0 Z - . - . - . - . - . - x
    0   1   2   3   4   5 

where all the C's indicate what can be accomplished after two 
slices.  We can't move off the left edge or the bottom edge of
the diagram, because that would correspond to a negative number
of heads or tails.  Keep going in this way with points labeled
D, E, and so on, until you have filled in as much of the grid as
possible.  If you find a point is already labeled, then you 
don't need to relabel it, since getting to that point is already
accomplished with fewer steps.

If you are careful, then when you finish you should find that the
origin is first labeled when you use the letter "J".  This will 
be a demonstration that nine steps are both necessary and sufficient,
meaning that nine steps is the minimum.

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/15/2007 at 15:02:20
From: Camille
Subject: Thank you (Smallest number of slices)

Thank you for your helpful advice. It helped me solve the problem much
faster than I would have been able to without.