Tuesday, October 17, 2006

Fraction Faction. Topic: Inequalities/NT. Level: AIME/Olympiad.

Problem: (2005 Putnam - B2) Find all positive integers $n, k_1, \ldots, k_n$ such that $k_1+\cdots+k_n = 5n-4$ and

$\frac{1}{k_1}+\cdots+\frac{1}{k_n} = 1$.

Solution: First, by the Cauchy-Schwarz Inequality, we find that

$\displaystyle \left(\sum k_i \right)\left(\sum \frac{1}{k_i}\right) \ge n^2 \Rightarrow \sum \frac{1}{k_i} \ge \frac{n^2}{5n-4}$.

For $n > 4$, however, $n^2 > 5n-4 \Rightarrow \sum \frac{1}{k_i} > 1$, which is a contradiction. Hence $n \le 4$. Then we proceed by cases:

CASE 1: $n = 1$

Clearly $k_1 = 1$ is the only solution.

CASE 2: $n = 2$

We have $k_1+k_2 = 6$ so our possible pairs are $(1,5); (2,4); (3,3)$ (and permutations), none of which work.

CASE 3: $n = 3$

We have $k_1+k_2+k_3 = 11$. Notice that $k_i \neq 1$ or the sum of the reciprocals will exceed $1$. So our possible triplets are $(2, 2, 7); (2, 3, 6); (2, 4, 5); (3, 3, 5); (3, 4, 4)$ (and permutations), of which only $(2, 3, 6)$ works.

CASE 4: $n = 4$

Notice that with our use of Cauchy Schwarz above at $n = 4$ we have $\sum \frac{1}{k_i} \ge \frac{n^2}{5n-4} = \frac{16}{16} = 1$, so equality must hold. Hence $k_1 = k_2 = k_3 = k_4 = 4$ is the only solution.

In summary, our solutions are

$n = 1$: $\{1\}$
$n = 3$: $\{2,3,6\}$
$n = 4$: $\{4, 4, 4, 4\}$.

QED.

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

Comment: The only really interesting part of this problem was bounding with Cauchy. After that, it's just manual counting to figure out the solutions. But overall this is a good test of using inequalities to simplify number theory problems.

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

Practice Problem: What if $k_1+\cdots+k_n = 4n-3$?