OLYMPIAD CHALLENGE 3/320: "(a) N rings having different outer diameters are slipped into an upright peg, the largest ring on the bottom, to form a pyramid. We wish to transfer all of the rings, one at a time, to a second peg, but we have a third (auxiliary) peg at our disposal. During the transfers it is not permitted to place a larger ring on a smaller one. What is the smallest number, k, of moves necessary to complete the transfer to peg number 2?"

Question

mendicant_bias · Answer

@ganeshie8

mendicant_bias · Answer

(Don't feel like I *need* this answered or anything, heh, just posted it as a curiosity)

ganeshie8 · Answer

towers of hanoi ! this is a cool+hard problem

mendicant_bias · Answer

Yeah, I knew I've seen it somewhere before.

jtvatsim · Answer

I'm running out of lids...

mendicant_bias · Answer

I think the most efficient thing would be-LOL

mendicant_bias · Answer

I think the most efficient thing to do would be like, placing the entire stack on the middle/intended/"final" peg, and then splitting the stack in nearly two on the left and right peg, and then doing something like alternating on and off, I'm not sure.

jtvatsim · Answer

problem being that you can only move one ring at a time

mendicant_bias · Answer

But either way, I have no idea how to mathematically prove it, and exhaustion seems like a silly method; there has to be a more elegant way to do this. You can only move one ring at a time? I misinterpreted the prompt.

jtvatsim · Answer

Yeah, otherwise you can just pick the whole stack up and place it on the middle peg (the goal) k = 1 move for all N.

mendicant_bias · Answer

There's something else I'm imagining that I'm failing to describe, lol, method-wise.

mendicant_bias · Answer

You can move the other stacks/not the primary stacks, with multipe rings, though, right? Like if you have two rings on the intended or auxiliary pole, you're allowed to move all of those at once, yes? Otherwise this literally seems impossible to me, unless

jtvatsim · Answer

I don't think so. But with the condition that we can place smaller on top of larger rings, it is possible.
Three rings takes 7 moves to complete for me.

mendicant_bias · Answer

Yeah, this was the "unless"; and yeah, I can figure out how to do it with so many iterations, but I have no idea how to *prove* that with math.

jtvatsim · Answer

Yeah, we know that there has to be a connection to the larger/smaller, so there has to be a pattern, it just will be tough to find.

mendicant_bias · Answer

What we can do is figure out a pattern dependent on N at the very least, and describe it as a series term. Like you said, with three rings, it takes seven moves. How about two, and four?

mendicant_bias · Answer

(Has no lids, is having to imagine, lol)

jtvatsim · Answer

(switched to flash cards...) lol

jtvatsim · Answer

(N,k) = (1,1)   (2, 3)    (3, 7)    (4, 17)   <--- this one is questionable...

mendicant_bias · Answer

You did that really quickly, lol...

jtvatsim · Answer

I was making a bit of a list...

jtvatsim · Answer

Now, I can't reproduce the N = 4 one... lol

jtvatsim · Answer

OK, I think its (4,15)

jtvatsim · Answer

Obviously, this can't continue :)

mendicant_bias · Answer

I'm on track behind you trying to visualize it.

I think it can continue in that it's possible, but I'd rather not, hah. We can just find out from here. I'm trying to double-check your 4-15 mentally atm, not too far from you.

mendicant_bias · Answer

We still need to solve the actual problem, though.