Induction help... number of cities

Question

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??

Answer 1

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.

Answer 2

The answer by Aritro works and is more elegant, but if you must use induction, there's a way to do it using strong induction.

Label the city $A_1, \dots A_n$, and suppose $A_1$ is the city that can be reached from any other city through at most 1 other city. And now we add $A_{n+1}$. If the road between $A_1$ and $A_{n+1}$ leads to $A_1$ then we are done. So now we assume that road leads to $A_{n+1}$.

Divide the cities $A_2, \dots, A_n$ into three categories:

Category 1: the ones that lead directly to $A_{n+1}$.

Category 2: the ones where $A_{n+1}$ leads into it, but it leads into $A_1$

Category 3: the ones where $A_{n+1}$ leads into it, and $A_1$ also leads into it.

Obviously from category 1 we can reach $A_{n+1}$ easily. From category 2, we can also reach from that city through $A_1$ then to $A_{n+1}$.

If category 3 is empty, then $A_{n+1}$ is our required city, because from all the remaining cities ($A_1$, category 1, and category 2) we can reach $A_{n+1}$ through at most one other city.

So now we assume that category 3 is not empty.

Case 1: category 3 contains multiple cities.

We invoke the induction hypothesis one more time, ONLY on category 3 cities. There is a city say $B$ that satisfies the required property among category 3 cities. Then we assert that $B$ is our required city for all $n+1$ cities.

Meaning, from other cities in category 3, we can reach $B$ through at most 1 other city by the induction hypothesis. From cities in category 1, we can reach $B$ through $A_{n+1}$. From cities in category 2, we can reach $B$ through $A_1$.

Case 2: category 3 contains a single city, say $B$. We cannot invoke the induction hypothesis because the premise requires there are at least 2 cities, but we can still assert that $B$ is our required city. From any other cities ($A_1, A_{n+1}$, category 1, and category 2) we can reach $B$ either directly or through $A_1$ or $A_{n+1}$.