This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Programming Diversions and the fly likes Can Dragon ever die? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Can Dragon ever die?" Watch "Can Dragon ever die?" New topic
Author

Can Dragon ever die?

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
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?


MH
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
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

Joined: Mar 13, 2003
Posts: 1874
.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

Joined: Jan 30, 2000
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 ]

"I'm not back." - Bill Harding, Twister
David O'Meara
Rancher

Joined: Mar 06, 2001
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

Joined: May 15, 2002
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

Joined: Jul 27, 2001
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

Joined: May 15, 2002
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

Joined: Aug 08, 2003
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

Joined: May 15, 2002
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

Joined: Oct 12, 2000
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


42
Jeroen Wenting
Ranch Hand

Joined: Oct 12, 2000
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

Joined: Dec 01, 2003
Posts: 226
the ISBN (found on Amazon) is
0387982191
Jeroen Wenting
Ranch Hand

Joined: Oct 12, 2000
Posts: 5093
cheers
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
Almost all problems are from Maths Olympiad training camp in Germany!Some of them were also from IMO and RMO/USAMO. .
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Can Dragon ever die?
 
Similar Threads
Death and beyond..
What’s next after touchscreens? Touchless devices.
Restricting access to an object in the same package.
pass by value for static
Most addictive song ever.