There are n studio apartments in a building. Some of the apartments are connected with each other by direct phone line. Prove that it is possible to assign to each apartment a female or a male in such way that each person has direct connection with at least as many people of the opposite sex as he/she has with people the same sex.
Asked
Active
Viewed 531 times
2
-
2This can hardly be proof-verification unless others see things, that I don't ;-) – String Oct 05 '13 at 23:45
-
I apologize for my ignorance. I did not know what tags were appropriate. – Jebediah Oct 06 '13 at 03:05
1 Answers
5
Assign the apartments in a way that maximizes the number of direct lines connecting a male to a female. Consider any tenant, assumed w.l.o.g. to be male. If he were connected to more men than women, then replacing him with a woman would increase the number of male-female connections, contradicting the assumed maximality.
By a standard "compactness" argument [*], the result can be generalized to locally finite graphs, i.e., the number of apartments may be infinite, but each one is connected to only finitely many others.
The result easily generalizes to any number of sexes. To put it in standard graph-theoretic terminology:
Theorem. Given a locally finite graph $G$ and a nonempty finite set $S$, we can find a function $f:V(G)\to S$ such that, for any $x\in V(G)$ and any $s\in S$, we have $$|\{y\in N(x):f(y)=s\}|\ge|\{y\in N(x):f(y)=f(x)\}|.$$
[*] In case anyone is interested, here is (one version of) the "compactness argument" used to get from the finite to the locally finite case. Let $F$ be the set of all functions $f:V(G)\to S$. Viewed as the Tychonoff product of copies of $S$ endowed with the discrete topology, $F$ is a compact space. For each vertex $x$, let $K_x$ be the set of all functions $f\in F$ such that the displayed inequality holds at $x$ (for all $s\in S$). Note that $K_x$ is a closed set. (The assumption of local finiteness is used here.) I claim the the family $\{K_x:x\in V(G)\}$ has the finite intersection property, i.e., that $\bigcap_{x\in X}K_x\ne\emptyset$ for each finite set $X\subseteq V(G)$. This follows from the finite case of the theorem, applied to the finite graph obtained by restricting $G$ to the finite set consisting of the vertices in $X$ and their neighbors. (Local finiteness is used again here.) Hence, by compactness, we have $\bigcap_{x\in V(G)}K_x\ne\emptyset$, Q.E.D.
bof
- 6,156
-
-
@David "Without loss of generality." It's a conventional expression used by mathematicians, when making a simplifying assumption, to indicate that the full result will follow from the ostensibly weaker statement which will be proved. The justification here is the fact that the assumptions in force (given in the problem or in specifying the kind of assignment to be used) treat males and females symmetrically. – bof Oct 06 '13 at 03:21