2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

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

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} )$.

$\endgroup$

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.