Maximum score for the game

Question

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?

Answer 1

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.