A Pigeonhole Principle problem:

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)

  • $\begingroup$ Do you mean two consecutive numbers? $\endgroup$ – preferred_anon Jan 20 '13 at 9:20
  • $\begingroup$ @DanielLittlewood Surely not: use one hundred $1$s and a single $200$; then you cannot find two consecutive numbers whose sum is $200$. $\endgroup$ – Benjamin Dickman Jan 20 '13 at 9:21
  • $\begingroup$ Adjacent is a better term, I think. The problem should be the same as the sum of adjacent numbers is 100. $\endgroup$ – lab bhattacharjee Jan 20 '13 at 9:21
  • $\begingroup$ Yes, adjacent is a better word .I mean adjacent not consecutive. $\endgroup$ – Narek Margaryan Jan 20 '13 at 9:26
  • $\begingroup$ 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. $\endgroup$ – Narek Margaryan Jan 20 '13 at 9:31

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.

  • $\begingroup$ When you say "subsequence" in line 5, you mean consecutive right? $\endgroup$ – alancalvitti Jan 20 '13 at 15:56
  • $\begingroup$ @alancalvitti Of course. $\endgroup$ – WimC Jan 20 '13 at 16:49
  • $\begingroup$ 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? $\endgroup$ – alancalvitti Jan 20 '13 at 17:18
  • 1
    $\begingroup$ @alancalvitti I've known the pigeon hole principle for more than twentyfive years, plenty of time to practice! $\endgroup$ – WimC Jan 20 '13 at 18:21
  • 2
    $\begingroup$ @alancalvitti $101$ pigeons in $100$ holes... ($101$ numbers and only $100$ possibilities for their last two digits.) $\endgroup$ – WimC Jan 25 '13 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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