PUMaC 2019 · 团队赛 · 第 15 题
PUMaC 2019 — Team Round — Problem 15
题目详情
- Determine the number of functions f : Z → Z so that for all positive integers x we have f ( f ( x )) = f ( x + 1), and max( f (2) , . . . , f (14)) ≤ f (1) − 2 = 12. 2
解析
- Determine the number of functions f : Z → Z so that ∀ x ∈ Z , f ( f ( x )) = f ( x + 1), and max( f (2) , . . . , f (14)) ≤ f (1) − 2 = 12. Proposed by: Frank Lu Answer: 258 We replace 14 with k , or f (1). We have that f ( k ) = f (2), so it follows from above that f ( x ) = f ( x + k − 2) ∀ x ≥ 2. Now, suppose f was eventually periodic with period n as well. Let r be the remainder upon dividing k − 2 by n , q the quotient. Then, f ( x + r ) = f ( x + q ∗ n + r ) = 5 f ( x + ( k − 2)) = f ( x ) ∀ x large enough. Hence, it follows that if r is the smallest value so f ( x ) = f ( x + r ) eventually, it follows that r divides k − 2. Combining the fact that f (2) = f ( k ) yields that this eventual periodicity begins at x = 2. Let n be the smallest period of f . Now, it follows that f is determined by the values f (1) , f (2) , . . . , f ( n ) , f ( n + 1). Suppose that f ( f (2)) doesn’t leave a remainder of 3 upon division by n . Then, it follows that f (3) = f ( x ) for some x so x − 3 isn’t divisible by n . But running our argument above yields that n isn’t our smallest period, contradiction. We can repeat this for other values. Thus, we need that f ( i ) − ( i + 1) is divisible by i ∀ i ≥ 2. Now, we know that our period has to divide 12, suppose it is n . It follows that with period n , we have (12 /n ) choices for each of f (2) , f (3) , . . . , f ( n + 1), (by the n number of elements that are i + 1 modulo 12 /n ) which means we have (12 /n ) possibilities. 2 3 4 6 12 Summing this yields 12 + 6 + 4 + 3 + 2 + 1 = 12 + 36 + 64 + 81 + 64 + 1 = 258. 6