# Pigeonhole principle and finite sequences

Suppose we have $75$ boxes that are labeled from $1$ to $75$ and that in each box there is at least one ball, but there are not more than $125$ balls total. I'm trying to find the largest number $n \in \left\{1,\, \ldots,\, 75 \right\}$ such that this statement is true: There is a collection of neighbouring boxes that contain exactly $n$ balls together. With neighbouring boxes I mean that their labels have to be consecutive.

I hope it's clear what I mean. We can rephrase the statement like this: $1 \leq x_i$, $1 \leq i \leq 75$ and $\sum_{i=1}^{75} x_i \leq 125$. Then there is a sequence $x_i,\, x_{i+1},\, \ldots,\, x_{i+j}$ such that $n=x_i + x_{i+1} + \ldots + x_{i+j}$ for some $j$.

The pigeonhole principle allows an easy proof of the statement for $n \leq 24$ that doesn't work for $n \geq 25$. I tried to apply the following algorithm to create simple counter-examples: To prevent the first $n$ boxes from contributing to a collection, we need $n+1$ balls in the $n$th box. Then we do the same with the following boxes, starting at $n+1$ and so on.

The algorithm only works for $33 \leq n \leq 49$. For smaller $n$, we would need two boxes with $n+1$ balls, but since we have at most $125$ balls altogether and each box contains at least one ball, there are not enough spare balls. For $50 \leq n \leq 75$, there are not even enough balls to put $n+1$ balls in any box.

If the algorithm I mentioned above is optimal, then the statement is true for all $n$, except those between $33$ and $49$. But if that's true, how can I prove it for $25 \leq n \leq 32$ and $50 \leq n \leq 75$?

• Please share your proof using the pigeonhole principle, and why you think the statement isn't true for $n=75$. – vadim123 Jun 4 '14 at 13:37
• Since you know that each box contains at least one ball, why can't you immediately conclude that there is a sequence of neighboring boxes that collectively contain $n$ balls for any $n\le 75$? And this is the best you can possibly do, since there may not be more than 75 balls total. What have I misunderstood? – MJD Jun 4 '14 at 13:45
• He meant exactly $n$ not "at least $n$" balls – PA6OTA Jun 4 '14 at 13:59
• @vadim123: Define $y_i = \sum_{j=1}^i x_j$. Then look at the sequence $\left(y_1, \ldots, y_{75}, y_1 + 24, \ldots, y_{75} + 24 \right)$. The sequence has $150$ elements that take only $149$ different values, so two elements must be equal by pigeonhole principle. Since the two subsequences $y_1, \ldots, y_{75}$ and $y_1 + 24, \ldots, y_{75} + 24$ contain only distinct elements, there must be $i$ and $k$ such that $y_k = y_i + 24$. The rest is basic arithmetic. About your other question: I don't know whether the statement holds for $75$. But the algorithm I explained above doesn't work with it. – Amarus Jun 4 '14 at 15:59

Okay, here's a fuller account of how to apply what "Bananarama" wrote to the original problem. That answer looks like it settles $n=25$ and $32\le n\le37$ without alteration. For $n$ in between, remember that the final boxes cannot be empty. Now we consider larger values of $n$.

Statement. A sequence of $n$ integers contains an uninterrupted stretch with a sum divisible by $n$.

Proof. Considering subsets $\{a_1\},\{a_1,a_2\},...\{a_1,a_2,...,a_n\}$. If none has a sum divisible by $n$, their sums must fall into $n-1$ residue classes; by the pigeonhole principle, two must be in the same class, in which case we can remove members of the smaller set from the larger to obtain the stretch with sum divisible by $n$. $\blacksquare$

In the original problem, with $75$ boxes, there must be an uninterrupted stretch of boxes with a sum divisible by $75$.

But that sum must be positive, and cannot be $150$ or any greater multiple. So it is $75$.

This will work without modification for $63\le n\le75$.

Now consider $51\le n\le62$. The first $n$ boxes contain a stretch with $n$ or $2n$ balls. But if it's $2n$, then the last $75-n$ boxes contain no more than $125-2n$ balls. There must be at least as many balls as boxes, so $75-n\le125-2n\implies n\le50$, a contradiction.

My most sincere apologies, I've been learning german for the last few years, and for some reason this has made me to read $n$ as "nine" in my head sometimes, this made me missunderstand the problem. In fact the new problem is a lot simpler to prove.

We apply the same lemma as before: If we have boxes $\{1,2\dots n\}$, each with at least $1$ marble, then there is a collection of consecutive boxes with a positive multiple of $n$ number of marbles. consider the collections $\{1\},\{1,2\}\dots \{1,2\dots n\}$ if one of those has a multiple of $n$ marbles then we are done, otherwise there are $n-1$ conguences the collections can take mod $n$ and therefore two have the same congruence, therefore the collection of consecutive boxes made up of the boxes that are in the big collection but not the small one gives us a collection of consecutive boxes with a sum which is a positive multiple of $n$.

If we have $75$ boxes then by the previous result there is a collection of consecutive boxes which has a positive multiple of $75$ number of marbles. Since there are no more than $125$ marbles that multiple must be $75$ and we are done.

• What exactly does it prove? I lean towards saying that $n=75$ has the desired property ("There is a collection of neighbouring boxes that contain exactly n balls together") but I don't have a clear proof. – PA6OTA Jun 4 '14 at 16:33
• So you prove the conjecture for $n=9$? State clearly what you're proving. – PA6OTA Jun 4 '14 at 16:41
• I still don't understand, but if you're saying the conjecture is true for every $n$ it's clearly wrong because the OP has a counterexample for some $n$. – PA6OTA Jun 4 '14 at 16:49
• ok I see now. Your idea seems to work for $n > 125/2$ because then being equal modulo $n$ means simply being equal. However, the proof is really poorly written, and $\{1,...,9\}$ stuff is just confusing. – PA6OTA Jun 4 '14 at 17:05
• Maybe I'm wrong, but the last paragraph is quite confusing, really. :( I think you can just drop it. The original problem is kind of a straight application of the lemma you mentioned above. – user49685 Jun 5 '14 at 1:38