HMMT 十一月 2021 · 冲刺赛 · 第 29 题
HMMT November 2021 — Guts Round — Problem 29
题目详情
- [15] Kevin writes down the positive integers 1 , 2 , . . . , 15 on a blackboard. Then, he repeatedly picks two random integers a, b on the blackboard, erases them, and writes down gcd( a, b ) and lcm( a, b ). He does this until he is no longer able to change the set of numbers written on the board. Find the maximum sum of the numbers on the board after this process. 2
解析
- [15] Kevin writes down the positive integers 1 , 2 , . . . , 15 on a blackboard. Then, he repeatedly picks two random integers a, b on the blackboard, erases them, and writes down gcd( a, b ) and lcm( a, b ). He does this until he is no longer able to change the set of numbers written on the board. Find the maximum sum of the numbers on the board after this process. Proposed by: Akash Das Answer: 360864 Solution: Since v (gcd( a, b )) = min( v ( a ) , v ( b )) and v (lcm( a, b )) = max( v ( a ) , v ( b )), we may show p p p p p p the following: Claim. For any prime p and non-negative integer k , the number of numbers n on the board such that v ( n ) = k doesn’t change throughout this process. p Let the 15 final numbers on the board be a ≤ a ≤ a · · · ≤ a . Note that a | a for all i < j . For 1 2 3 15 i j each prime p , let X = v ( a ). Note that by the lemma, we have p,i p i ( X , X , . . . , X ) = (0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 2 , 2 , 3) 2 , 1 2 , 2 2 , 15 ( X , X , . . . , X ) = (0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 2) 3 , 1 3 , 2 3 , 15 ( X , X , . . . , X ) = (0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1) 5 , 1 5 , 2 5 , 15 ( X , X , . . . , X ) = (0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1) 7 , 1 7 , 2 7 , 15 ( X , X , . . . , X ) = (0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1) 11 , 1 11 , 2 11 , 15 ( X , X , . . . , X ) = (0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1) 13 , 1 13 , 2 13 , 15 ∏ X p,i Thus, since a = p for each i , so we get the 15 final numbers on the board are i p 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 2 , 2 , 6 , 6 , 60 , 420 , and 360360 . Adding these up gives 360854. 2