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?

No comments:

Post a Comment