1

There are n islands and initially all islands are separated and each form their own group. When a bridge is constructed between two arbitrarily chosen islands they become a connected group. As long as there are separated island groups, arbitrarily pick two groups and construct a bridge between two arbitrarily-chosen islands (one from each group). As a consequence, the two selected groups are merged into one single connected group.

Prove, using the principle of strong induction on the number of islands n, that no matter how the groups and islands are selected in each step, the total number of bridges obtained by the above procedure is always nāˆ’1.

I am not sure how to use strong induction on this or where to even start. Any help would really be appreciated.

H. Davies
  • 41
  • 4
  • 1
    Again?!? This is the third time this question has come up in as many days .. or even less, I can;t quite remember. And no one seems to be able to take the first step. ā€“ Bram28 Mar 09 '17 at 20:49
  • 2 islands = 1 bridge, for every island you add, you need another bridge. Just translate that into maths. ā€“ c.. Mar 09 '17 at 20:51

1 Answers1

2

HINT:

The last bridge connects two island groups A and B. Say A consists of $k$ islands and thus $B$ of $n-k$ islands. By inductive hypothesis, it takes ___ bridges to connect all the islands from A into the island group A, and it takes ____ to form group B. So, to connect everything it takes ____ + ____ + 1 = ... bridges

Bram28
  • 100,612
  • 6
  • 70
  • 118