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.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum