HMMT 十一月 2008 · 团队赛 · 第 6 题
HMMT November 2008 — Team Round — Problem 6
题目详情
- Now, using information from problems 4 and 5, prove that the following method to decompose any 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 or 1 b n a equal to . b a Step 2. If we have already chosen t through t , and if t + t + . . . + t is still less than , then 1 1 2 k k b a let t be the largest unit fraction less than both t and . k +1 k b 1 a Step 3. If t + . . . + t equals , the decomposition is found. Otherwise, repeat step 2. 1 k +1 b Why does this method never result in an infinite sequence of t ? i Juicy Numbers [ 100 ] A juicy number is an integer j > 1 for which there is a sequence a < a < . . . < a of positive 1 2 k integers such that a = j and such that the sum of the reciprocals of all the a is 1. For example, i k 1 1 1 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 if you do not solve a question, you can still use its result on later questions.
解析
- Now, using information from problems 4 and 5, prove that the following method to decompose any 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 or 1 b n a equal to . b a Step 2. If we have already chosen t through t , and if t + t + . . . + t is still less than , then 1 k 1 2 k b a let t be the largest unit fraction less than both t and . k +1 k b a Step 3. If t + . . . + t equals , the decomposition is found. Otherwise, repeat step 2. 1 k +1 b Why does this method never result in an infinite sequence of t ? i a a a k k Solution: Let = − t − . . . − t , where is a fraction in simplest terms. Initially, this 1 k b b b k k a 1 1 1 k algorithm will have t = 1, t = , t = , etc. until < . This will eventually happen 1 2 3 2 3 b k +1 k a 1 1 k by problem 5, since there exists a k such that + . . . + > . At that point, there is 1 k +1 b k a 1 1 1 1 k some n with < t such that > > . In this case, t = . k k +1 n n b n +1 n +1 k a 1 1 1 k 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 k a a k +1 1 1 1 k and < . This shows that once we have found n such that > > and k b 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 n k 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 decreasing k k by problem 4. Since the a are all integers, we eventually have to get to 0 (as there is no k infinite decreasing sequence of positive integers). Therefore, after some finite number of steps a a a k the algorithm terminates with a = 0, so 0 = = − t − . . . − t , so = t + . . . + t , k +1 1 k 1 k b b b k which is what we wanted. 2 Juicy Numbers [ 100 ] A juicy number is an integer j > 1 for which there is a sequence a < a < . . . < a of positive 1 2 k integers such that a = j and such that the sum of the reciprocals of all the a is 1. For example, i k 1 1 1 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 if you do not solve a question, you can still use its result on later questions.