# Pigeonhole: 200 Balls into 101 Bins

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.

• What happens if each spaceship now contains exactly one monkey, and then you take them out? Commented Aug 27, 2021 at 6:28
• @TobyMak I'm not sure how that would help --- the size of the subset I'm interested in is not a fixed number. It might be $1$ but it also might be $50$, say. Commented Aug 27, 2021 at 7:17

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