A researcher is studying the social dynamics of chicken coops. In each coop, for each pair of chickens $A$ and $B$, there is a pecking relationship: either $A$ pecks $B$ or $B$ pecks $A$ (but not both). This does not have to be transitive - it is perfectly possible that $A$ pecks $B$ pecks $C$ pecks $A$.
The researcher notices something interesting: in every coop he visits, there exists a "king chicken" $K$ with the following property: for any other chicken $C$, either $K$ pecks $C$ or there exists some third chicken $G_C$ such that $K$ pecks $G_C$ pecks $C$.
Prove that this observation has nothing to do with the behavior of chickens; no matter how the pecking order is arranged, there will always be such a king.
Note: the pecking order can be thought of as a tournament, also known as a complete oriented graph. The problem in these terms is to show that for any tournament, there exists a node such that any other node is at most two directed steps away.
Posted: Jul 21 '12
Seen: 36 times
Last updated: Jul 21 '12
