sequence problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

sequence problem

G H J

Reveal topic tags

pigeonhole principle

combinatorics unsolved

L

G H BBookmark kLocked kLocked NReply

Source: China south east mathematical Olympiad 2007 problem 4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

290 posts

jred

#1 h Jul 12, 2013, 3:51 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

676 posts

bcp123

#2 h Jul 12, 2013, 7:44 AM • 2 Y

Y by Adventure10, Mango247

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)$

This post has been edited 1 time. Last edited by bcp123, Jul 21, 2013, 11:42 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

27 posts

#3 h Jul 13, 2013, 4:57 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

676 posts

bcp123

#4 h Jul 13, 2013, 7:06 PM • 1 Y

Y by Adventure10

Can you explain ?
Why $1977 \notin M_{n}$ ?

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a