HMMT 十一月 2022 · GEN 赛 · 第 10 题
HMMT November 2022 — GEN Round — Problem 10
题目详情
- Compute the number of distinct pairs of the form 4 (first three digits of x, first three digits of x ) 10 over all integers x > 10 . 10 10 For example, one such pair is (100 , 100) when x = 10 .
解析
- Compute the number of distinct pairs of the form 4 (first three digits of x, first three digits of x ) 10 over all integers x > 10 . 10 10 For example, one such pair is (100 , 100) when x = 10 . Proposed by: Albert Wang Answer: 4495 Solution: Graph these points on an x, y -plane. We claim that there are integers 100 = a < a < 0 1 a < a < a = 999, for which the locus of these points is entirely contained in four taxicab (up/right 2 3 4 movement by 1 unit) paths from ( a , 100) to ( a , 999), i = 0 , 1 , 2 , 3. i i +1 As we increment x very slowly over all reals in [100 , 1000), which would produce the same set of tuples as we want (some small details missing here, but for large enough x we can approximate these decimals k to arbitrary precision by scaling by some 10 ), it is clear that we must either have only one of the values increasing by 1, or both of them increasing by 1, where increasing by 1 in this context also includes the looping over from 999 to 100. In particular, this looping over occurs at the first three digits of √ 4 powers of 10 between 1 and 10 (i.e. 177 , 316 , 562), which are precisely the values of a , a , a that 1 2 3 we claimed to exist. Therefore, our taxicab paths have the same total length as one going from (100 , 100) up to (999 + 900 + 900 + 900 , 999), by stacking our four segments to continue from each other vertically. It remains to compute the number of times both sides of the tuple increased simultaneously, which correspond to 4 4 4 4 fourth powers in the interval (1 , 1000). There are four of these corresponding to 2 , 3 , 4 , 5 , which are at (199 , 159) to (200 , 160), (299 , 809) to (300 , 810), (399 , 255) to (400 , 256), and (499 , 624) to (500 , 625). So, our taxicab path is only missing these four holes. Our final count is equal to the total taxidistance of the path, minus 4, and then finally adding back 1 to account for a starting point. 2 · 899 + 3 · 900 − 4 + 1 = 4495 .