MathDB
The 24/7 party of 25 elves

Source: Germany 2024, Problem 3

June 14, 2024
combinatoricscombinatorics proposedgraph theoryDirected graphs

Problem Statement

At a party, 2525 elves give each other presents. No elf gives a present to herself. Each elf gives a present to at least one other elf, but no elf gives a present to all other elves. Show that it is possible to choose a group of three elves including at least two elves who give a present to exactly one of the other two elves in the group.