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

1 comment:

  1. http://www.adobeandteardrops.com/2015/06/thee-faction-reading-writing-revolution.html?showComment=1562228818934#c37100540026031762

    ReplyDelete