Thursday, March 30, 2006

Zero Has No Friends. Topic: Combinatorics/Inequalities/Sets. Level: Olympiad.

Problem: (360 Problems For Mathematical Contests - 6.1.9) Find the maximum number of nonzero terms of the sum

$ \displaystyle \sum_{i,j=1}^n |f(i)-f(j)| $

where $ f:\{1,2,\ldots,n\} \rightarrow \{a,b,c\} $ is one of the $ 3^n $ possible functions.

Solution: Let $ x $ be the number of elements $ p \in \{1,2,\ldots,n\} $ such that $ f(p) = a $. Similarly define $ y $ and $ z $ to be the corresponding values for $ f(p) = b $ and $ f(p) = c $, respectively. Since there are $ n $ total values in the domain, we know $ x+y+z = n $.

We will try counting the opposite of what we want and minimizing it; the number of pairs such that $ |f(i)-f(j)| = 0 $. The number of ways we can pick two elements that map to $ a $ is $ x^2 $ ($ x $ choices for both the first and second). Similarly, the number that map to $ b $ and $ c $ are $ y^2 $ and $ z^2 $, respectively.

Now it remains to minimize $ x^2+y^2+z^2 $ for $ x+y+z = n $. By Cauchy or AM-GM, we know $ x^2+y^2+z^2 \ge \frac{1}{3}(x+y+z)^2 = \frac{n^2}{3} $. But remember that $ x,y,z $ have to be positive integers, so we have two separate cases: (1) if $ n $ is a multiple of $ 3 $, then the minimum is $ \frac{n^2}{3} $, (2) otherwise, it is $ \frac{n^2+2}{3} $.

So we then subtract the minimum number of zero terms from the total number of terms $ n^2 $ to get $ \frac{2n^2}{3} $ if $ n $ is a multiple of $ 3 $ and $ \frac{2(n^2-1)}{3} $ otherwise. This can also be stated as $ \left\lfloor \frac{2n^2}{3} \right\rfloor $. QED.

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

Comment: It can be a good idea to look at the complement of what you actually are counting because it may be a lot simpler to count. This is a common technique in probability problems as well.

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

Practice Problem: (360 Problems For Mathematical Contests - 6.1.6) Let $ a_1, a_2, \ldots, a_n $ be positive real numbers and let $ k \ge 0 $. Prove that

$ \displaystyle k+\sqrt[n]{\prod_{i=1}^n a_i} \le \sqrt[n]{\prod_{i=1}^n (k+a_i)} \le k +\frac{1}{n} \sum_{i=1}^n a_i $.

No comments:

Post a Comment