Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!

# Can Dragon ever die?

Arjun Shastry
Ranch Hand
Posts: 1898
1
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?

David Weitzman
Ranch Hand
Posts: 1365
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
Posts: 1898
1
.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 ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
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 ]

David O'Meara
Rancher
Posts: 13459
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

HS Thomas
Ranch Hand
Posts: 3404
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
Posts: 1365
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
Posts: 3404
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 ]

Ray Stojonic
Ranch Hand
Posts: 326
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
Posts: 3404

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 ]

Jeroen Wenting
Ranch Hand
Posts: 5093
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

Jeroen Wenting
Ranch Hand
Posts: 5093
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]

ISBN please? (German version is OK if not better)

Timmy Marks
Ranch Hand
Posts: 226
the ISBN (found on Amazon) is
0387982191

Jeroen Wenting
Ranch Hand
Posts: 5093
cheers

Arjun Shastry
Ranch Hand
Posts: 1898
1
Almost all problems are from Maths Olympiad training camp in Germany!Some of them were also from IMO and RMO/USAMO. .