Dragon has 100 heads.One can cut either 15,17,20 or 5 heads with one blow of sword.For these 24,2,14,17 new heads arise respectively.Dragon dies only when there are no headson shoulders.Can dragon ever die?
If we ignore the question of whether the moves are legal at a given time, the cutting off and growing back evens out so that the head count can change by the following deltas: +9, -15, -6, +12. These numbers are all multiples of three, and thus any linear combination of them will have to be a multiple of three. We're looking for a combination that adds up to -100. This is impossible since -100 isn't a multiple of 3. Anyone attempting to slay the dragon will be roasted.
Arjun Shastry
Ranch Hand
Joined: Mar 13, 2003
Posts: 1861
posted
0
.Happy new year.12Hours 41 minutes to go. I took this again from Problem Solving Strategies(Springer Verlag)Problem book in Mathematics. [ December 30, 2003: Message edited by: Capablanca Kepler ] [ December 30, 2003: Message edited by: Capablanca Kepler ]
OK I agree with David's answer. But what happens if we replace the original numbers with these:
One can cut either 15,17,19, or 5 heads with one blow of sword.For these 24,2,13,17 new heads arise respectively.
I just altered two of the numbers, in bold. It would seem that most of David's anaysis would remain unchanged here. The net deltas are still +9, -15, -6, +12 But I assert that the result now is different. This dragon can be killed. Why? Or how? (I will probably be away from the internet for the next few days, but will revisit this thread eventually. You won't escape me that easily.) Happy New Year, puzzle fans... [ December 30, 2003: Message edited by: Jim Yingst ]
Reponse to Jim: You can now cut off 81 heads (multiple of 3) then cut the last 19 and the dragon will die. The 13 heads won't come back after the dragon is killed. Unless it's a magic dragon
Cut off 17 heads 7 times in quick succession and the remaining 5 in one fell swoop. One very beheaded dragon. No that leaves 17 which when cut off leaves 2. A 2 headed dragon. Cutting off 2 heads doesn't give rise to new heads so Dragon dies! [ December 31, 2003: Message edited by: HS Thomas ]
David Weitzman
Ranch Hand
Joined: Jul 27, 2001
Posts: 1365
posted
0
Ah, the joy of careless errors. There's a reason I'm a computer scientist and not a mathematician . We're looking for linear combinations that leave us at 15, 17, 20, or 5 rather than 0. Suppose we generalize the question format: Given a set of operations in the form {cutoff, delta} where an operation can only be performed on a number greater than or equal to cutoff and returns the value of the argument increased (or decreased) by delta, does there exist a composition of operations F such that F(0) is a member of a set of valid outputs? How does one programatically determine if a given problem is solvable and what the solution is? The case where all deltas are negative can be exhaustively searched. When there are positive deltas, it should be possible to restrict the search space using some knowledge of modular arithmetic and also do an exhaustive search. I'm wondering if it's possible to do something more efficient using Extended Euclid's algorithm though. The catch is both "greater than or equal to -cutoff" part and that standard Extended Euclid's may return negative coefficients while these operations are only one way. [ January 01, 2004: Message edited by: David Weitzman ]
HS Thomas
Ranch Hand
Joined: May 15, 2002
Posts: 3404
posted
0
This may be similar to this problem: Seven cups upside on a table. Try to right all cups by turning 4 cups at a time. Can it be done ? OR try and right all by turning 3 cups at a time. With turning 4 cups at a time , after a few turning sequences you have 4 cups in any one position and 3 cups in the other and these numbers repeat constantly. With turning 3 cups at a time, after a few turn sequences you have 5 cups in any position and 2 in the other.And these numbers repeat constantly. Ignore this if it confuses. It's an attempt to look for a similar simpler (?) problem. [ January 01, 2004: Message edited by: HS Thomas ]
Intrigued by the cup turning, for whatever reason, I wrote a little program. Suprisingly, it found that the 7 cups, choose 3 could be solved. It takes the program 127 tries to right all cups (on average), but I found it can be done in 3 steps. (parens designate the cups about to be flipped)
yeah, it's off topic...
HS Thomas
Ranch Hand
Joined: May 15, 2002
Posts: 3404
posted
0
I can't imagine why I thought it was similar to the main problem . Unless these are magic cups that flip themselves back under certain conditions.. [ January 06, 2004: Message edited by: HS Thomas ]
Originally posted by David O'Meara: Reponse to Jim: You can now cut off 81 heads (multiple of 3) then cut the last 19 and the dragon will die. The 13 heads won't come back after the dragon is killed. Unless it's a magic dragon
Dragons being intrinsically magical creatures that is a given
42
Jeroen Wenting
Ranch Hand
Joined: Oct 12, 2000
Posts: 5093
posted
0
Originally posted by Capablanca Kepler: [QB] .Happy new year.12Hours 41 minutes to go. I took this again from Problem Solving Strategies(Springer Verlag)Problem book in Mathematics. [QB]
0
.
