Recently I was thinking about the pigeonhole principle in a problem and it occurred to me that we should probably be able to generalize it in a very natural way.
A slightly different and weaker version of the pigeonhole principle can be stated as – suppose we place $nk$ objects in $n$ holes. Then there is a choice of a hole that contains $k$ or more objects.
Is it also true that we can choose $2$ holes, such that the sum of the objects contained in these two holes is $2k$ or more? Similarly for any amount of holes.
This is clearly true for a choice of $n-1$ holes – we can choose a hole that contains $k$ or less objects, because if they all had more than $k$ objects, there would be more than $nk$ objects. Thus there exists a choice of $n-1$ objects such that they contain $(n-1)k$ or more objects. It's also clearly true that we can find a choice of $x$ holes that have $xk$ or more objects, if $x$ divides $n$ – just apply the pigeonhole principle (here, even the analogy of the classical formulation of the pigeonhole principle using $nk+1$ objects and $n$ holes works).
For a general proof, I think we could proceed by induction. As an example, if the amount of holes is divisible by $2$, we can just apply the pigeonhole principle to the choices $\{1,2\}\{3,4\}…\{(n-1)/2,n/2\}$. If it's not divisible, we first find the hole that contains at least $k$ objects. We can assume that this hole contains $2k-z$ objects for some $0<z \leq k$, as if it contains $2k$ objects or more we can just choose this object and any other to find a choice of two that have $2k$ objects or more in total.
We know that each remaining hole must have less than $z$ many objects, otherwise we're done. But if that's the case, then the total amount of objects is less than $(n-1)z + 2k – z \leq nk$. Induction can be used because the remainder is smaller than the divisor.
While I find this somewhat interesting, I don't see this mentioned anywhere, which makes me think I must be missing some reason why this observation is uninteresting, as opposed to the pigeonhole principle. Is that so? I might also be missing some very simple proof of this fact.
Best Answer
Your observation is correct. I suspect it is not stated often because people don't find it useful for the problems they want to solve. The intuitive proof is that you can sort the holes by contents and pick the holes down from the top. You are claiming that at each step the ones you have picked total at least the average contents times the number you have picked. Since the ones you haven't picked have the least contents this is reasonable.