Maths Olympiad Prep

Track / Stage 7 / 37 of 300 #1437 of 1964

Problem 1437

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.0 Prove it

Let be a sequence of 51 51 natural numbers whose sum is 100. 100. Show that for any natural number 1k<100 1\le k<100 there are some consecutive numbers from this sequence whose sum is k k or 100k. 100-k.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Define Partial Sums:
Consider the partial sums si=a1+a2++ai s_i = a_1 + a_2 + \ldots + a_i for i=1,2,,51 i = 1, 2, \ldots, 51 . Clearly, s1,s2,,s51 s_1, s_2, \ldots, s_{51} are natural numbers ranging from 1 to 100, inclusive, since the sum of all 51 numbers is 100.

2. **Case 1: k50 k \geq 50 :**
- Create pairs (1,k+1),(2,k+2),,(100k,100)(1, k+1), (2, k+2), \ldots, (100 - k, 100). There are 100k50 100 - k \leq 50 such pairs.
- By the Pigeonhole Principle, since we have 51 partial sums and only 100k 100 - k pairs, at least one pair must receive two partial sums. Suppose pair (j,j+k)(j, j+k) receives partial sums s s_{\ell} and sm s_m with <m \ell < m .
- Then, sms=a+1+a+2++am=(j+k)j=k s_m - s_{\ell} = a_{\ell + 1} + a_{\ell + 2} + \ldots + a_m = (j+k) - j = k .
- Thus, there exist consecutive terms whose sum is k k .

3. **Case 2: k<50 k < 50 :**
- Create pairs (1,101k),(2,102k),,(k,100)(1, 101 - k), (2, 102 - k), \ldots, (k, 100). There are k<50 k < 50 such pairs.
- By the Pigeonhole Principle, since we have 51 partial sums and only k k pairs, at least one pair must receive two partial sums. Suppose pair (j,j+(100k))(j, j + (100 - k)) receives partial sums s s_{\ell} and sm s_m with <m \ell < m .
- Then, sms=a+1+a+2++am=(j+(100k))j=100k s_m - s_{\ell} = a_{\ell + 1} + a_{\ell + 2} + \ldots + a_m = (j + (100 - k)) - j = 100 - k .
- Thus, there exist consecutive terms whose sum is 100k 100 - k .

4. Conclusion:
In either case, for any natural number 1k<100 1 \leq k < 100 , there are some consecutive numbers from the sequence whose sum is either k k or 100k 100 - k .

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.