Every road in country X is one-way. Every pair of cities is connected by exactly one direct road (going in only one direction). Show that there exists a city which can be reached from every other city either directly or via a route that goes through at most one other city. (Hint: Use induction on the number of the cities.)
I have no clue. The base case is n = 2 and the theorem is true for that case. I don't see any pattern as n increases so I don't know what exactly happens to the roads when n is changed to n + 1
Edit:
So I just started drawing a bunch of cities in a circle, and I see something. Let's say we have n cities. If each city is connected to every other city by one road, then City 1 is connected to Cities 2, 3, 4, ….n. City 2 is connected to 3,4,5,6…n. 3 is connected to 4,5,6,7…n. And finally n-1 is connected to n. In all cases, the last city, n, has roads coming to it from every other city. Does this get me anywhere??
Best Answer
We claim that a city $C_{k}$ (not necessarily unique) with the maximum number of roads leading into it, has the required property.
Suppose to the contrary there is some city $C_{j}$ so that there is no road leading from $C_{j}$ to $C_{k}$ directly or through one stop. Suppose there are exactly $m$ roads leading out from $C_{j}$, to cities which are not $C_{k}$. Then for each of these cities, roads have to lead out from $C_{k}$ to them as well. Further, the road between $C_{k}$ to $C_{j}$ also has to lead out from $C_{k}$ to $C_{j}$. Thus, we have at least $m+1$ roads leading out from $C_{k}$, whereas we had exactly $m$ roads leading out from $C_{j}$. This gives a contradiction to the fact that $C_{k}$ has the maximum number of roads leading into it.