HMMT 二月 2022 · ALGNT 赛 · 第 8 题
HMMT February 2022 — ALGNT Round — Problem 8
题目详情
- Positive integers a , a , . . . , a , b , b , . . . , b satisfy 2 ≤ a ≤ 166 and a ≡ a (mod 167) for each 1 2 7 1 2 7 i i +1 i 1 ≤ i ≤ 7 (where a = a ). Compute the minimum possible value of b b · · · b ( b + b + · · · + b ). 8 1 1 2 7 1 2 7
解析
- Positive integers a , a , . . . , a , b , b , . . . , b satisfy 2 ≤ a ≤ 166 and a ≡ a (mod 167) for each 1 2 7 1 2 7 i i +1 i 1 ≤ i ≤ 7 (where a = a ). Compute the minimum possible value of b b · · · b ( b + b + · · · + b ). 8 1 1 2 7 1 2 7 Proposed by: Gregory Pylypovych Answer: 675 Solution: Let B = b b · · · b − 128. Since 1 2 7 b b ··· b 2 b b ··· b 4 b b ··· b 128 1 2 7 2 3 7 3 4 7 a ≡ a ≡ a ≡ · · · ≡ a (mod 167) , 1 1 2 3 B B we find that a ≡ 1 (mod 167). Similarly, a ≡ 1 (mod 167) for all i . Since 167 is a prime and 1 i 167 − 1 = 2 · 83, we know that the order of each individual a (since a ̸ = 1) must be either 2 of a i i multiple of 83. If B is not a multiple of 83, then it follows that all the a must be − 1, which implies i that all the b must be even, meaning that the minimum possible value of b b · · · b ( b + b + · · · b ) is i 1 2 7 1 2 7 7 2 · 14 > 1000. Oh the other hand, if B is a multiple of 83, then the smallest possible values for b b · · · b are 45 and 1 2 7
- If b b · · · b = 45, then the smallest possible value for b + b + · · · + b is 5+3+3+1+1+1+1 = 15, 1 2 7 1 2 7 so the minimum possible value for b b · · · b ( b + b + · · · b ) is 45 · 15 = 675. This can be achieved by 1 2 7 1 2 7 1 / 2 1 / 4 1 / 8 1 / 16 letting g be an element of order 83 and setting a = g, a = g , a = g , a = g , a = g , a = 1 2 3 4 5 6 3 / 32 9 / 64 g , a = g (all exponents are taken mod 83). 7 If b b · · · b ≥ 128, then by the AM-GM inequality we have 1 2 7 8 / 7 8 b b · · · b ( b + b + · · · b ) ≥ 7( b b · · · b ) ≥ 7 · 2 > 1000 . 1 2 7 1 2 7 1 2 7 Therefore 675 is optimal.