Mike's Magical Scale

[BMAD]

Mike has a magic scale, each side of which holds a positive integer. He plays the following game: each turn, he chooses a positive integer n. He then adds n to the number on the left side of the scale, and multiplies by n the number on the right side of the scale. (For example, if the turn starts with 4 on the left and 6 on the right, and Mike chooses n = 3, then the turn ends with 7 on the left and 18 on the right.) Mike wins if he can make both sides of the scale equal. Show that if the game starts with the left scale holding 17 and the right scale holding 5, then Mike can win the game in 4 or fewer turns.

[Barcallica]

1, 1, 1, 5

That answer works. Is there a shorter answer, one that uses less numbers?

I don't think so. 5,1,1,1 also works. I think these are the only solutions

[Barcallica]

1, 1, 1, 5

[BMAD]

1, 1, 1, 5

That answer works. Is there a shorter answer, one that uses less numbers?

[superprismatic]

1, 1, 1, 5

That answer works. Is there a shorter answer, one that uses less numbers?

I don't think so. 5,1,1,1 also works. I think these are the only solutions

There are two others: 1,5,1,1 and 1,1,5,1.

[BMAD]

1, 1, 1, 5

That answer works. Is there a shorter answer, one that uses less numbers?

I don't think so. 5,1,1,1 also works. I think these are the only solutions

There are two others: 1,5,1,1 and 1,1,5,1.

But is there a three number solution?

[superprismatic]

1, 1, 1, 5

That answer works. Is there a shorter answer, one that uses less numbers?

I don't think so. 5,1,1,1 also works. I think these are the only solutions

There are two others: 1,5,1,1 and 1,1,5,1.

But is there a three number solution?

No

[Pickett]

I proved programmatically that for n < 5000, there are no 3 move solutions...for n < 50000 there are no 2 move solutions...and for n < 500000 there are no 1 move solutions...and for n < 500, the only 4 move solutions are:

1,1,1,5

1,1,5,1

1,5,1,1

5,1,1,1

Plus, once you get into higher numbers you can prove that the right hand side of the scale is going to simply grow faster and faster (since it's multiplication and the left side is addition)...So there really is no need to test with n higher than what I have already done...

[Pickett]

I actually also don't even see any 5, 6, or 7 move solutions (although with 7 moves, I only validated with n < 10...since my algorithm is extremely inefficient...)...so I'm starting to think that the ONLY solutions to this are the 4 move solutions presented.

[BMAD]

Bonus points for Pickett though for awesome programming talents!

[Nins_Leprechaun]

I actually also don't even see any 5, 6, or 7 move solutions (although with 7 moves, I only validated with n < 10...since my algorithm is extremely inefficient...)...so I'm starting to think that the ONLY solutions to this are the 4 move solutions presented.

There will be solutions with a greater number of moves stretching to infinity.

For fun I came up with what I believe to be a complete generic solution for when n moves will have a solution.

n=x*(5*y+4)+t

Where x>=1 y>=0 and t has a value dependent on y as follows

if y=1 or y=2 then t=10

if y=0 then t=0

if y=3 then t=19

if y>=4 then t=(y-4)*4

Edited June 15, 2013 by Nins_Leprechaun