HMMT 二月 2021 · ALGNT 赛 · 第 10 题
HMMT February 2021 — ALGNT Round — Problem 10
题目详情
- Let S be a set of positive integers satisfying the following two conditions: • For each positive integer n , at least one of n, 2 n, . . . , 100 n is in S . • If a , a , b , b are positive integers such that gcd( a a , b b ) = 1 and a b , a b ∈ S , then 1 2 1 2 1 2 1 2 1 1 2 2 a b , a b ∈ S . 2 1 1 2 5 Suppose that S has natural density r . Compute the minimum possible value of b 10 r c . 1 Note: S has natural density r if | S ∩ { 1 , ..., n }| approaches r as n approaches ∞ . n
解析
- Let S be a set of positive integers satisfying the following two conditions: • For each positive integer n , at least one of n, 2 n, . . . , 100 n is in S . • If a , a , b , b are positive integers such that gcd( a a , b b ) = 1 and a b , a b ∈ S , then 1 2 1 2 1 2 1 2 1 1 2 2 a b , a b ∈ S . 2 1 1 2 5 Suppose that S has natural density r . Compute the minimum possible value of b 10 r c . 1 Note: S has natural density r if | S ∩ { 1 , ..., n }| approaches r as n approaches ∞ . n Proposed by: Milan Haiman Answer: 396 1 Solution: The optimal value of r is . This is attained by letting S be the set of integers n for 252 which ν ( n ) ≡ 4 mod 5 and ν ( n ) ≡ 1 mod 2. 2 3 Let S be a set of positive integers satisfying the two conditions. For each prime p , let A = { ν ( n ) : p p n ∈ S } . We claim that in fact S is precisely the set of positive integers n for which ν ( n ) ∈ A for p p each prime p . e e e e 1 2 1 2 Let p be prime and suppose that a p , a p ∈ S , with p - a , a . Then, setting b = p and b = p 1 2 1 2 1 2 e 2 in the second condition gives that a p ∈ S as well. So, if we have an integer n for which ν ( n ) ∈ A 1 p p ′ for each prime p , we can start with any element n of S and apply this step for each prime divisor of ′ n and n to obtain n ∈ S . Now we deal with the first condition. Let n be any positive integer. We will compute the least positive integer m such that mn ∈ S . By the above result, we can work with each prime separately. For a given prime p , let e be the least element of A with e ≥ ν ( n ). Then we must have ν ( m ) ≥ e − ν ( n ), p p p p p p p and equality for all primes p is sufficient. So, if the elements of A are c < c < c < c < . . . , p p, 1 p, 2 p, 3 p, 4 then c = max( c , c − c − 1 , c − c − 1 , c − c − 1 , . . . ) p p, 1 p, 2 p, 1 p, 3 p, 2 p, 4 p, 3 is the worst case value for ν ( m ). p ∏ c p We conclude two things from this. First, we must have p ≤ 100 by condition 1, and in fact this p is sufficient. Second, since we only care about c and would like to minimize r , the optimal choice for p A is an arithmetic progression with first term c and common difference c + 1. So we assume that p p p each A is of this form. p ∏ c p Let t = p . We now compute r . Note that S is the set of integers n such that for each prime p , p k ( c +1) − 1 k ( c +1) p p n ≡ ap mod p for some positive integers a, k with a < p . This means that each prime p contributes a factor of p − 1 p − 1 p − 1 p − 1 1
-
-
- · · · = = c +1 2 c +2 3 c +3 c +1 c p p p p p p p p p − 1 1 + p + · · · + p 1 to the density of S . Multiplying over all primes p gives r = , where σ ( t ) is the sum of divisors of t . σ ( t ) 1 So, it suffices to maximize σ ( t ) for t ≤ 100. By inspection, t = 96 is optimal, giving r = . 252
-