I found the following question on this website:
You have 200 monkeys placed in 101 spaceships such that each spaceship contains at least one monkey. Prove there is a subset of spaceships containing a total of exactly 100 monkeys.
I suspect that there is an elegant way to "construct" pigeons and holes which I have not yet discovered. I would appreciate any hints (preferably not full solutions) that can lead me there. Thanks in advance.
Best Answer
Let $i^{th}$ spaceship have $a_i$ monkeys. For $1\le r\le101$ let $b_r=\sum_{i=1}^{r}a_i$
We have $1\le b_1<b_2<...<b_{101}=200$.
Divide $101$ $b_i$'s into $100$ boxes numbered $0,1,2,3..,99$ such that $b_i$ which leaves remainder $k$ when divided by $100$ goes in box $k$.
By pigeon hole principal there is a box with 2 elements say $b_p$ and $b_q$ with $p<q$.
Then $b_q-b_p=100n$ where $n\in\mathbb{N}$
$n<2$ otherwise $b_q-b_p=100n\ge200$. Therefore $b_q-b_p=100$.
$$\implies\sum_{i=p+1}^{q}a_i=100$$