Colocación: 200 pelotas en 101 casillas

Question

He encontrado la siguiente pregunta en este sitio web:

Tienes 200 monos colocados en 101 naves espaciales de forma que cada nave contiene al menos un mono. Demuestra que hay un subconjunto de naves espaciales que contienen un total de exactamente 100 monos.

Sospecho que hay una forma elegante de "construir" palomas y agujeros que aún no he descubierto. Agradecería cualquier consejos (preferiblemente que no sean soluciones completas) que puedan llevarme hasta allí. Gracias de antemano.

Answer 1

Dejemos que $i^{th}$ nave espacial tienen $a_i$ monos. Para $1\le r\le101$ dejar $b_r=\sum_{i=1}^{r}a_i$
Tenemos $1\le b_1<b_2<...<b_{101}=200$ .

Dividir $101$ $b_i$ 's en $100$ cajas numeradas $0,1,2,3..,99$ tal que $b_i$ lo que deja un remanente $k$ cuando se divide por $100$ va en la caja $k$ .
Por el principio de la colombofilia hay una caja con 2 elementos digamos $b_p$ y $b_q$ con $p<q$ .
Entonces $b_q-b_p=100n$ donde $n\in\mathbb{N}$
$n<2$ De lo contrario, $b_q-b_p=100n\ge200$ . Por lo tanto, $b_q-b_p=100$ .
$$\implies\sum_{i=p+1}^{q}a_i=100$$