HMMT 十一月 2022 · GEN 赛 · 第 9 题
HMMT November 2022 — GEN Round — Problem 9
题目详情
- Call a positive integer n quixotic if the value of 1 1 1 1 lcm(1 , 2 , 3 , . . . , n ) · + + + . . . + 1 2 3 n is divisible by 45 . Compute the tenth smallest quixotic integer.
解析
- Call a positive integer n quixotic if the value of 1 1 1 1 lcm(1 , 2 , 3 , . . . , n ) · + + + . . . + 1 2 3 n is divisible by 45 . Compute the tenth smallest quixotic integer. Proposed by: Vidur Jasuja Answer: 573 1 1 1 Solution: Let L = lcm(1 , 2 , 3 , . . . , n ), and let E = L 1 + + + · · · + denote the expression. 2 3 n In order for n to be quixotic, we need E ≡ 0 (mod 5) and E ≡ 0 (mod 9). We consider these two conditions separately. k k +1 Claim: E ≡ 0 (mod 5) if and only if n ∈ [4 · 5 , 5 ) for some nonnegative integer k . Proof. Let k = ⌊ log n ⌋ , which is equal to ν ( L ). In order for E to be divisible by 5, all terms in 5 5 L L L , , . . . , that aren’t multiples of 5 must sum to a multiple of 5. The potential terms that are not 1 2 n k k k k going to be multiples of 5 are L/ 5 , L/ (2 · 5 ) , L/ (3 · 5 ), and L/ (4 · 5 ), depending on the value of n . k k k k • If n ∈ [5 , 2 · 5 ), then only L/ 5 appears. Thus, the sum is L/ 5 , which is not a multiple of 5. k k k k k • If n ∈ [2 · 5 , 3 · 5 ), then only L/ 5 and L/ (2 · 5 ) appear. The sum is 3 L/ (2 · 5 ), which is not a multiple of 5. k k k k k k • If n ∈ [3 · 5 , 4 · 5 ), then only L/ 5 , L/ (2 · 5 ), and L/ (3 · 5 ) appear. The sum is 11 L/ (6 · 5 ), which is not a multiple of 5. k k +1 k k k k • If n ∈ [4 · 5 , 5 ), then L/ 5 , L/ (2 · 5 ), L/ (3 · 5 ), and L/ (4 · 5 ) all appear. The sum is k 25 L/ (12 · 5 ), which is a multiple of 5. Thus, this case works. Only the last case works, implying the claim. k − 1 k − 1 Claim: E ≡ 0 (mod 9) if and only if n ∈ [7 · 3 , 8 · 3 ) for some positive integer k . Proof. This is a repeat of the previous proof, so we will only sketch it. Let k = ⌊ log n ⌋ , which is equal 3 to ν ( L ). This time, the terms we need to consider are those that are not multiples of 9, which are 3 L L L , , · · · , . k − 1 k − 1 k − 1 3 2 · 3 8 · 3 Similar to the above, we need to check that the sum of the first j terms is divisible by 9 if and only if j = 7. There are 8 cases, but we could reduce workload by showing first that it is divisible by 3 if and k k only if j ∈ { 6 , 7 , 8 } (there are only L/ 3 and L/ (2 · 3 ) to consider), then eliminate 6 and 8 by using (mod 9). Doing a little bit of arithmetic, we’ll get the first 10 quixotic numbers: 21, 22, 23, 567, 568, 569, 570, 571, 572, 573.