Induction Hypothesis

Date: 08/16/2003 at 09:20:49
From: Kiran Bajaj
Subject: Principal of Mathematical Induction

I am working on some difficult problems of Mathematical Induction.
Here is a statement to be proved:

Every road in Sikinia is one way. Every pair of cities is connected 
by exactly one direct road. Show that there exists a city that can 
be reached from every other city either directly or via at most one 
other city.

Date: 08/17/2003 at 08:21:23
From: Doctor Jacques
Subject: Re: Principal of Mathematical Induction

Hi Kiran,

Let n be the number of cities. We will proceed by induction on n.

As the problem only makes sense for n >= 2, we will use 2 as the base 
case.

If there are two cities, the theorem is obviously true: if the (only) 
road goes from A to B, it is possible to reach B from A in exactly one 
"hop."

Let us now assume that n >= 3, and that the theorem holds for n-1.

Let the n cities be called C[1] through C[n]. We will write C[i] -> C
[j] to mean that the road joining cities i and j goes from C[i] to 
C[j].

By the induction hypothesis, there is at least one city among C
[1], ... C[n-1] that can be reached from all the rest of those cities 
in at most two hops. As we are free to number the cities as we wish, 
we may assume that C[1] is such a city.

As it is possible to go from any city C[2], ..., C[n-1] to C[1], 
there is at least one city with a direct road going to C[1] 
(otherwise, all roads in C[1] would go outward, and it would not be 
possible to reach C[1] at all).

Let all the cities with direct roads to C[1] be C[2],..., C[k], with 
k <= (n-1) (once again, we may assign the numbers as we want). We 
have therefore four sets of cities:

(1) C[1].

(2) C[2], ..., C[k] : the cities with a direct road to C[1], i.e.
    C[j] -> C[1] for 2 <= j <= k.

(3) C[k+1], ..., C[n-1] : the cities without a direct road to C[1].
    As there is a road between any two cities, there is a road from
    C[1] to any of those cities, i.e. C[1] -> C[j] for
    (k+1) <= j <= (n-1)

(4) C[n]

Note that set (3) could be empty; the other sets are never empty.

Consider now the roads to and from C[n]. There are three possible 
cases:

Case 1:
-------
If C[n] -> C[1], then we can reach C[1] in one hop from C[n] also, 
and, as we already know that we can reach it in at most two hops from 
the other cities, the theorem is true in this case.

Case 2:
-------
If C[n] -> C[j] for at least one j between 2 and k, we can reach C[1] 
in two hops from C[n]:

  C[n] -> C[j] -> C[1]

and, in this case, the theorem is also true.

Case 3:
-------
The only case that remains is when we have C[j] -> C[n] for all j 
between 1 and k.

In that case, we have a direct route from C[j] to C[n], for j <= k.

If set (3) is empty, this accounts for all cities, and we are done.

Otherwise, consider now the remaining cities, i.e. set (3), and let
C[i] be one such city, i > k. It is possible to reach C[1] in two 
hops from C[j] (induction hypothesis), but not in one hop, because of 
the choice of i. As the only cities with a direct road to C[1] are 
those in set (2), this means that there is a direct road from C[i] to 
at least one city of set (2), i.e. we have, for some j:

  C[i] -> C[j] -> C[1]

with 2 <= j <= k. As we know that, in case 3, we have C[j] -> C[n], 
this gives a two-hop road from C[i] to C[n]:

  C[i] -> C[j] -> C[n]

and this shows that we can reach C[n] from all the other cities in at 
most two hops, i.e. the theorem is also true in this case.

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/