Question

Suppose that for every pair of cities in a country there is a direct one-way road connecting them in one direction or the other. Use mathematical induction to show that there is a city that can be reached from every other city either directly or via exactly one other city.

Short answer

By mathematical induction, the result \(P\left( n \right)\) is true for all positive integers \(n\).

Step-by-step solution

To recall the concepts and principles

Mathematical Induction:-The mathematical induction is defined as follows:

Step 1 (Base step): In this step, to prove that the statement is true for n=1.

Step 2(Inductive step): In this case, if the statement is true for n^th iteration, then to prove it is also true for (n+1)^th iteration.

It has given that every pair of cities in a country have a direct one-way road connecting them in one direction or the other.

To prove the result using principle of mathematical induction

Let the \(P\left( n \right)\) be the statement: There is a city that can be reached from every other city either directly or via exactly one other city, when the country has \(n\) cities.

Then by principle of mathematical induction,

For \(n = 2\):

For any two cities in the country, there is direct one-way road connecting them in one direction or the other.

Without loss of generality, assume that there is a direct one-way road connecting two cities, say, A and B (if not, then interchange A and B).

Then city B is reachable from every other city directly.

Thus, the result is true for \(n = 2\).

Hence, \(P\left( 2 \right)\) is true.

Now, consider the result is true for \(n = k\)\(\left( {k \ge 2} \right)\). It means, there is a city A that can be reached from either directly or via exactly one other city among first \(k\) cities.

Thus, \(P\left( k \right)\) is true.

Let’s prove the result for \(n = k + 1\).

Let B be the \(\left( {k + 1} \right)st\) city.

If there is a direct one-way road from B to A, then the city A can be reached from each city either directly or via exactly one other city.

Assume that there is a direct one-way road from A to B. If there is a direct one-way road from city B to city C and also a direct one-way road form city C to city A, then the city A can be reached from each city either directly or via exactly one other city.

If the above case is not possible for all cities C, the B is a city that can be reached from each city either directly or via exactly one other city.

Thus, the result is true for \(n = k + 1\).

Hence, \(P\left( {k + 1} \right)\) is true.

Hence, by the principle of mathematical induction, the result \(P\left( n \right)\) is true for all positive integers \(n\).