HMMT 二月 2011 · TEAM1 赛 · 第 13 题

英文解析

13. [ 30 ] Given positive integers a and b such that a > b , define a sequence of ordered pairs ( a , b ) forl lnonnegative integers l by a = a , b = b , and ( a , b ) = ( b , a mod b ), where, for all positive
    0 0 l +1 l +1 l l lintegers x and y , x mod y is defined to be the remainder left by x upon division by y . Define f ( a, b )
    to be the smallest positive integer j such that b = 0. Given a positive integer n , define g ( n ) to bejmax f ( n, k ).
    1 ≤ k ≤ n − 1
    (a) [ 15 ] Given a positive integer m , what is the smallest positive integer n such that g ( n ) = m ?
    m m
    (b) [ 15 ] What is the second smallest?
    Solution:
    (a) The answer is F , where F = 1, F = 2, and F = F + F for all i ≥ 2.
    m +1 1 2 i +1 i i − 1
    We consider a reverse sequence as follows: starting at p = ( k , 0) for some positive integer k ,
    0 0 0
    at each step we can take a pair p = ( r , s ) to any pair p = ( s + k r , r ) = ( r , s ) fori i i i +1 i i +1 i i i +1 i +1
    some positive integer k . It is clear that any such sequence is the reverse of a legal sequence.
    i +1
    Thus, n is equal to the smallest possible value of the first integer in a possible p of a reversem msequence. The pair p is uniquely determined by the choice of k , k , . . . , k , and lowering any km 0 1 m ilowers the first number of p . Thus, the minimum possible value occurs when all k are equal tom i