Empty a peg and marry a Princess (difficult)

[bonanova]

Captain Kirk has landed the Enterprise in your front yard and invites you onto the holodeck, where you meet a King with a beautiful daughter (aren't they all?) The King wishes to give her hand in marriage only to the wisest of her suitors. So he has devised the following test, and you're first in line. (For puzzle solvers of the female persuasion, the King has a handsome prince ... etc. Actually, you are free to write the prologue in the manner that provides the greatest motivation.)

 

On the Princess' vanity table sits a ring holder comprising three vertical pegs, each holding a random positive number of royal rings. (Reminiscent of the old Tower of Hanoi puzzle, but here the objective is different.) You must transfer rings from one peg to another, in discrete steps, with the objective of emptying one of the pegs of all its rings. A step consists of doubling the number of rings on some peg using rings from another peg that initially has at least as many rings as the first. Say the rings on two pegs initially number a and b, respectively, where a is not less than b. After the move, the pegs will have respectively (a - b) and 2b rings. Clearly the winning position occurs when you have two pegs with equal numbers of rings (a=b.) You may make as many moves as you like.

 

Will you have a pleasurable afternoon on the holodeck? If so, how will you empty one of the pegs?

 

By the way, when you go home, the Princess stays on the deck.  

[plasmid]

If you can reach a state where any of the pegs have exactly one ring on them, then you can empty one of the others -- specifically, you can empty whichever of the other pegs has the smallest number of rings.

Label the peg that has one ring X, the peg that has the next smallest number of rings Y (which we'll say has N rings), and the peg with the most rings Z. Write N as a binary number, like 100110 if it were 38. When peg X has 1 ring on it, you look at the first (rightmost) digit of the binary representation of N: if it's a 1 you move a ring from Y to X, and if it's a 0 you move a ring from Z to X. Peg X will now have 2 rings, and you'll know that the rightmost digit of N will be a zero. Now look at the second-to-rightmost digit in N: again if it's a 1 you move 2 rings from Y to X, and if it's a 0 you move 2 rings from Z to X. Then peg X will have 2² rings and you'll know that the two rightmost digits of N are now zero. Just continue that procedure until you've converted all the digits in N to zero. The fact that Z starts off with more rings than Y ensures that you'll be able to fill up X as much as you need to cover every digit in the binary representation of N and convert all the digits to zero.

[bonanova]

If you can reach a state where any of the pegs have exactly one ring on them, then you can empty one of the others -- specifically, you can empty whichever of the other pegs has the smallest number of rings.

Label the peg that has one ring X, the peg that has the next smallest number of rings Y (which we'll say has N rings), and the peg with the most rings Z. Write N as a binary number, like 100110 if it were 38. When peg X has 1 ring on it, you look at the first (rightmost) digit of the binary representation of N: if it's a 1 you move a ring from Y to X, and if it's a 0 you move a ring from Z to X. Peg X will now have 2 rings, and you'll know that the rightmost digit of N will be a zero. Now look at the second-to-rightmost digit in N: again if it's a 1 you move 2 rings from Y to X, and if it's a 0 you move 2 rings from Z to X. Then peg X will have 2² rings and you'll know that the two rightmost digits of N are now zero. Just continue that procedure until you've converted all the digits in N to zero. The fact that Z starts off with more rings than Y ensures that you'll be able to fill up X as much as you need to cover every digit in the binary representation of N and convert all the digits to zero.

 

Nice progress. We now have two conditions that lead to a win.

 

Since the number of rings remains constant, and we do not want an even distribution, there are two different strategies that might work.

[plasmid]

There were two questions posed.

1) Can you clear out a peg?

2) How would you do it?

A little surprisingly, I can answer the second question but not the first.

When you see the initial distribution of rings, count the total number of rings (call it R) and make an equilateral triangle like the one below with R+1 dots on each side. This will serve as a graph, where each possible distribution of rings is represented by one dot -- the number of rings on peg X is represented by the coordinate going vertically, peg Y by the coordinate going from the top to the lower right, and peg Z by the coordinat going from the lower right to lower left. The blue dot in this example is at X=6, Y=5, Z=4. You can work backwards and answer the question: what states could have preceded this so you could reach (6, 5, 4) on the next move? Since each move will double the number of rings on a peg, you just need to look at all of the pegs that have an even number of rings (in this case X and Z) and consider ways that they could have reached that state. If peg X were the one to have rings moved onto it, the state could have been preceeded by (3, 8, 4) if the rings were moved from Y to X or (3, 5, 7) if the rings were moved from Z to X, and those two states are represented by the red dots. If the rings were moved to Z to reach (6, 5, 4), then it could have been preceded by (8, 5, 2) or (5, 7, 2) which are represented by the yellow dots.

Working backwards like this, you can color all of the final solution states red (the states where one of the pegs has zero rings, which is the perimeter of the triangle), and call red "color #0". From each red dot, color every dot that can reach a red dot in one move (and is not already colored red) orange, or "color #1". From each orange dot, find every uncolored dot that could lead to an orange dot in one move and color it yellow, or "color #2". Continuing to do so will either fill the triangle or eventually reach a point where no more uncolored cells can be reached. In this example, I've colored the R=15 trinagle with colors according to the spectral sequence. For any given starting state, if it is colored, then you can reach a solution state on the edge of the triangle within the number of steps corresponding to the color of that state -- simply look at all the states that could follow the current state and move to one whose color number is smaller than the current color number until you reach color #0 on the perimeter. This not only ensures you reach a solution, but that you do so in the minimum number of steps.

[bonanova]

if the are N rings and a colored N-triangle, seems to be solved. no?

That's a nice approach.

[gavinksong]

There were two questions posed.

1) Can you clear out a peg?

2) How would you do it?

A little surprisingly, I can answer the second question but not the first.

When you see the initial distribution of rings, count the total number of rings (call it R) and make an equilateral triangle like the one below with R+1 dots on each side. This will serve as a graph, where each possible distribution of rings is represented by one dot -- the number of rings on peg X is represented by the coordinate going vertically, peg Y by the coordinate going from the top to the lower right, and peg Z by the coordinat going from the lower right to lower left. The blue dot in this example is at X=6, Y=5, Z=4. You can work backwards and answer the question: what states could have preceded this so you could reach (6, 5, 4) on the next move? Since each move will double the number of rings on a peg, you just need to look at all of the pegs that have an even number of rings (in this case X and Z) and consider ways that they could have reached that state. If peg X were the one to have rings moved onto it, the state could have been preceeded by (3, 8, 4) if the rings were moved from Y to X or (3, 5, 7) if the rings were moved from Z to X, and those two states are represented by the red dots. If the rings were moved to Z to reach (6, 5, 4), then it could have been preceded by (8, 5, 2) or (5, 7, 2) which are represented by the yellow dots.

fig1.jpg

Working backwards like this, you can color all of the final solution states red (the states where one of the pegs has zero rings, which is the perimeter of the triangle), and call red "color #0". From each red dot, color every dot that can reach a red dot in one move (and is not already colored red) orange, or "color #1". From each orange dot, find every uncolored dot that could lead to an orange dot in one move and color it yellow, or "color #2". Continuing to do so will either fill the triangle or eventually reach a point where no more uncolored cells can be reached. In this example, I've colored the R=15 trinagle with colors according to the spectral sequence. For any given starting state, if it is colored, then you can reach a solution state on the edge of the triangle within the number of steps corresponding to the color of that state -- simply look at all the states that could follow the current state and move to one whose color number is smaller than the current color number until you reach color #0 on the perimeter. This not only ensures you reach a solution, but that you do so in the minimum number of steps.

fig2.jpg

A programmer's solution.

That's a beautiful triangle.

Bonanova, is this an original puzzle?

I'm not completely convinced that there's always a solution, and I don't think plasmid is either.

Was there another strategy that you had in mind?

[bonanova]

From any starting point a peg can be emptied. I know of two proofs. One that seeks to increase the number of rings on one of the pegs until another peg is empty, another that systematically decreases the rings on one of the pegs, after securing a mild starting position (where exactly one peg has an odd number.)

Agree about plasmid's use of trilinear coordinates, and I think it's a solution, so long as all the elements of arbitrarily large triangles can be given colors. I won't mark it solved until that is clarified.

[bonanova]

In fact, I wonder: Might a close study of the colored triangle disclose an algorithm for moving methodically from one color to the next until red is reached? Or do the triangles for each N differ qualitatively enough that each N would need its own algorithm?

[plasmid]

Suppose you reach a configuration where two of the three pegs have a total of N rings on them where N is a power of 2, that is, N = 2

^x for some integer x. Then by simply continuously moving rings between those two pegs, from whichever one has the most to whichever one has the fewest, you will eventually clear out one of the pegs.

The proof is as follows. Call the number of rings on each peg P and Q, where P<Q. Since there are a total of N = 2^x rings on P and Q, then either P and Q must both be even or must both be odd (else their sum would not be even). Suppose P and Q are both odd - then you would move P rings from Q to P and after that move both P and Q would be even.

Now consider a state where P and Q are both even, whether it's because you initially started in such a state or because you reached it after moving from an odd state. P and Q must now either both be multiples of 4 (2²) or neither be multiples of four because their sum N = 2^x is a multiple of 4. If neither of them are multiples of four (but they are both multiples of 2 because they're even) then you can call them P = 4y+2 and Q = 4z+2, so after moving P rings from Q to P they will have P = 2(4y+2) rings and Q = (4z+2)-(4y+2) = 4z-4y rings, so they will both have multiples of 4.

Now do the same thing considering whether P and Q are both multiples of 8 (2³), and I think you'll be able to see where I'm going with this. Eventually they will have to reach the state where they are both multiples of N/2, so they both have N/2 rings on them and you can clear out a peg in the next move.

Written in triangle notation, if two pegs have a total of 2^x rings between them, those states appear as lines parallel to an axis that become increasingly widely spaced as you get further from a vertex, but will always include at least some of the central inverted triangle occupying 1/4 of the total triangle's area.

[bonanova]

I believe plasmid's line of analysis will lead to a solution.

 

To achieve a degree of closure this year, here is the 2^nd of the two proofs referenced in post 7.

It is much simpler than it first appears. Working an example is the best way to understand it.

 

The puzzle appeared in the 5^th All Soviet Union Mathematical Olympiad, Riga, 1971.

It appeared in modified form on the Putnam Exam in 1993.

I found it in one of Peter Winckler's books (as a water and buckets problem) and adapted it to its present form.

 

The solution described below was found by Svante Janson of Uppsala University, Sweden.

It shows how the rings on one of the pegs can be reduced until it is zero.

 

-bn

Label the pegs A, B, C with initially a, b and c rings, where 0 < a <= b <= c.

We describe a sequence of moves leading to a state where the minimum number

of rings on the three pegs is less than a. If this minimum is 0 we are done.

 

Otherwise we relabel and repeat.

Let b = qa + r, where 0 <= r < a, and q >= 1 is an integer.

Write q in binary form q = q₀ + 2q₁ + ... + 2ⁿq_n where each q_i is 0 or 1, and q_n = 1.

Do n+1 moves, numbered 0,...,n, as follows:

 

In move i we transfer rings

• from B to A if q_i = 1 or
• from C to A if q_i = 0.

Since we always move rings to A, its rings are doubled each time, so A has 2ⁱa rings before the i^th move.

Hence, the total rings moved from B equals qa, so at the end there remains (b - qa) = r < a rings on B.

The total rings moved from C is at most

{SUM _iⁿ₌^-₀¹ 2ⁱa} < 2ⁿa <= qa <= c,

so there will always be enough rings on C (and on B) to make these moves.

 

-SJ