Philippine Mathematical Olympiad Area Stage

Solution:

First, we show that $6 \leq |A| \leq 13$. To do this, we show that if $|A| = n$, then $2n-1 \leq |A-A| \leq n(n-1)+1$. The upper bound is easily attained; the number of distinct differences is bounded above by the number of ordered pairs $(a, b)$ of distinct elements of $A$ plus 1, to account for the remaining pairs $(a, a)$ which give a difference of $0$; this is exactly $n(n-1)+1$.

For the lower bound, suppose that $A = \{ a_1, a_2, \ldots, a_n \}$ with $a_1 < a_2 < \cdots < a_n$. Then the $n-1$ differences $a_n - a_1, a_n - a_2, \ldots, a_n - a_{n-1}$ are all positive and distinct and appear in $A-A$; their additive inverses are all negative and distinct and also appear in $A-A$. Also, $0 \in A-A$ and $0$ is not among those differences previously listed. This gives us at least $2(n-1)+1 = 2n-1$ differences in $A-A$. These bounds show us that if $|A-A| = 25$, we must have $6 \leq |A| \leq 13$ as desired.

We then show that for any $n$ with $6 \leq n \leq 13$, there exists a set $A$ such that $|A| = n$ and $|A-A| = 25$. Consider now the sets $B = \{ 1, 2, 4, 8, 12, 13 \}$ and $C = \{ 1, 2, \ldots, 13 \}$. Then we have $|B| = 6$, $|C| = 13$, $B \subseteq C$, and $B-B = C-C = \{ -12, -11, \ldots, 0, \ldots, 11, 12 \}$. Now, for any set $A$ with $B \subseteq A \subseteq C$, we have $B-B \subseteq A-A \subseteq C-C$, and so we must have $A-A = B-B = C-C$. For any $n$ with $6 \leq n \leq 13$, it is always possible to choose $A$ such that $|A| = n$ and $B \subseteq A \subseteq C$, and this will give us the desired $A$.

Thus, the sum of all possible values of $|A|$ is $6 + 7 + \cdots + 13 = 76$.