A sequence of positive integers with $n$ terms satisfies $\sum_{i=1}^{n} a_i=2007$. Find the least positive integer $n$ such that there exist some consecutive terms in the sequence with their sum equal to $30$.
Problem
Source: China south east mathematical Olympiad 2007 problem 4
Tags: pigeonhole principle, symmetry, combinatorics unsolved, combinatorics
12.07.2013 10:44
Let $ \sum_{i=1}^{k} a_{i}= b_{k} $ and $M_{n}=\left \{b_{1},b_{2},..,b_{n},b_{1}+30,b_{2}+30,..,b_{n}+30 \right \} $ All of members in $M_{n}$ $\leq 2037$ Therefore, $n\geq 1019 \Rightarrow $ there exist $i,j$ such that $b_{i}=b_{j}+30$ because of Piegonhole principle. So, $ \sum_{t=j+1}^{i} a_{t}= 30 $. Therefore, $min_{n}\leq 1019$. For $n=1017$ , $b_{i}=i \forall i=1,2,..,29$ $b_{30k+n}=60k+n \forall n=0,1,..,29 \Lambda k=1,2,..,32 $ $b_{990+n}=1980+n \forall n=0,1,..,27 $ There aren't $i,j$ such that $b_{i}-b_{j}=30$. So $min_{n}\ge 1018$. Therefore, $min_{n}=1018 or 1019$ I think answer is $1018$ but I can't prove. For $n=1018$, if doesn't exist some consecutive terms in the sequence with their sum equal to $30$,then all of members in $M_{1018} \leq 2037 $ and $30 \notin M_{1018} $ So all of members in $M_{1018}$ can take $2036$ values and $|M_{1018}|=2036$ Therefore, $ (b_{1},b_{2},..,b_{1018},b_{1}+30,b_{2}+30,..,b_{1018}+30) $ is a permutation of $(1,2,..,29,31,..,2037)$
13.07.2013 19:57
You have solved the problem. Indeed, let $M_{n}=\left \{b_{1},b_{2},..,b_{n},b_{1}+30,b_{2}+30,..,b_{n}+30 \right \}$. Then $|M_n| \leq 2035$ because all members of $M_n$ are $\leq 2037$ and $M_n$ cannot contain numbers 30 and 2007-30=1977 in it. (Use the symmetry!) Hence by the Pigeonhole Principle if $n \geq 1018$, then there is a sequence of consecutive numbers that add up to 30.
13.07.2013 22:06
Can you explain ? Why $1977 \notin M_{n}$ ?