Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
Associated Topics:
College Discrete Math

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search