In a building there are $119$ inhabitants who live in $120$ apartments (several inhabitants can live in the same apartment). We call an apartment overcrowded if $15$ or more people live in it. Every day in some overcrowded apartment (if there is one) its inhabitants have a fight and yes they all go to live in a different apartment (which may or may not be already inhabited). Should you always terminate this process?
Problem
Source: Mathematics Regional Olympiad of Mexico West 2017 P3
Tags: combinatorics
28.10.2022 17:41
any solutions?
28.10.2022 18:32
First Solution: (by a friend) Let $P_i$ be the number of people in apartment $i$, we will show that after each fight the sum $\displaystyle \sum \limits _{i=1}^{120}P_i^2$ decreases by at least $2$. Since the sum is always positive, the process terminates. Assume WOLG that the people in apartment $1$ fight and move to apartments $2,\ldots ,P_1+1$, then the value of the sum after the fight is $\displaystyle 0^2+\sum \limits _{i=2}^{P_1+1}(P_i+1)^2+\sum \limits _{i=P_1+2}^{120}P_i^2$. Hence the difference is\begin{align*}\Delta & =\sum \limits _{i=2}^{P_1+1}(P_i+1)^2+\sum \limits _{i=P_1+2}^{120}P_i^2-\sum \limits _{i=1}^{120}P_i^2 \\ & =\sum \limits _{i=2}^{P_1+1}(2P_i+1)-P_1^2 \\ & =2\sum_{i=2}^{P_1+1}P_i+ P_1-P_1^2 \\ & <2(119-P_1)+P_1-P_1^2 \\ & =238-P_1-P_1^2 \\ & <238-15-15^2 \\ & =-2, \end{align*}as claimed. Second Solution: (by my brother) If an apartment has a fight at a night $N$, then it has at least $15$ persons in the night $N$. The apartment that fights the night $N+1$ has at least $14$ persons in the night $N$ (at most $1$ person moves into the apartment). The apartment that fights the night $N+2$ has at least $13$ persons in the night $N$ (at most $2$ persons move into the apartment). $\vdots$ The apartment that fights the night $N+14$ has at least $1$ person in the night $N$ (at most $14$ persons move into the apartment). Observe that the people and the apartments are all distinct because people only move when they fight and you can't overcrow an empty apartment in less than $15$ nights. If the process lasted at least $15$ nights we should have at least $1+2+\cdots +15=120$ persons. Hence the process terminates after $14$ nights (at most).