HMMT 二月 2026 · ALGNT 赛 · 第 6 题
HMMT February 2026 — ALGNT Round — Problem 6
题目详情
- The numbers 1 , 2 , . . . , 2100 are written on a board. Every second, Mark takes two numbers on the board, a and b , erases them, and replaces them with gcd( a, b ) and lcm( a, b ) . Mark stops once any move he makes will not change the numbers written on the board. Compute the number of divisors of the 2026 th smallest positive integer written on the board when he finishes.
解析
- The numbers 1 , 2 , . . . , 2100 are written on a board. Every second, Mark takes two numbers on the board, a and b , erases them, and replaces them with gcd( a, b ) and lcm( a, b ) . Mark stops once any move he makes will not change the numbers written on the board. Compute the number of divisors of the 2026 th smallest positive integer written on the board when he finishes. Proposed by: Rishabh Das Answer: 3840 Solution: Let p < 2100 be a prime number. Consider the largest power of p dividing a positive integer n in the sequence (we’ll call this the ν value of n , denoted ν ( n ) ). For a fixed p , performing p p an operation on two numbers a and b preserves the ν values of the numbers. Indeed, ν (gcd( a, b )) = p p min( ν ( a ) , ν ( b )) and ν (lcm( a, b )) = max( ν ( a ) , ν ( b )) , so we always have p p p p p { ν ( a ) , ν ( b ) } = { ν (gcd( a, b )) , ν (lcm( a, b )) } . p p p p Therefore, the multiset of ν values for the entire sequence never changes. Moreover, when Mark p finishes, if the numbers on the board are a ≤ a ≤ · · · ≤ a , then we must have a | a for all 1 2 2100 i i +1 1 ≤ i < 2100 , or else we would be able to perform an operation on a and a . Thus, when Mark i i +1 finishes, we have ν ( a ) ≤ ν ( a ) ≤ · · · ≤ ν ( a ) p 1 p 2 p 2100 for all primes p . Combining this with the fact that the multiset of ν values doesn’t change under p operations, we can conclude that the sequence ν ( a ) , ν ( a ) , . . . , ν ( a ) is the multiset of ν in the p 1 p 2 p 2100 p beginning arranged in nondecreasing order. Now, we want to compute a , or the 75 th largest number when Mark finishes. Since the ν values 2026 p k are sorted, we have that p divides a if and only if there exist at least 75 numbers in the sequence 2026 k k k divisible by p . This is equivalent to 2100 /p ≥ 75 , or p ≤ 28 . Hence, the prime powers that divide 4 3 2 a are 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 . Thus 2026 4 3 2 a = 2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 , 2026 6 which has (4 + 1)(3 + 1)(2 + 1)(1 + 1) = 3840 divisors.