PUMaC 2013 · 个人决赛（B 组） · 第 3 题

PUMaC 2013 — Individual Finals (Division B) — Problem 3

Find the smallest positive integer n with the following property: for every sequence of positive integers a , a , ..., a with a + a + ... + a = 2013, there exist some (possibly one) consecutive 1 2 n 1 2 n term(s) in the sequence that add up to 70. 1

解析

Find the smallest positive integer n with the following property: for every sequence of positive integers a , a , ..., a with a + a + ... + a = 2013, there exist some (possibly one) consecutive 1 2 n 1 2 n term(s) in the sequence that add up to 70. Solution We claim that n ≥ 1034. If n = 1033, then consider the 70-term subsequence 1 , 1 , ..., 1 , 71 with 69 1’s. The sum of the terms in this subsequence is 140. Now consider the sequence obtained by concatenating 14 copies of this subsequence and then 53 1’s. The sum of the terms in this sequence is 14 × 140 + 53 = 2013 and the sequence contains no consecutive terms that add up to 70, a contradiction. If n < 1033, we can also construct a counterexample by combining some terms in the above sequence to form a new sequence with fewer terms. Thus n ≥ 1034. We now show that the minimum value of n is indeed 1034. Put the positive integers from 1 to 2013 into the following sets: { 1 , 71 } , { 2 , 72 } , ..., { 70 , 140 } { 141 , 211 } , { 142 , 212 } , ..., { 210 , 280 } ... ... ... ... { 1821 , 1891 } , { 1822 , 1892 } , ..., { 1890 , 1960 } { 1961 } , { 1962 } , ..., { 2013 } Define S = a + a + ... + a . By the pigeonhole principle, there must be some S and S k 1 2 k i j (1 ≤ i < j ≤ 1034) that belong to the same pair above. Then a + a + ... + a = S − S = 70. i +1 i +2 j j i 2