MathDB

10

Part of 2009 QEDMO 6th

Problems(1)

2^n dungeons and n Dragon cults in the land of Draconis

Source: 6th QEDMO problem 10 (22. - 29. 8. 2009) https://artofproblemsolving.com/community/c1512515_qedmo_200507

5/8/2021
Let nāˆˆNn \in N. The land of Draconis has more than 2n2^n dungeons. Between two different Dungeons have exactly one path, but each path is a one-way street. Total nn Dragon cults share the territory; each path is controlled by exactly one cult. It is said that a dragon cult KK has established itself in a dungeon DD if there is both one a path beginning in DD and one a path ending in DD, both of which are controlled by KK . Prove that there is a cult KK, which has at least one dungeon controlled.
combinatorics