Maths Olympiad Prep

Library / /9 of 15

Combinatorics Difficulty 6.3 National Olympiad Prove it Argentina

Find the least nn with the following property: In each nn-term sequence of positive integers with sum 20132013 there are several consecutive terms with sum 3131.

Solution

The least nn in question is 10221022. An example that n=1021n = 1021 is not enough: arrange in a row 3232 blocks 1,1,,1,321, 1, \ldots, 1, 32, with 3030 ones in each, then add 2929 ones. This gives a sequence of length 3231+29=102132 \cdot 31 + 29 = 1021 and sum 6232+29=201362 \cdot 32 + 29 = 2013. No consecutive terms in it have sum 3131.

Take a sequence with positive integer terms with length 10221022 and sum 20132013. We show that several consecutive terms add up to 3131. Let SjS_j be the sum of its first jj terms, j=1,,1022j = 1, \ldots, 1022. Consider the two sequences
1S1<S2<<S1022=2013 and 3231+S1<31+S2<<31+S1022=2044. 1 \leq S_1 < S_2 < \dots < S_{1022} = 2013 \text{ and } 32 \leq 31 + S_1 < 31 + S_2 < \dots < 31 + S_{1022} = 2044.
Assume Sj31S_j \neq 31 for all jj, otherwise the claim follows. Since 31+Sj3131 + S_j \neq 31 for all jj, it follows that the 20442044 integers above are in [1,2044][1, 2044] and different from 3131. Hence two of them are the same. Because the terms in each sequence are distinct, there are indices i,ji, j such that Si=Sj+31S_i = S_j + 31. Clearly i>ji > j and the terms of the original sequence with indices j+1,,ij+1, \ldots, i have sum 3131.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.