Combinatorics: Matching students and teachers from different schools

75 Views Asked by At

Let $s_1$, $s_2$$\dots$, $s_n$ be $n$ different schools. Given are $x_i$ teachers and $y_i$ students from school $s_i$, so that $\sum\limits_{i=1}^nx_i=\sum\limits_{i=1}^ny_i$. Do a one to one match between teachers and students.

It was found that no matter how this was done, there exists a pair of people from the same school.

Find the necessary and sufficient relation between $x_1$$\dots$, $x_n$ and $y_1$$\dots$, $y_n$.

I think that an obvious sufficient relation would be $\max\limits_ix_i\ge\sum\limits_{k\ne i}y_k$ or $\max\limits_iy_i\ge\sum\limits_{k\ne i}x_k$. In these cases, the school $s_i$ must have a teacher and a student who are matched.

Is this also the necessary condition?

Maybe the Hall theorem helps, but I'm not sure how.

1

There are 1 best solutions below

0
On BEST ANSWER

You have proven that the existence of $i$ for which $x_i>\sum_{k\neq i} y_k$ is sufficient (note that you need a strictly greater than sign here, where you wrote $\ge $). I will prove that this is necessary as well.

Let $T=\sum_{i=1}^nx_i$. Consider the bipartite graph with $2T$ vertices, one for each teacher and student. A student is adjacent to a teacher whenever they are from different schools. We know that there does not exist a selection of $T$ edges whose endpoints cover all of the teachers and all of the students. Therefore, Hall's marriage theorem implies that the Hall condition must fail. That is, there must exist an integer, $k$, and a set $S$ of $k$ teachers, such that the number of students adjacent to at least one these teachers is fewer than $k$.

I claim that all of the teachers in $S$ came from the same school. Indeed, if there were teachers from two different schools in $S$, then every student would be adjacent to at least one teacher in $S$, but this would violate the property "there are fewer than $k$ students adjacent to some teacher in $S$." Therefore, there exists a particular index, $i$, such that all the teachers in $S$ came from $s_i$, so $k\le x_i$. On the other hand, the number of students adjacent to some teacher in $S$ is then $\sum_{k\neq i} y_k$, so $\sum_{k\neq i}y_k<k$. We conclude that $x_i> \sum_{k \neq i}y_k$.

The exact same logic implies that the condition $y_i>\sum_{k\neq i}x_k$ for some $i$ is also necessary.