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
May 8, 2021
combinatorics
Problem Statement
Let . The land of Draconis has more than dungeons. Between two different Dungeons have exactly one path, but each path is a one-way street. Total Dragon cults share the territory; each path is controlled by exactly one cult. It is said that a dragon cult has established itself in a dungeon if there is both one a path beginning in and one a path ending in , both of which are controlled by . Prove that there is a cult , which has at least one dungeon controlled.