Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

101 positive integers are placed on a circle whose sum is 300.Prove that it is possible to choose from these numbers some consecutive numbers whose sum is equal to 200. (I don't know if the word 'consecutive' is appropriate in this case ,I mean that these numbers follow each other on that circle)

share|improve this question
    
Do you mean two consecutive numbers? –  Daniel Littlewood Jan 20 '13 at 9:20
    
@DanielLittlewood Surely not: use one hundred $1$s and a single $200$; then you cannot find two consecutive numbers whose sum is $200$. –  Benjamin Dickman Jan 20 '13 at 9:21
    
Adjacent is a better term, I think. The problem should be the same as the sum of adjacent numbers is 100. –  lab bhattacharjee Jan 20 '13 at 9:21
    
Yes, adjacent is a better word .I mean adjacent not consecutive. –  user1978522 Jan 20 '13 at 9:26
    
I think the circle here can be viewed as a string and the problem asks to prove that there is a substring whose sum is 200. –  user1978522 Jan 20 '13 at 9:31

2 Answers 2

up vote 9 down vote accepted

Start at a certain position and form sums of subsequences of length $1, 2, \dotsc, 101$ starting at that position and going in clockwise direction. This is an increasing sequence of $101$ numbers so there are two different entries that are equal $\bmod$ $100$ (end in the same two digits). The difference between those entries is a positive multiple of $100$ and less than $300$ so either $100$ or $200$. This difference corresponds to a subsequence of numbers on the circle with sum either $100$ or $200$. If it is $200$ we're done, otherwise take the complement of that sequence.

share|improve this answer
    
When you say "subsequence" in line 5, you mean consecutive right? –  alancalvitti Jan 20 '13 at 15:56
    
@alancalvitti Of course. –  WimC Jan 20 '13 at 16:49
    
That's what I thought. What's the general principle that enabled you to solve this problem? Would I find it in, eg, Bona's Walk Through Combinatorics? –  alancalvitti Jan 20 '13 at 17:18
1  
@alancalvitti I've known the pigeon hole principle for more than twentyfive years, plenty of time to practice! –  WimC Jan 20 '13 at 18:21
    
I'm familiar with the principle, but curious how you applied it here. –  alancalvitti Jan 25 '13 at 14:50

What is the integer sum of a circle?

share|improve this answer
    
Nice answer, mate. –  Git Gud Jan 20 '13 at 10:06
    
Are there different boxes/ buttons to answer and to comment ? I´ll be more careful. –  user55514 Jan 20 '13 at 10:08
1  
Yes. I don't think the OP will know how to answer your question anyway. The problem was probably put like that to him. –  Git Gud Jan 20 '13 at 10:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.