Arjun Shastry

Ranch Hand

Posts: 1903

1

David Weitzman

Ranch Hand

Posts: 1365

posted 13 years ago

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.

+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: 1903

1

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 13 years ago

OK I agree with David's answer. But what happens if we replace the original numbers with these:

+9, -15, -6, +12

But I assert that the result now is different. This dragon

(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 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 stillOne can cut either 15,17,19, or 5 heads with one blow of sword.For these 24,2,13,17 new heads arise respectively.

+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*

HS Thomas

Ranch Hand

Posts: 3404

posted 13 years ago

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 ]

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

posted 13 years ago

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 ]

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

posted 13 years ago

This

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 ]

*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

posted 13 years ago

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...

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

Jeroen Wenting

Ranch Hand

Posts: 5093

posted 13 years ago

Dragons being intrinsically magical creatures that is a given

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

Posts: 5093

It is sorta covered in the JavaRanch Style Guide. |