HMMT 十一月 2008 · 团队赛 · 第 6 题

英文解析

6. Now, using information from problems 4 and 5, prove that the following method to decomposeany positive rational number will always terminate:
   a 1
   Step 1. Start with the fraction . Let t be the largest unit fraction which is less than orb n 1
   equal to .ab
   Step 2. If we have already chosen t through t , and if t + t + . . . + t is still less than , thena
   1 k 1 2 kblet t be the largest unit fraction less than both t and .ak +1 k
   Step 3. If t + . . . + t equals , the decomposition is found. Otherwise, repeat step 2.ab
   1 k +1
   Why does this method never result in an infinite sequence of t ?bia aak k
   Solution: Let = − t − . . . − t , where is a fraction in simplest terms. Initially, thisk 1
   b b bk k
   1 1 1 akalgorithm will have t = 1, t = , t = , etc. until < . This will eventually happen
   1 2 3
   2 3 b k +1
   1 1 akkby problem 5, since there exists a k such that + . . . + > . At that point, there is
   1 k +1 bk
   1 1 1 1 aksome n with < t such that > > . In this case, t = .
   k k +1
   n n b n +1 n +1
   1 1 1 akk
   Suppose that there exists n such that > > for some k . Then we have t =
   k k +1
   n b n +1 n +1
   k k k kak +1 1 1 1 akand < . This shows that once we have found n such that > > andkb n ( n +1) n b n +1
   k +1 k k k k k
   1 1 1
   ≤ t , we no longer have to worry about t being less than t , since t = < <
   k k +1 k k +1
   n n +1 nk k k
   1 1
   t , and also n ≥ n ( n + 1) while ≤ = t .
   k k +1 k k k +1
   n ( n +1) n +1
   k k k
   On the other hand, once we have found such an n , the sequence { a } must be decreasingk kby problem 4. Since the a are all integers, we eventually have to get to 0 (as there is nokinfinite decreasing sequence of positive integers). Therefore, after some finite number of stepsaa akthe algorithm terminates with a = 0, so 0 = = − t − . . . − t , so = t + . . . + t ,
   k +1 1 k 1 kb b bwhich is what we wanted.k
   Juicy Numbers [ 100 ]2
   A juicy number is an integer j > 1 for which there is a sequence a < a < . . . < a of positive
   1 2 kintegers such that a = j and such that the sum of the reciprocals of all the a is 1. For example,
   1 1 1 ki
   6 is a juicy number because + + = 1, but 2 is not juicy.
   2 3 6
   In this part, you will investigate some of the properties of juicy numbers. Remember that ifyou do not solve a question, you can still use its result on later questions.