Here is a game: There is a list of distinct numbers. At any round, a player arbitrarily chooses two numbers $a, b$ from the list and generates a new number $c$ by subtracting the smaller number from the larger one. The numbers $a$ and $b$ are put back in the list. If the number $c$ is non-zero and is not yet in the list, $c$ is added to the list. The player is allowed to play as many rounds as the player wants. The score of a player at the end is the size of the final list.

Suppose at the beginning of the game the list contains the following numbers: $48, 99, 120, 165$ and $273$. What is the score of the best player for this game?

My questions are:

1) What should be my approach to start solving this puzzle? How can I model this problem with Mathematics?

2) Can we write an algorithm for this problem for any numbers in general?

  • $\begingroup$ Distinct numbers implies that $c$ cannot be zero unless it is allowed that $a=b$. Is that indeed allowed? $\endgroup$ – drhab Jan 27 '14 at 15:04
  • $\begingroup$ No. Numbers should remain distinct throughout the whole process. And so that, $0$ cannot be the part of the list ever. And neither two same numbers can be there in the list at any moment of time. I didn't get your last question. $\endgroup$ – Nimit Jan 27 '14 at 15:07

It is clear that we can't get any number higher than the highest number in the list (called $M$ here). Furthermore, you can't get any number lower than the gcd (called $G$ here) of the elements in the list. As a conclusion, with optimal play, you will have $\frac{M}{G}$ elements in your list at the end. (I assume that all numbers are different in the initial list). In order to achieve that :

  1. Calculate $G_{1}$, the gcd of the 2 first elements $e_{1}$ and $e_{2}$ by doing Euclid's algorithm. It will give you a way to get $G_{1}$ with substractions. Then calculate $G_{2} = gcd(G_{1}, e_{3})$ and generate $G_{2}$ in your list the same way you got $G_{1}$. Do it for all the numbers in the list (you can stop if you get to $1$) The final number will be $G$.
  2. Substract $G$ to $M$, then to $M-G$...

Short proof : suppose you can get more elements than $\frac{M}{G}$. Then you will have at least 2 elements $A$ and $B$ such as $|A-B| < G$. The gcd of the final list would then be strictly inferior to the one of the initial list, whereas it should be the same (this is the basis of Euclid's algorithm). So by contradiction, it is impossible. Furthermore, I have given you a way to get $\frac{M}{G}$. So this is the maximum, and it is always doable.

  • $\begingroup$ Alright: for the given list, the smallest gcd for the list comes out to be $3$ and the largest number is $273$. And I guess it should be $M/G$ instead of $G/M$. $273/3$ gives $91$. Is this the answer? I mean have I interpreted correctly? And if yes, can you please explain with proof that why/how this happens? $\endgroup$ – Nimit Jan 27 '14 at 15:18
  • $\begingroup$ I have edited some mistakes, it should be correct now. $\endgroup$ – Traklon Jan 27 '14 at 15:20
  • $\begingroup$ Yes, but you should take the gcd of the whole list, not the smallest pariwise gcd. But 91 is the result here. $\endgroup$ – Traklon Jan 27 '14 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.