Induction HypothesisDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/