The participants to an international conference are native and foreign scientist. Each native scientist sends a message to a foreign scientist and each foreign scientist sends a message to a native scientist. There are native scientists who did not receive a message. Prove that there exists a set $S$ of native scientists such that the outer $S$ scientists are exactly those who received messages from those foreign scientists who did not receive messages from scientists belonging to $S$. Radu Niculescu
Problem
Source: Romanian IMO Team Selection Test TST 1999, problem 14
Tags: combinatorics proposed, combinatorics
25.09.2005 16:13
I always had a problem with the way this is formulated . For instance, the set $S$ could be taken to be empty if there were no native scientists which did not receive any messages, so this condition doesn't significantly change the problem, I think . Anyway, consider a maximal (with respect to inclusion) set $S$ of native scientists, which contains the set of native scientists who did not receive any messages (so that they are non-empty), and with the property that the set $S'$ of native scientists who received messages from those foreigner scientists who did not receive messages from the scientists in $S$ is disjoint from $S$. There exists at least one such set, namely the set of natives who did not receive messages itself. Let's show that such a set $S$, together with $S'$, covers the whole set $N$ of native scientists. Suppose we can find a native scientist $x_1$ in $N$, but outside both $S$ and $S'$. If he sends a message to a foreigner scientist who also receives a message from $S$, we can safely add $x_1$ to $S$ and leave $S'$ unchanged, thus contradicting the maximality of $S$. If, on the other hand, $x_1$ sends a message to some $y_1$ who does not receive any messages from $S$, two things ca happen: either $y_1$ sends a message to $x_2$, who also receives messages from other foreigners who do not receive messages from $S$, in which case we add $x_1$ to $S$ and leave $S'$ unchanged, or $y_1$ sends a message to $x_2$, and it's the only foreigner who does not receive messages from $S$ to do so. In this case, we add $x_1$ to $S$ and take $x_2$ out of $S'$. Either way, the existence of $S\cup\{x_1\}$ contradicts the maximality of $S$, and we have a contradiction. I hope it's correct.