Suggest a Book

# Pecking order

Level: unknown

posted Jul 21 '12

aa1062
31 4

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.

Source: folklore
delete retag edit

## Stats

Posted: Jul 21 '12

Seen: 36 times

Last updated: Jul 21 '12