Here is a problem from the book 102 Combinatorial Problems: From the Training of the USA IMO Team by Titu Andreescu and Zuming Feng:
Original problem: A total of $119$ residents live in a building with $120$ apartments. We call an apartment overpopulated if there are at least $15$ people living there. Every day the inhabitants of an overpopulated apartment have a quarrel and each goes off to a different apartment in the building (so they can avoid each other). Is it true that this process will necessarily be completed someday?
Extension (Self-made): If after $n$ days the process is completed, what is the maximum value of $n$?
Solution from the book
Let $p_1,p_2,\cdots,p_{120}$ denote the $120$ apartments, and let $a_i$ denote
the number of residents in apartment $p_i$. We consider the quantity
$$\color{red}{\textrm{S=$\frac{a_1(a_1-1)}{2}+\frac{a_2(a_2-1)}{2}+\cdots+\frac{a_{120}(a_{120}-1)}{2}$}}$$
(Assume that all the residents in an apartment shake hand with each other at the beginning of the day, then quantity $S$ denotes the number of the handshakes in that day.) If all $a_i < 15$, then the process is completed and we are done. If not, without loss of generality, we assume that $a_1\ge15$ and that
the inhabitants in $p_i$ go off to different apartments in the building. Assume that they go to apartments $p_{i_{1}},p_{i_2},\cdots,p_{i_{a_1}}$. $\color{blue}{\textrm{On the next day, the quantity is changed by an amount of }}$ $$\color{blue}{\textrm{$a_{i_1}+a_{i_2}+\cdots+a_{i_{a_1}}-\frac{a_1(a_1-1)}{2}$}}$$ which is positive as $$a_{i_1}+a_{i_2}+\cdots+a_{i_{a_1}}\le119-a_1\le119-15=104$$
and $$\frac{a_1(a_1-1)}{2}\ge\frac{15\cdot14}{2}=105$$
Hence the quantity is decreasing during this process. On the other hand, $S$
starts as a certain finite number and $S$ is nonnegative. Therefore this process
has to be completed someday. $\blacksquare$
My question
I don't understand the solution (especially the texts which are in colored), even after trying to understand it for almost two days. I have the following questions:
- Why is $S$ needed to be considered?
- Shouldn't the quantity be same all the time, as there is no change in the number of residents? (text in $\color{blue}{\textrm{blue}}$)
- And how to solve the extension of the problem?
Can someone explain the solution or provide a different and easier solution?
Thanks in advance.
Best Answer
The general motivation for $S$ is the technique of monovariants. To show that the desired state (no more quarrels) will happen eventually, we show that we are always "making progress" toward the state in some sense. To show that we are making progress, we need to have a way to track progress.
The specific formula for $S$ is:
Why does the quantity change? Well, the number of people in different apartments changes. Suppose that on day 1, we have $19$ residents in the first apartment ($a_1 = 19$), $5$ residents in each of the next $20$ apartments ($a_2 = a_3 = \dots = a_{21} = 5$) and nobody in any of the other apartments ($a_{22} = \dots = a_{119} = 0$). Then on day 1, we have $$S = \binom {19}{2} + 20 \cdot \binom 52 + 99 \cdot \binom 02 = 371.$$ On day 1, the inhabitants of the first apartment quarrel. Let's say that all $19$ of them move to already-populated apartments. Now $a_1 = 0$, $a_2, \dots, a_{20}$ increase to $6$, and the rest stay the same. On day 2, we have $$ S = \binom 02 + 19 \cdot \binom 62 + \binom 52 + 99 \cdot \binom 02 = 310. $$
To solve the extension (and give a simpler proof!), we prove the following claim:
Claim. For $k\le 15$, in order for there to be at least $k$ apartment fights, on day $1$ there must be at least $k$ different apartments with $16-k$ or more people.
Proof. Suppose there have been $k$ apartment fights, for some $k\le 15$. An apartment that's had a fight gains a person after every subsequent fight, for at most $k-1<15$ people by the end; so no apartment can have had two fights yet. Therefore all $k$ fights have been in different apartments. By symmetry, let's assume the $i^{\text{th}}$ fight has been in apartment $i$.
Then apartment $i$ has gained at most one person after each of the first $i-1$ fights: $i-1$ new people total. In order to have at least $15$ people for the $i^{\text{th}}$ fight, it must have started out with at least $15 - (i-1) = 16-i$ people. In particular, apartments $1, 2, \dots, k$ all must have at least $16-k$ people. QED
Without loss of generality, assume that $a_1 \ge a_2 \ge \dots \ge a_{120}$ on day 1. The the condition in the claim says that $a_k \ge 16-k$.
This condition cannot hold for all of $k=1, 2, \dots, 15$. If it did, we'd get $a_1 \ge 15$, $a_2 \ge 14$, $a_3 \ge 13$, and so on through $a_{15} \ge 1$. But then there are at least $$ a_1 + a_2 + \dots + a_{15} \ge 15 + 14 + \dots + 1 = 120 $$ people, and we know there are only $119$.
Therefore $15$ fights cannot happen, and so the process must be completed after the $14^{\text{th}}$ day. This bound is tight: one way to have the process last $14$ days is to start with populations $$ a_1 = 15, a_2 = 14, a_3 = 13, \dots, a_{14} = 2, a_{15} = \dots = a_{120}=0 $$ and have the $15$ inhabitants of an apartment go to the first $15$ other apartments by number after each fight.