5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Re-reading your question, it occurred to me that there's an implied assumption in the problem which makes perfect sense mathematically but none at all in real life. Namely: when the people living in an overpopulated apartment quarrel and leave to different apartments, they all move out of their old apartment and now they're living in those different apartments. $\endgroup$ May 2 '21 at 19:35
  • 1
    $\begingroup$ There is an unstated fact in the book solution: S is always an integer. If S could take arbitrary real values, then the process need not terminate, since S could reduce by smaller and smaller increments at each step and never fall below the threshold where all the $a_i$ are less than 15. $\endgroup$
    – alephzero
    May 3 '21 at 2:21
  • $\begingroup$ As an alternative to (a) $S$ is always an integer, it would be enough to observe either (b) $S$ always increases by at least $1$ or (c) there are only finitely many possible states. $\endgroup$ May 3 '21 at 3:07
7
$\begingroup$

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:

  • Justified in its existence by our later proof that it will decrease every day until we're done. That's all we need for this proof to work, and so you can think of $S$'s definition as an "algebraic trick".
  • Intuitively motivated as the following quantity: how many pairs of people living in the same apartment are there? It makes sense that this quantity ought to decrease when the inhabitants of a crowded apartment split up.

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.

$\endgroup$
3
  • $\begingroup$ Thanks. That was really helpful. $\endgroup$
    – F Nishat
    May 3 '21 at 13:34
  • $\begingroup$ With regards to the claim: A) It is not stated for $ k = 15$, so you can't apply it later. (I suspect this is just a typo) B) You likely want the condition to be "$\forall i \leq k$, there exists at least $i$ apartments with at least $16-i$ people". (the same proof works) Otherwise, for (say) $k = 15$, we could have 15 apartments with 1 person in each, satisfying your condition. (Ah, but I also see how you could apply the counting argument subsequently, so it might just be clarifying that part.) $\endgroup$
    – Calvin Lin
    May 4 '21 at 8:25
  • $\begingroup$ @CalvinLin (A) was just indeed a typo. "For all $i \le k$" would be redundant, though; that's just a combination of the lemma for $1, 2, \dots, k$. Applying the current condition for some fixed $k$ is all we need to know a lower bound on $a_k$. $\endgroup$ May 4 '21 at 12:50
1
$\begingroup$

At least for 1 and 2:

  1. Why is S needed to be considered?

At a larger-scale level, the solution attempts to find a property of the system that is:

  • a nonnegative integer
  • will decrease to a smaller integer each time overpopulated apartments quarrel and split up

In doing so, we can see that there can only be a finite number of quarrels before the "property" reaches 0 and can therefore no longer decrease (since it must be nonnegative).

In this solution, the property happens to be the number of handshakes possible at the start of the day, though there could be other properties that fill the same duty.

S doesn't "need" to be considered, it just happens to be a property that happens to satisfy the two points I listed above, so it is what we use.

  1. Shouldn't the quantity be same all the time?

Not sure what you mean by 'same all the time' but the next 2 equations below the blue one prove that this quantity is always <= -1.

$\endgroup$
0
1
$\begingroup$

It may be easier to follow the solution in the context of a graph.

In the solution, $S$ is the number of edges of the graph $G$ where the graph’s vertices represent the residents and the edges mean “live in the same apartment.” The graph $G$ at any moment is a union of disjoint complete graphs, one for each apartment. A complete graph on $a$ vertices has $a(a-1)\over2$ edges.

The blue quantity is the change in the number of edges of $G$ if all residents of one apartment leave that apartment and move to separate other apartments.

The specific calculations show that when an “overpopulated” apartment is vacated, the number of edges of $G$ decreases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.