6
$\begingroup$

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 :( )

$\endgroup$
  • 1
    $\begingroup$ The first guess would be to say $\frac{\sup S}{\gcd (\text{elements of }S)}$. Need a formal proof, though. $\endgroup$ – TZakrevskiy Sep 20 '13 at 23:52
  • $\begingroup$ @TZakrevskiy This is correct. Could you please explain how/why this is your first guess? $\endgroup$ – Alvaro Sep 21 '13 at 0:04
  • $\begingroup$ 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. $\endgroup$ – TZakrevskiy Sep 21 '13 at 0:11
  • $\begingroup$ @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! $\endgroup$ – Alvaro Sep 21 '13 at 0:24
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I was having a little trouble understanding the 0 thing before, I didn't mention that a and b need to be different numbers. I also should have stated that the initial set should have at least 2 numbers. I'll edit my question to make this details clearer. This was very helpful, thanks a lot! $\endgroup$ – Alvaro Sep 21 '13 at 0:22
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Sep 21 '13 at 0:26

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.