PUMaC 2009 · 代数（A 组） · 第 7 题
PUMaC 2009 — Algebra (Division A) — Problem 7
题目详情
- Let x , x , . . . , x be a sequence of integers, such that − 1 ≤ x ≤ 2, for i = 1 , 2 , . . . , n , 1 2 n i 8 8 8 x + x + · · · + x = 7 and x + x + . . . x = 2009. Let m and M be the minimal and maximal 1 2 n 1 2 n M 9 9 9 possible value of x + x + . . . x , respectively. Find the . Round your answer to nearest 1 2 n m integer, if necessary.
解析
- Let x , x , . . . , x be a sequence of integers, such that − 1 ≤ x ≤ 2, for i = 1 , 2 , . . . , n , 1 2 n i 8 8 8 x + x + · · · + x = 7 and x + x + . . . x = 2009. Let m and M be the minimal and maximal 1 2 n 1 2 n M 9 9 9 possible value of x + x + . . . x , respectively. Find . 1 2 n m M Solution. = 511. The x -s that are 0 do not matter at all, they can be disregarded. The i m remaining x are − 1, 1, or 2 and the only thing that matters is how many of the x have i i each particular value. If a, b, c ≥ 0 denote the number of − 1-s, 1-s, and 2-s, respectively, then 8 8 8 x + x + . . . x = 2009 says that a + b + 256 c = 2009: each x which is − 1 contributes 1 to the i 1 2 n sum, for a total of a , also b is the contribution of the 1-s, and 256 c is the contribution of the 2-s 9 9 9 (each gives 256). Similarly, x + x + · · · + x = − a + b +2 c , and x + x + . . . x = − a + b +512 c . 1 2 n 1 2 n Hence given that a, b, c are nonnegative integers such that − a + b + 2 c = 7 a + b + 256 c = 2009 . We must find the extremal values of − a + b + 512 c . We can write − a + b + 512 c = ( − a + b + 2 c ) + 510 c = 7 + 510 c , and this expression is extremal when c is extremal. Adding the first two equations we get 2 b + 258 c = 2016, and since b ≥ 0, this implies c ≤ 2016 / 258 = 7 + 35 / 43. Since c is a non-negative integer, 7 ≤ 7 + 510 c ≤ 7 + 510 × 7. Also, it is easy to check that if ( a, b ) = (1001 , 1008) then c = 0; and if ( a, b ) = (112 , 105), then c = 7. So the extrema are 7 and 7 × 511.