Competition problem — Combinatorics

Library / /84 of 105

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:

Martha is a chicken who lives in a coop whose finitely many residents have a definite "pecking order": for every pair of distinct chickens, exactly one pecks the other. (However, it is not necessarily true that if $X$ pecks $Y$ and $Y$ pecks $Z$ , then $X$ pecks $Z$ .) A chicken $X$ is called a "leader" of the coop if every other chicken is pecked by $X$ or pecked by a chicken who is pecked by $X$ . Prove that if no one in the coop pecks more chickens than Martha, then Martha is a leader.

Solution

Solution:

Suppose that no one pecks more chickens than $M$ , yet $M$ is not a leader; we will seek a contradiction. Let $X_{1}, X_{2}, \ldots, X_{n}$ be the chickens pecked by $M$ . Since $M$ is not a leader, there is a chicken $N$ who is neither pecked by $M$ nor by any of the $X_{i}$ . But it is given that of any two distinct chickens, one pecks the other; hence, $N$ pecks all of $M, X_{1}, X_{2}, \ldots, X_{n}$ . Thus, we have found at least $n+1$ chickens pecked by $N$ . But $M$ only pecks $n$ chickens. Since we assumed nobody pecked more chickens than $M$ , we have a contradiction, as needed.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.