返回题库

HMMT 二月 2011 · TEAM1 赛 · 第 13 题

HMMT February 2011 — TEAM1 Round — Problem 13

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. [ 30 ] Given positive integers a and b such that a > b , define a sequence of ordered pairs ( a , b ) for l l nonnegative 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 l integers 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 be j max 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?
解析
  1. [ 30 ] Given positive integers a and b such that a > b , define a sequence of ordered pairs ( a , b ) for l l nonnegative 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 l integers 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 be j max 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 ) for i 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 reverse m m sequence. The pair p is uniquely determined by the choice of k , k , . . . , k , and lowering any k m 0 1 m i lowers the first number of p . Thus, the minimum possible value occurs when all k are equal to m i