Tuesday, October 24, 2006

As It Goes. Topic: Sets. Level: AIME.

Problem: (1992 Putnam - B1) Let $S$ be a set of $n$ distinct real numbers. Let $A_s$ be the set of numbers that occur as averages of two distinct elements of $S$. For a given $n \ge 2$, what is the smallest possible number of elements in $A_s$?

Solution: We claim that $|A_s| \ge 2n-3$. To show this, let the elements of $S$ be $a_1 < a_2 < \cdots < a_n$. We can easily see that

$\frac{a_1+a_2}{2} < \frac{a_1+a_3}{2} < \cdots < \frac{a_1+a_n}{2}$,

giving us $n-1$ distinct elements of $A_s$. Furthermore,

$\frac{a_1+a_n}{2} < \frac{a_2+a_n}{2} < \cdots < \frac{a_{n-1}+a_n}{2}$,

giving us an additional $n-2$ distinct elements of $A_s$ for a total of $2n-3$ elements. For any $n \ge 2$, the set $S = \{1, 2, \ldots, n\}$ gives $A_s = \{1.5, 2, 2.5, \ldots, n-0.5\}$, which has precisely $2n-3$ elements. QED.

--------------------

Comment: A good strategy for solving minima/maxima problems (inequalities, too) is to find a case which you think may be a minimum/maximum and try to prove it. In this case, you can guess that the set $\{1, 2, \ldots, n\}$ gives the minimum number of distinct average elements and try to find that many distinct elements in an arbitrary set, as shown above through ordering.

--------------------

Practice Problem: What if you consider the average of three elements?