Maths Olympiad Prep

Library / /28 of 40

Combinatorics Difficulty 6.4 National olympiad Prove it China

Find the smallest positive integer nn such that any sequence of positive integers a1,a2,,ana_1, a_2, \dots, a_n satisfying i=1nai=2007\sum_{i=1}^{n} a_i = 2007 must have several consecutive terms whose sum is 30.

Solution

Firstly, we could construct a sequence of positive integers with 1017 terms a1,a2,,a1017a_1, a_2, \dots, a_{1017}, such that we cannot find consecutive terms whose sum is 30. Hence, we could set a1=a2==a29=1a_1 = a_2 = \cdots = a_{29} = 1, a30=31a_{30} = 31 and a30+m+i=aia_{30+m+i} = a_i, i{1,2,,30}i \in \{1, 2, \dots, 30\}, mNm \in \mathbb{N}, which means the sequence is 1, 1, \dots, 1, 31, 1,1,,1,31,,1,1,,1,31,|1, 1, \dots, 1, 31, \dots, 1, 1, \dots, 1, 31, \dots|, 1, \dots, 1 (in which there are 34 groups all have 30 terms except the last group with 27 terms, totalling 1017 terms).

Secondly, when the terms are less than 1017, what we should do is just to combine several consecutive terms into a larger number within certain groups of the sequence.

Now, for any sequence with 1018 terms a1,a2,,a1018a_1, a_2, \dots, a_{1018} that satisfies the condition i=11018ai=2007\sum_{i=1}^{1018} a_i = 2007, we want to prove that there must exist several consecutive terms whose sum is 30.

Denote Sk=i=1kaiS_k = \sum_{i=1}^{k} a_i, k=1,2,,1018k = 1, 2, \dots, 1018, then
1S1<S2<<S1018=2007.1 \le S_1 < S_2 < \cdots < S_{1018} = 2007.

Group the elements in the set {1,2,,2007}\{1, 2, \dots, 2007\} as follows:

(1, 31), (2, 32), ..., (30, 60);
(61, 91), (62, 92), ..., (90, 120);
(121, 151), (122, 152), ..., (150, 180);
......
(60k + 1, 60k + 31), (60k + 2, 60k + 32), ..., (60k + 30, 60k + 1);
......
(60 \cdot 32 + 1, 60 \cdot 32 + 31), (60 \cdot 32 + 2, 60 \cdot 32 + 32), ..., (60 \cdot 32 + 30, 60 \cdot 33);
1981, 1982, ..., 2007.

There are 33×30=99033 \times 30 = 990 brackets and 27 numbers without brackets. Arbitrarily take 1018 numbers, whose sum is the value of SkS_k. There must be two numbers from the same bracket. Denote the two numbers by (Sk,Sk+m)(S_k, S_{k+m}), then Sk+mSk=30S_{k+m} - S_k = 30, which means,
ak+1+ak+2++ak+m=30. a_{k+1} + a_{k+2} + \cdots + a_{k+m} = 30.
Therefore, the minimum of nn is 1018.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.