# Minimum sum of set whose average of subsets is positive integer

A finite set of positive integers $A$ is called meanly if for each of its nonempty subsets the arithmetic mean of its elements is also a positive integer. In other words, $A$ is meanly if $\frac{1}{k}(a_1 + \dots + a_k)$ is an integer whenever $k \ge 1$ and $a_1, \dots, a_k \in A$ are distinct.

Given a positive integer $n$, what is the least possible sum of the elements of a meanly $n$-element set?

Source: Middle European Math Competition

For motivation, let's do some small ones by hand. For $n=1$, the set can be $\{1\}$ with sum $1$. For $n=2$, we can put $1$ in, but then we can't have $2$, which would give mean $\frac 32$ for the whole set. But $\{1,3\}$ with sum $4$ works. It should be clear that if $n \ge 2$ all the numbers have to have the same parity. For $n=3$, then, we can't use $4$, but $\{1,3,5\}$ with sum $9$ works. But if $n\ge 4$, we can't have all of $1,3,5$, as whatever the fourth element $k$ is, either $\{1,3,k\}$ or $\{1,5,k\}$ will not have an integral mean. The best we can do is $\{1,7,13,19\}$ with sum $40$

This indicates that all the numbers in the set must be equivalent $\pmod {\operatorname{lcm}(1,2,3,\dots n-1)}$ Let $p=\operatorname{lcm}(1,2,3,\dots n-1)$, then our set is $\{1,1+p,1+2p,\dots 1+(n-1)p\}$ with sum $\frac 12np(n-1)+n$

• There is a much cleaner way of explaining it, by showing that $k \mid a_i - a_j$. – Calvin Lin Sep 30 '14 at 1:29
• I believe that the sum should be $1/2 n (n-1) p + n$. – Calvin Lin Sep 30 '14 at 1:35
• @CalvinLin: you are right. – Ross Millikan Sep 30 '14 at 4:26
• First proofs are always rougher. – marty cohen Sep 30 '14 at 5:23

Consider any integer $k < n$

Consider fix any 2 element $a_i, a_j$. Fix any $k-1$ subset $A$ that doesn't contain $a_i$ or $a_j$. Then, by considering $A \cup \{ a_i\}$ and $A \cup \{ a_j \}$, we see that

$$k \mid a_i - a_j$$

Since this holds true for all $k < n$, we get that $LCM ( 1, 2, \ldots, n-1 ) \mid a_i - a_j$.

Let $p = LCM (1, 2, \ldots, n-1)$.

As such, the set with the smallest possible sum will have the form $\{ a, a + x_2 p , a + x_3 p, \ldots a + x_ n p \}$, where $x_i$ is an increasing sequence of positive integers.

We still need that this entire subset is divisible by $n$. As it turns out, we can set $x_i = i -1$, and $a = 1$, which gives us a sum of $n( 1 + \frac{p(n-1)}{2} )$.