IMO 2021 Shortlist C4

IMO 2021 Shortlist C4

Category: Combinatorics

Problem

ThekingdomofAnisotropyconsistsofn cities. Foreverytwocitiesthereexistsexactly one direct one-way road between them. We say that a path from X to Y is a sequence of roads such that one can move from X to Y along this sequence without returning to an already visited city. A collection of paths is called diverse if no road belongs to two or more paths in the collection. Let A and B be two distinct cities in Anisotropy. Let NAB denote the maximal number of paths inadiverse collectionofpaths fromA toB. Similarly,letNBA denote the maximalnum- ber of paths in a diverse collection of paths from B to A. Prove that the equality NAB “NBA holds if and only if the number of roads going out from A is the same as the number of roads going out from B.