Skip to main content
OlympiadHQ

Browse · MathNet

Print

China Southeastern Mathematical Olympiad

China counting and probability

Problem

Find the smallest positive integer such that any sequence of positive integers satisfying must have several consecutive terms whose sum is 30.
Solution
Firstly, we could construct a sequence of positive integers with 1017 terms , such that we cannot find consecutive terms whose sum is 30. Hence, we could set , and , , , which means the sequence is 1, 1, \dots, 1, 31, , 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 that satisfies the condition , we want to prove that there must exist several consecutive terms whose sum is 30.

Denote , , then

Group the elements in the set 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 brackets and 27 numbers without brackets. Arbitrarily take 1018 numbers, whose sum is the value of . There must be two numbers from the same bracket. Denote the two numbers by , then , which means, Therefore, the minimum of is 1018.
Final answer
1018

Techniques

Pigeonhole principleColoring schemes, extremal argumentsSums and products