Associated Topics || Dr. Math Home || Search Dr. Math

### 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
(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)

faster than I would have been able to without.
```
Associated Topics:
High School Discrete Mathematics
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search