Problem

Source: Swiss TST 2015. Problem 9

Tags: combinatorics



Let $n \geq 2$ be a positive integer. At the center of a circular garden is a guard tower. On the outskirt of the garden there are $n$ garden dwarfs regularly spaced. In the tower are attentive supervisors. Each supervisor controls a portion of the garden delimited by two dwarfs. We say that the supervisor $A$ controls the supervisor $B$ if the region of $B$ is contained in that of $A$. Among the supervisors there are two groups: the apprentices and the teachers. Each apprentice is controlled by exactly one teachers, and controls no one, while the teachers are not controlled by anyone. The entire garden has the following maintenance costs: - One apprentice costs 1 gold per year. - One teacher costs 2 gold per year. - A garden dwarf costs 2 gold per year. Show that the garden dwarfs cost at least as much as the supervisors.