HMMT 十一月 2021 · THM 赛 · 第 9 题
HMMT November 2021 — THM Round — Problem 9
题目详情
- Let n be the answer to this problem. Find the minimum number of colors needed to color the divisors of ( n − 24)! such that no two distinct divisors s, t of the same color satisfy s | t .
解析
- Let n be the answer to this problem. Find the minimum number of colors needed to color the divisors of ( n − 24)! such that no two distinct divisors s, t of the same color satisfy s | t . Proposed by: Sean Li Answer: 50 Solution: We first answer the following question. Find the minimum number of colors needed to color the divisors of m such that no two distinct divisors s, t of the same color satisfy s | t . e e 1 k Prime factorize m = p . . . p . Note that the elements 1 k 2 e 1 1 , p , p , . . . , p , 1 1 1 e e e e 2 1 1 1 2 p p , p p , . . . , p p 2 1 1 2 1 2 e e e e e e e 2 1 2 1 2 1 2 3 p p p , p p p , . . . , p p p 3 3 1 2 1 2 1 2 3 . . . e e e e k − 1 e k − 1 2 e k − 1 e 1 1 1 k p . . . p p , p . . . p p , . . . , p . . . p p k 1 1 k 1 k − 1 k − 1 k − 1 k must be pairwise different colors. Hence, we need at least 1 + e + · · · + e colors. This is also sufficient: 1 k ∑ number the colors 1 , 2 , . . . , 1 + e + · · · + e , and color the divisor s with color 1 + ν ( s ). Thus, 1 k p p prime the answer to the above question is c ( m ) := 1 + e + · · · + e . 1 k Now, we return to the original problem. We wish to find the integer n for which c (( n − 24)!) = n , or c (( n − 24)!) − ( n − 24) = 24. Let f ( k ) = c ( k !) − k , so that we want to solve f ( n − 24) = 24. Note that f (1) = 0, while for k > 1 we have f ( k ) − f ( k − 1) = c ( k !) − c (( k − 1)!) − 1 = Ω( k ) − 1, where Ω( k ) is the number of prime factors of k with multiplicity. k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Ω( k ) 1 1 2 1 2 1 3 2 2 1 3 1 2 2 4 f ( k ) 0 0 0 1 1 2 2 4 5 6 6 8 8 9 10 13 k 17 18 19 20 21 22 23 24 25 26 27 Ω( k ) 1 3 1 3 2 2 1 4 2 2 3 f ( k ) 13 15 15 17 18 19 19 22 23 24 26 Therefore n − 24 = 26 and n = 50.