HMMT 二月 2019 · ALGNT 赛 · 第 8 题
HMMT February 2019 — ALGNT Round — Problem 8
题目详情
- There is a unique function f : N → R such that f (1) > 0 and such that ( ) ∑ n f ( d ) f = 1 d d | n 2019 for all n ≥ 1. What is f (2018 )?
解析
- There is a unique function f : N → R such that f (1) > 0 and such that ( ) ∑ n f ( d ) f = 1 d d | n 2019 for all n ≥ 1. What is f (2018 )? Proposed by: Ashwin Sah 2 4038 2 ( ) (4038!) 2019 Answer: OR 8076 4 8076 2 (2019!) · 2 n n Fix any prime p , and let a = f ( p ) for n ≥ 0. Notice that using the relation for p , we obtain n n ∑ a a = 1 , i n − i i =0 ∑ n 2 2 1 which means that if we let g ( x ) = a x , then g ( x ) = 1 + x + x + · · · = as a generating n n ≥ 0 1 − x 1 − 2 function. Thus g ( x ) = (1 − x ) , and this is well-known to have generating function with coefficients 2 n ( ) n a = . One way to see this is using the Taylor series and then reorganizing terms; it is also n n 4 intimately related to the generating function for the Catalan numbers. In particular, a is independent n of our choice of p . ∏ Now if we define f ( n ) = a , then we see that f = f on the prime powers. 0 v ( n ) 0 p p | n If we define the Dirichlet convolution of two functions χ , χ : N → R as χ such that 1 2 3 ( ) ∑ n χ ( n ) = χ ( d ) χ , 3 1 2 d d | n then it is well-known that multiplicative functions ( χ ( m ) χ ( n ) = χ ( mn ) if gcd( m, n ), so e.g. φ ( n ), the Euler totient function) convolve to a multiplicative function. In particular, f is a multiplicative function by definition (it is equivalent to only define it at prime 0 powers then multiply), so the convolution of f with itself is multiplicative. By definition of a , the 0 n convolution of f with itself equals 1 at all prime powers. Thus by multiplicativity, it equals the 0 constant function 1 everywhere. Two final things to note: f (1) = a = 1 > 0, and f satisfying the conditions in the problem statement 0 0 is indeed unique (proceed by induction on n that f ( n ) is determined uniquely and that the resulting algorithm for computing f gives a well-defined function). Therefore f , satisfying those same conditions, 0 must equal f . At last, we have ( ) 4038 2019 2019 2019 f ( p ) = f ( p ) = 0 2019 4 so ( ) ( ) 2 2 4038 4038 2019 2019 2019 2019 2019 f (2018 ) = f (2 ) f (1009 ) = = . 4038 8076 4 2