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