HMMT 二月 2021 · 冲刺赛 · 第 10 题
HMMT February 2021 — Guts Round — Problem 10
题目详情
- [10] Let a , a , . . . , a be a sequence of distinct positive integers such that a + a + · · · + a = 2021 and 1 2 n 1 2 n k a a · · · a is maximized. If M = a a · · · a , compute the largest positive integer k such that 2 | M . 1 2 n 1 2 n
解析
- [10] Let a , a , . . . , a be a sequence of distinct positive integers such that a + a + · · · + a = 2021 and 1 2 n 1 2 n k a a · · · a is maximized. If M = a a · · · a , compute the largest positive integer k such that 2 | M . 1 2 n 1 2 n Proposed by: Sheldon Kieren Tan Answer: 62 Solution: We claim that the optimal set is { 2 , 3 , · · · , 64 } \ { 58 } . We first show that any optimal set is either of the form { b, b + 1 , b + 2 , . . . , d } or { b, b + 1 , . . . , d } \ { c } , for some b < c < d. Without loss of generality, assume that the sequence a < a < · · · < a has the maximum product. 1 2 n Suppose a > a + 2 . Then, increasing a by 1 and decreasing a by 1 will increase the product j +1 j j j +1 M, contradicting the assumption that the sequence has the optimal product. Thus, any ”gaps” in the a can only have size 1 . i Now, we show that there can only be one such gap. Suppose a = a + 2 , and a = a + 2 , for j +1 j k +1 k j < k. Then, we can increase a by 1 and decrease a by 1 to increase the total product. Thus, there j i +1 is at most one gap, and the sequence a is of one of the forms described before. i We now show that either b = 2 or b = 3 . Consider any set of the form { b, b + 1 , b + 2 , . . . , d } or { b, b + 1 , . . . , d } \ { c } . If b = 1 , then we can remove b and increase d by 1 to increase the product. If b > 4 , then we can remove b and replace it with 2 and b − 2 to increase the product. Thus, we have b = 2 , 3 , or 4 . Suppose b = 4 . If the next element is 5 , we can replace it with a 2 and a 3 to increase the product, and if the next element is 6 , we can replace it with a 1 , 2 , and 3 without making the product any smaller. Thus, we can assume that either b = 2 or b = 3 . The nearest triangular number to 2021 is 2016 = 1+2+ · · · +64 . Using this, we can compute that if b = 2 , 64! our set must be { 2 , 3 , · · · , 64 } \ { 58 } , leading to a product of . If b = 3 , our set is { 3 , · · · , 64 } \ { 56 } , 58 64! leading to a product of . 2 · 56 64! Thus, the maximum product is . We now compute the highest power of 2 that divides this expres- 58 sion. 64! includes 32 elements that contribute at least one power of 2 , 16 that contribute at least two powers of 2 , and so on until the one element that contributes at least six powers of 2 . This means the highest power of 2 that divides 64! is 32 + 16 + · · · + 2 + 1 = 63 . Finally, dividing by 58 removes one of these powers of 2 , making the answer 62 .