HMMT 二月 2017 · ALGNT 赛 · 第 10 题
HMMT February 2017 — ALGNT Round — Problem 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 .
解析
- 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. 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 8 the value 1. This contributes 2 . For f (1) = 2, we can once again propagate down the tree. While it looks like we have 2 choices at each 2 node (for the square roots), this is wrong, as if f ( x ) = − 2 and y = x , then f ( y ) = 0 is forced. Given this intuition, let a denote the answer for a binary tree of height n where the top is either − 2 n n 2 2 − 4 or 2. Therefore, a = 2 , a = 5 . You can show the recurrence a = a + 2 . This is because if the 1 2 n n − 1 2 top is 2, then we get a contribution of a . If the top is − 2, then both entries below it must be 0. n − 1 n After that, you can show that each of the remaining 2 − 4 vertices can be either of 2 possible square roots. Therefore, we get the recurrence as claimed. One can compute that a = 5777, so we get the 4 final answer 2(256 + 5777) = 12066 .