HMMT 二月 2017 · ALGNT 赛 · 第 10 题

英文解析

10. Let N denote the natural numbers. Compute the number of functions f : N → { 0 , 1 , . . . , 16 } such that
    2 2
    f ( x + 17) = f ( x ) and f ( x ) ≡ f ( x ) + 15 (mod 17)
    for all integers x ≥ 1 .
    Proposed by: Yang Liu
    Answer: 12066
    By plugging in x = 0, we get that f (0) can be either − 1 , 2. As f (0) is unrelated to all other values,
    we need to remember to multiply our answer by 2 at the end. Similarly, f (1) = − 1 or 2.
    Consider the graph x → x . It is a binary tree rooted at − 1, and there is an edge − 1 → 1, and a loop 2
    1 → 1 . Our first case is f (1) = − 1 . Note that if x, y satisfy x = y , then f ( y ) 6 = 1. Otherwise, we 2
    would have f ( x ) = 3 (mod 17), a contradiction as 3 is a nonresidue. So only the 8 leaves can take 2
    the value 1. This contributes 2 .8
    For f (1) = 2, we can once again propagate down the tree. While it looks like we have 2 choices at eachnode (for the square roots), this is wrong, as if f ( x ) = − 2 and y = x , then f ( y ) = 0 is forced.2
    Given this intuition, let a denote the answer for a binary tree of height n where the top is either − 2
    2 2 − 4 nnor 2. Therefore, a = 2 , a = 5 . You can show the recurrence a = a + 2 . This is because if the
    1 2 nn − 1
    top is 2, then we get a contribution of a . If the top is − 2, then both entries below it must be 0.2
    n − 1
    After that, you can show that each of the remaining 2 − 4 vertices can be either of 2 possible squarenroots. Therefore, we get the recurrence as claimed. One can compute that a = 5777, so we get thefinal answer 2(256 + 5777) = 12066 .4