Competition problem — Combinatorics

Library / /20 of 26

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

Let $n$ be a positive integer. There are $n$ islands, and you want to build some number of bridges so that there is a path between any two islands. (Each bridge joins a pair of islands, and can be traveled in both directions.) At least how many bridges must you build?

Solution

Solution:

You need to build at least $n-1$ bridges. Imagine you start at one island and are only building bridges that start from islands you can already reach. Then, each new bridge connects you to only one new island, so to be connected to all of them, you need $n-1$ bridges. Conversely, $n-1$ bridges is enough, since you can go from island 1 to island 2, then from island 2 to island 3 and so on in one path until you have reached all the islands.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.