HMMT 二月 2015 · 代数 · 第 6 题
HMMT February 2015 — Algebra — Problem 6
题目详情
- Let a, b, c, d, e be nonnegative integers such that 625 a + 250 b + 100 c + 40 d + 16 e = 15 . What is the maximum possible value of a + b + c + d + e ?
解析
- Let a, b, c, d, e be nonnegative integers such that 625 a + 250 b + 100 c + 40 d + 16 e = 15 . What is the maximum possible value of a + b + c + d + e ? Answer: 153 The intuition is that as much should be in e as possible. But divisibility obstructions 3 4 3 like 16 ∤ 15 are in our way. However, the way the coefficients 5 > 5 · 2 > · · · are set up, we can at least easily avoid having a, b, c, d too large (speifically, ≥ 2). This is formalized below. First, we observe that ( a , a , a , a , a ) = (5 , 1 , 0 , 0 , 0) is a solution. Then given a solution, replacing 1 2 3 4 5 ( a , a ) with ( a − 2 , a + 5), where 1 ≤ i ≤ 4, also yields a solution. Given a solution, it turns out i i +1 i i +1 all solutions can be achieved by some combination of these swaps (or inverses of these swaps). 4 Thus, to optimize the sum, we want ( a, b, c, d ) ∈ { 0 , 1 } , since in this situation, there would be no way to make swaps to increase the sum. So the sequence of swaps looks like (5 , 1 , 0 , 0 , 0) → (1 , 11 , 0 , 0 , 0) → (1 , 1 , 25 , 0 , 0) → (1 , 1 , 1 , 60 , 0) → (1 , 1 , 1 , 0 , 150), yielding a sum of 1 + 1 + 1 + 0 + 150 = 153. Why is this optimal? Suppose ( a, b, c, d, e ) maximizes a + b + c + d + e . Then a, b, c, d ≤ 1, or else we could use a replacement ( a , a ) → ( a − 2 , a + 5) to strictly increase the sum. But modulo 2 i i +1 i i +1 3 forces a odd, so a = 1. Subtracting off and continuing in this manner shows that we must have b = 1, then c = 1, then d = 0, and finally e = 150. 3 Remark. The answer is coincidentally obtained by dropping the exponent of 15 into the one’s place.