MHB What is the solution to Problem of the Week #172?

[Ackbach]

Here is this week's POTW:

-----

A number of different objects has been distributed into $n$ boxes $B_{1}, B_{2}, \dots ,B_{n}.$ All the objects from these boxes are removed and redistributed into $n+1$ new boxes $B_{1}^{*}, B_{2}^{*}, \dots , B_{n+1}^{*},$ with no new box empty (so the total number of objects must be at least $n+1$). Prove that there are two objects each of which has the property that it is in a new box that contains fewer objects than the old box that contained it.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

No one solved this week's POTW. Here is a solution I found online:

Spoiler

Represent the situation as a bipartite graph where one color class are the $B_{i}$'s; the others are the $B^*_{j}$'s - hereafter referred to as the $A_{j}$'s. We can do this by letting each edge connecting $B_{i}$ to $A_{j}$ represent an object that is moved from $B_{i}$ to $A_{j}$.

Now fix $n$ and induct on the total number of edges $k$. Note $k >= n + 1$. Induct on $k$.

Base: If $k=n+1$, exactly one of the $B_{i}$'s has degree two; the rest have degree $1$. Said $B_{i}$ must be adjacent to an $A_{m}$ and an $A_{j}$ each with degree one. Those edges are the objects you want.

Induction: Suppose it holds for $k - 1$ and look at a situation with $k$ edges. Now if the graph is such that there exists two adjacent vertices each with degree $> 1$, remove the edge connecting them. The new graph satisfies the situation of the problem and the induction hypothesis. If not, then it must be that every edge touches a vertex with degree $1$. Say there are $a$ degree one $B$'s adjacent to degree one $A$'s, $b$ degree one $B$'s adjacent to non-degree one $A$'s, and $c$ non-degree one $B$'s adjacent to degree one $A$'s. Then $n = a + b + c$. If $c > 0$ we are done, as we can pick one of the $B$'s of this class and two of the edges connected to that $B$. If $c = 0$ then the total number of $B$'s is $n = a + b$ and the total number of edges is $k = a + b$. Since $k >= n + 1$ this is impossible. So $c > 0$ and we're done.