MathDB

The kingdom of Anisotropy consists of

n

cities. For every two cities there exists exactly one direct one-way road between them. We say that a path from

X

Y

is a sequence of roads such that one can move from

X

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

N_{AB}

denote the maximal number of paths in a diverse collection of paths from

A

B

. Similarly, let

N_{BA}

denote the maximal number of paths in a diverse collection of paths from

B

A

. Prove that the equality

N_{AB} = N_{BA}

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

.
Proposed by Warut Suksompong, Thailand

C4

Problems(1)