返回题库

HMMT 二月 2019 · ALGNT 赛 · 第 8 题

HMMT February 2019 — ALGNT Round — Problem 8

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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 )?
解析

英文解析

  1. 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