PUMaC 2023 · 团队赛 · 第 4 题
PUMaC 2023 — Team Round — Problem 4
题目详情
- Find the largest integer x < 1000 such that and are both odd. x x
解析
- Find the largest integer x < 1000 such that and are both odd. x x Proposed by Michael Gintz Answer: 419 n Solution 1: Kummer’s Theorem (special case): is odd iff you never carry while performing m the addition of m and n − m in base 2 (proof will not be provided, look online). So, we need there to be no carries when we perform x + (1515 − x ) and x + (1975 − x ) in binary. 1515 = 1024 + 512 − 21 = 10111101011 and 1975 = 2047 − 64 − 8 = 11110110111 . 2 2 For there to be no carries, we need x and 1515 − x to both have 0’s in the spots where 1515 has a 0. To maximize x , we should include as many 1’s as possible. So, we should take x be as large as possible such that it has a 1 at each position where both 1515 and 1975 have 1’s. Then, x = 00110100011 = 419 . 2 Solution 2: k Q n n n i i Lucas’s Theorem: ≡ (mod p ), with n is n ’s i th digit, base p . = 0 if m > n . i i i m m m i i i =0 n n i Similar reasoning to before, if we want ≡ 0 (mod 2), we need ≡ 1 for all i , meaning m m i m = 0 if n = 0. So, x can only have a 1 where both 1515 and 1975 have 1’s, and the rest of i i the solution follows as before.