HMMT 十一月 2025 · 冲刺赛 · 第 2 题

2 . 5 | E − A | Submit a positive integer E . If the correct answer is A , you will receive 20 . 99 max 0 , 1 − A points. Proposed by: Derek Liu, Pitchayut Saengrungkongka Answer: 6422804 8 2 2 Solution: Let N = 10 , so ln N ≈ 18. Note that x − 2025 y = ( x − 45 y )( x + 45 y ) is a product of two numbers which are equivalent modulo 90. Conversely, if a and b are equivalent modulo 90, then 2 2 ab = x − 2025 y where x = ( a + b ) / 2 and y = ( a − b ) / 90. A naive estimate would be to simply count the number of such pairs ( a, b ) with ab ≤ N . For each a , there are approximately N/ (90 a ) such b that work, so the total number of such pairs is around Z N N 1 7 d a = N ln N ≈ 2 · 10 . 90 a 90 1 Almost all pairs ( a, b ) pair up with ( b, a ) with the same product, so a first estimate might be half this 7 quantity, or 10 (which earns 2 points). ′ ′ However, this is an overestimate because it ignores the fact that two pairs ( a, b ) and ( a , b ) might consist of different values and still have the same product. A similar analysis as above shows that there 1 8 are around N ln N ≈ 4 . 5 · 10 unordered pairs ( a, b ) of the same parity with product at most N , but 4 there are only 3 N/ 4 possible differences of squares (any value which is not 2 mod 4). Thus, on average, each of these 3 N/ 4 differences is hit by around 4 . 5 / (3 / 4) = 6 pairs ( a, b ). Each pair has around a 1 / 45 chance of satisfying a ≡ b mod 90 (as they are already equivalent mod 2), so the “probability” of any of these 6 pairs satisfying this is 6 1 6 21 1 − 1 − ≈ − ≈ 0 . 133 − 0 . 01 = 0 . 123 . 45 45 2025 This gives us a new estimate of 3 6 0 . 123 · N ≈ 9 . 225 · 10 , 4 which earns 5 points. This is still an overestimate because it assumes every number gets hit the same amount of times. 2 2 However, any number of the form x − 2025 y must be a square mod 2025. Note that there are 27 + 3 + 1 = 31 squares mod 81 and 10 + 1 = 11 mod 25, so the number of squares mod 2025 is 31 · 11 = 341, or around one-sixth of all numbers. These also make up for approximately 1 / 6 of all such pairs ( a, b ), so each of these pairs has around a 6 / 45 = 2 / 9 probability of satisfying a ≡ b mod 90. The new “probability” becomes 6 2 6 2 13 2200 5 1 − 1 − = 1 − ≈ 1 − = , 6 15 15 3300 9 giving us an approximation of 5 1 3 6 · N ≈ 6 . 94 · 10 , 9 6 4 which is a lot closer to the true value (earning 17 points). This estimate still assumes that each of the 341 squares mod 2025 gets hit equally, but this isn’t true either. For instance, 0 has 9 square roots mod 81 (the multiples of 9), but 1 only has 2 square roots. We can get a better estimate by applying the above method, but doing casework on gcd( ab, 2025) instead (note a ≡ b mod 45 implies this gcd is a square). © 2025 HMMT 2 4 8 • Suppose gcd( ab, 2025) = 1. We know · = of such pairs ( a, b ) satisfy this, and ab can be one 3 5 15 8 2025 of 27 · 10 = 270 residues mod 2025, so collisions are about · = 4 times more likely. The 15 270 number of values we get this way will be around ! 6 4 3 270 1 6 1 − 1 − · N ≈ 0 . 43 · N ≈ 4 . 3 · 10 , 45 4 2025 10 6 2 3 approximating 1 − (1 − 4 / 45) ≈ 6(4 / 45) − 15(4 / 45) + 20(4 / 45) ≈ 0 . 53 − 0 . 12 + 0 . 02 = 0 . 43. (Similar binomial expansions from now on will be omitted.) 2 4 8 • Suppose gcd( ab, 2025) = 9. We know · = of such pairs ( a, b ) satisfy this, and ab can be 9 5 45 8 2025 one of 3 · 10 = 30 residues mod 2025, so collisions are about · = 12 times more likely. The 45 30 number of values we get this way will be around ! 6 12 3 30 1 6 1 − 1 − · N ≈ 0 . 84 · N ≈ 0 . 93 · 10 . 45 4 2025 90 2 1 2 • Suppose gcd( ab, 2025) = 25. We know · = of such pairs ( a, b ) satisfy this, and ab can be 3 5 15 2 2025 one of 27 · 1 = 27 residues mod 2025, so collisions are about · = 10 times more likely. The 15 27 number of values we get this way will be around ! 6 10 3 27 1 6 1 − 1 − · N ≈ 0 . 78 · N ≈ 0 . 78 · 10 . 45 4 2025 100 1 4 4 • Suppose gcd( ab, 2025) = 81. We know · = of such pairs ( a, b ) satisfy this, and ab can be 9 5 45 4 2025 one of 1 · 10 = 10 residues mod 2025, so collisions are about · = 18 times more likely. The 45 10 number of values we get this way will be around ! 6 18 3 10 1 6 1 − 1 − · N ≈ 0 . 95 · N ≈ 0 . 35 · 10 . 45 4 2025 270 • One can similarly check that in the remaining cases gcd( ab, 2025) = 225 and 2025, which make up for 4 residues mod 2025, collisions are about 36 and 45 times more likely, respectively. Since 6 (1 − 36 / 45) ≈ 0, we may as well assume the number of values is 3 4 6 · N ≈ 0 . 14 · 10 . 4 2025 Adding these values up, we get 6 6 6 6 6 6