PUMaC 2020 · 代数（B 组） · 第 5 题

PUMaC 2020 — Algebra (Division B) — Problem 5

Let { x } = x − b x c . Consider a function f from the set { 1 , 2 , . . . , 2020 } to the half-open interval [0 , 1). Suppose that for all x, y , there exists a z so that { f ( x ) + f ( y ) } = f ( z ). We say that a pair of integers m, n is valid if 1 ≤ m, n ≤ 2020 and there exists a function f satisfying the m m above so f (1) = . Determine the sum over all valid pairs m, n of . n n

解析

Let { x } = x − b x c . Consider a function f from the set { 1 , 2 , . . . , 2020 } to the half-open interval [0 , 1). Suppose that for all x, y , there exists a z so that { f ( x ) + f ( y ) } = f ( z ). We say that a pair of integers m, n is valid if 1 ≤ m, n, ≤ 2020 and there exists a function f satisfying the m m above so f (1) = . Determine the sum over all valid pairs m, n of n n Proposed by: Frank Lu Answer: 1019595 We will consider the set of all possible images for f , as this is the only restriction we are given on our function. First, suppose that f ( x ) was irrational for some value of x . Then, it follows that { n ∗ f ( x ) } is in the image of f for all n ∈ N . But this is impossible since our domain has only finitely many elements. Thus, it follows that our function can only be rational-valued. By repeating this argument, we also know that the denominator of f ( x ) must be at most 2020. We now claim that all such values are valid for f (1). To see this, let f ( x ) = { xf (1) } . The fact ∑ ∑ ∑ 2020 i − 1 2020 j i − 1 that our condition is satisfied is clear. We thus find = = 2019 ∗ 505 = i =1 j =0 i =1 i 2 1019595 is our answer.