# Number of elements in the resulting set of “subtraction game”

You have the following game:

You start with a set $S$ with a number $n$ of positive integer elements, $n \ge 2$. At each step, you add to the set any new number $i$, as long as $i = |a-b|$ and $a$ and $b$ already belong to the set, $a \neq b$. Repeat this until no more new numbers can be added to the set.

Now, given a initial set $S$, how can you calculate the number of members of the set after the game is over? (Assume you will add all possible elements).

Some background on the question:
I know this sounds like homework, but it's not. The question appeared after solving a problem in codeforces, a programming competition website - http://codeforces.com/problemset/problem/346/A (The contest in which this problem appeared is over and now you are allowed to discuss it :)
I managed to solve the problem and get my solution accepted on the website, therefore I already know the formula that answers this question. The problem is: it was just a guess. Although I've tried a lot to devise some reasoning that would lead me to the answer, I could not. So I am more interested in how do you arrive to the solution, rather than the solution itself.
(Also, I thought about asking "how do you prove that the final number of elements is equal the formula", but the reasoning required to achieve this would be different, although I couldn't prove it too :( )

• The first guess would be to say $\frac{\sup S}{\gcd (\text{elements of }S)}$. Need a formal proof, though. – TZakrevskiy Sep 20 '13 at 23:52
• @TZakrevskiy This is correct. Could you please explain how/why this is your first guess? – Alvaro Sep 21 '13 at 0:04
• I played this game starting with $\{5,7\}$, $\{5,6\}$, and $\{4,6\}$, saw that in the first two cases we are bound to obtain $1$ and in the last case the smallest number we can obtain is the $\gcd$, made a hypothesis. The proof by @André Nicolas pretty much summarises my reasoning. – TZakrevskiy Sep 21 '13 at 0:11
• @TZakrevskiy I see, this is kinda how I got to this hypothesis too, except that it took me hours to do it :'( Thanks for the insight! – Alvaro Sep 21 '13 at 0:24

If our set $S$ has one element, clearly the answer is $1$. Now suppose that $S$ has $\ge 2$ elements.
If the greatest common divisor of the numbers in $S$ is greater than $1$, divide number in $S$ by this gcd. Let the resulting set of positive integers be $A$. Let $m$ be the largest of the numbers in $A$. Then $m$ turns out to be the answer.
The reason is that given any two positive integers $a_1$ and $a_2$ in $A$, then by repeated "absolute value" subtraction we can obtain the gcd of the two numbers. This is a primitive no-division version of the Euclidean Algorithm.
Call this gcd $d_1$. By repeated subtraction we can obtain the gcd $d_2$ of $d_1$ and $a_3$. And so on. After a while, we obtain the gcd of all the numbers in $A$, which is $1$. Now that we have $1$ we can get all the positive integers $\le m$. It is clear that we cannot get any more.
• You are welcome. The $0$ thing was a little silly of me. It was just to take care of singletons. I was worried gcd would not have a clear meaning to you in that case. – André Nicolas Sep 21 '13 at 0:26