返回题库

HMMT 二月 2025 · 冲刺赛 · 第 28 题

HMMT February 2025 — Guts Round — Problem 28

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

题目详情

  1. [14] Let f be a function from nonnegative integers to nonnegative integers such that f (0) = 0 and j k l m 2 m m f ( m ) = f + 2 2 for all positive integers m . Compute f (1) f (2) f (3) f (31)
      • · · · + . 1 · 2 2 · 3 3 · 4 31 · 32 (Here, ⌊ z ⌋ is the greatest integer less than or equal to z , and ⌈ z ⌉ is the least positive integer greater than or equal to z .) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2025, February 15, 2025 — GUTS ROUND Organization Team Team ID# √
解析
  1. [14] Let f be a function from nonnegative integers to nonnegative integers such that f (0) = 0 and j k l m 2 m m f ( m ) = f + 2 2 for all positive integers m . Compute f (1) f (2) f (3) f (31)
      • · · · + . 1 · 2 2 · 3 3 · 4 31 · 32 (Here, ⌊ z ⌋ is the greatest integer less than or equal to z , and ⌈ z ⌉ is the least positive integer greater than or equal to z .) Proposed by: Carlos Rodriguez 341 Answer: 32 Solution 1: For all positive integers n , let ω ( n ) = f ( n ) − f ( n − 1). We claim that ω ( n ) is the largest odd divisor of n for all n > 0. Indeed, for all positive integers k , we have 2 2 ω (2 k ) = f (2 k ) − f (2 k − 1) = f ( k ) + k − ( f ( k − 1) + k ) = f ( k ) − f ( k − 1) = ω ( k ) and 2 2 ω (2 k + 1) = f (2 k + 1) − f (2 k ) = f ( k ) + ( k + 1) − ( f ( k ) + k ) = 2 k + 1 . Inducting on the positive integers implies that ω ( n ) is indeed the largest odd divisor of n . We can now rewrite the sum as ! 31 31 30 X X X f ( n ) f ( n ) f ( n ) f ( n ) − f ( n − 1) f (31) = − = − . n ( n + 1) n n + 1 n 32 n =1 n =1 n =1 Note that by using the original recursive definition, we can compute 2 2 2 2 2 f (31) = 16 + 8 + 4 + 2 + 1 = 341 . f ( n ) − f ( n − 1) ω ( n ) − ν ( n ) ν ( n ) 2 2 Moreover, we also see that = = 2 , where 2 is the largest power of 2 dividing n n n . Thus, our desired sum is ! 31 X 341 341 341 − ν ( n ) − 0 − 1 − 2 − 3 − 4 2 2 − = 16 · 2 + 8 · 2 + 4 · 2 + 2 · 2 + 1 · 2 − = . 32 32 32 n =1 Solution 2: From the original recursion, for all positive integers n , we have 2 f (2 n ) f ( n ) + n f ( n ) n = = + 2 n (2 n + 1) 2 n (2 n + 1) 2 n (2 n + 1) 2(2 n + 1) and 2 f (2 n + 1) f ( n ) + ( n + 1) f ( n ) n + 1 = = + . (2 n + 1)(2 n + 2) (2 n + 1)(2 n + 2) (2 n + 1)(2 n + 2) 2(2 n + 1) Adding these two equations gives f (2 n ) f (2 n + 1) f ( n ) 1
  • = + . 2 n (2 n + 1) (2 n + 1)(2 n + 2) 2 n ( n + 1) 2 P n f ( k ) Thus, if T ( n ) = , we have k =1 k ( k +1) 2 n +1 X f ( k ) T (2 n + 1) = k ( k + 1) k =1 n X f (1) f (2 m ) f (2 m + 1) = + + 1(2) 2 m (2 m + 1) (2 m + 1)(2 m + 2) m =1 n X 1 f ( m ) 1 = + + 2 2 m ( m + 1) 2 m =1 n + 1 1 = + T ( n ) . 2 2 5 21 85 341 Starting from T (1) = 1, we can compute T (3) = , T (7) = , T (15) = , and finally, T (31) = . 4 8 16 32 √