PUMaC 2021 · 数论（A 组） · 第 5 题
PUMaC 2021 — Number Theory (Division A) — Problem 5
题目详情
- Suppose that f : Z × Z → R , satisfies the equation f ( x, y ) = f (3 x + y, 2 x + 2 y ) for all x, y ∈ Z . Determine the maximal number of distinct values of f ( x, y ) for 1 ≤ x, y ≤ 100 . P n gcd( i,n )
解析
- Suppose that f : Z × Z → R , such that f ( x, y ) = f (3 x + y, 2 x + 2 y ) . Determine the maximal number of distinct values of f ( x, y ) for 1 ≤ x, y ≤ 100 . Proposed by: Frank Lu Answer: 8983 Note that the only places where we can get distinct values for f ( x, y ) are those that are not of the form (3 a + b, 2 a + 2 b ) for some integers ( a, b ) in the range 1 ≤ a, b ≤ 100 . Observe that 2 x − y 3 y − 2 x if x = 3 a + b, y = 2 a + 2 b, then we’d have that a = , b = . In other words, for this 4 4 to occur, we need that 2 x ≡ y, 3 y (mod 4) . But then we have that y is even and x is the same parity of y/ 2 . Furthermore, for the points that are of the above form, in order for 1 ≤ a, b ≤ 100 as well, we need 4 ≤ 2 x − y ≤ 400 and 4 ≤ 3 y − 2 x ≤ 400 . From here, we see that for a given value of y, we have that y + 4 ≤ 2 x ≤ 3 y − 4 , as the other two bounds are automatically satisfied as 1 ≤ x, y ≤ 100 . But then with y = 2 y , we see that y + 2 ≤ x ≤ 3 y − 2 . For y ≤ 34 , we 1 1 1 1 see that both bounds are the final bounds, meaning that, as x is the same sign as y , we have 1 y − 1 values for x. Over the values of y this yields us with 33 · 17 = 561 . 1 1 For 35 ≤ y ≤ 50 , we have y + 2 ≤ x ≤ 100 as the sharp bounds. Notice that this yields 1 1 100 − y 1 us with ⌊ ⌋ values for x, again maintaining the parity condition. Summing over these 2 values yields us with 25 + 25 + 26 + 26 + · · · + 32 + 32 = 57 · 8 = 456 values, so in total we have 561 + 456 = 1017 values of ( x, y ) that are images of the function that sends ( x, y ) to (3 x + y, 2 x + 2 y ) within 1 ≤ x, y ≤ 100 . 2 The number of distinct values of f ( x, y ) is then at most 100 − 1017 = 8983 . P n gcd( i,n )