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
( )
∑
f ( d ) f = 1 ndd | 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
( )
∑
f ( d ) f = 1 ndd | n
2019
for all n ≥ 1. What is f (2018 )?
Proposed by: Ashwin Sah
40382
( )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 obtainn
∑na a = 1 ,
i n − ii =0
∑
n 2 2 1
which means that if we let g ( x ) = a x , then g ( x ) = 1 + x + x + · · · = as a generatingnn ≥ 0
1 − x −1
function. Thus g ( x ) = (1 − x ) , and this is well-known to have generating function with coefficients 2
2 n
( )
a = . One way to see this is using the Taylor series and then reorganizing terms; it is alsonn nintimately related to the generating function for the Catalan numbers. In particular, a is independent 4
of our choice of p .n
∏
Now if we define f ( n ) = a , then we see that f = f on the prime powers.
0 v ( n ) 0
p | np
If we define the Dirichlet convolution of two functions χ , χ : N → R as χ such that
1 2 3
( )
∑
χ ( n ) = χ ( d ) χ ,n
3 1 2
d | ndthen 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 primepowers then multiply), so the convolution of f with itself is multiplicative. By definition of a , the 0
0 nconvolution of f with itself equals 1 at all prime powers. Thus by multiplicativity, it equals theconstant function 1 everywhere.0
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 resultingalgorithm for computing f gives a well-defined function). Therefore f , satisfying those same conditions,
must equal f .0
At last, we have
( )
4038
2019 2019
2019
f ( p ) = f ( p ) =
20190
so 4
( ) ( )
2 2
4038 4038
2019 2019 2019
2019 2019
f (2018 ) = f (2 ) f (1009 ) = = .
4038 8076
4 2