3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ K(n+1) is a suspension of K(n). try to think about your induction in this way. $\endgroup$
    – Zackkenyon
    Oct 10, 2017 at 19:08

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.