Pigeonhole principle and finite sequences

Question

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

Answer 1

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.

Answer 2

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.