In Tlaxcala, there is a transportation system that works through buses that travel from one city to another in one direction . A set $S$ of cities is said beautiful if it contains at least three different cities and from each city $A$ in $S$ at least two buses depart, each one goes directly to a different city in $S$ and none of them is $A$ (if there is a direct bus from $A$ to a city $B$ in $S$, there is not necessarily a direct bus from $B$ to $A$). Show that if there exists a beautiful set of cities $S$, then there exists a beautiful $T$ subset of $S$, such that for any two cities in $T$, you can get from one to another by taking buses that only pass through cities in $T$. Note: A bus goes directly from one city to another if it does not pass through any other city.
Problem
Source: Mathematics Regional Olympiad of Mexico Center Zone 2016 P6
Tags: combinatorics
x3yukari
13.11.2021 17:04
Call the desired condition of $T$ satisfactory.
Suppose there exists a city $c_1$ that we cannot get to from a city $c_2$ in $T.$ This implies that the city $c_3$ that leads to $c_1$ also cannot be reached by the two cities that $c_2$ lead to, the city $c_4$ that leads to $c_3$ cannot be reached by the two cities that lead to the two cities $c_2$ lead to, and so on. In general, any city that leads to $c_1$ eventually cannot be reached by any city that leads to $c_2,$ and any city that $c_2$ leads to cannot lead to any city that leads to $c_1.$ Since there is always another city leading to any city leading to $c_1,$ and any city that $c_2$ leads to always leads to another two cities in turn, the only way this can happen is if there is a cycle of cities that the cities leading to $c_2$ stay within. But then consider this cycle $Q.$ It's also a beautiful set, since each city in it leads to another two cities in turn. So if a set is not satisfactory, there exists a smaller beautiful subset of the set. Since the smallest possible set (of 3 cities) is satisfactory, for any $S$ there exists a satisfactory subset.