Competition problem — Combinatorics

Library / /51 of 155

Combinatorics Difficulty 5.7 AIME, harder Prove it Saudi Arabia

There are $64$ towns in a country, and some pairs of towns are connected by roads but we do not know these pairs. We may choose any pair of towns and find out whether they are connected by a road. Our aim is to determine whether it is possible to travel between any two towns using roads. Prove that there is no algorithm which would enable us to do this in less than $2016$ questions.

Solution

In general, we can replace $64$ and $2016$ by $n$ and $\frac{n(n-1)}{2}$ .
The given problem can be converted into the graph theory by considering each town as a vertex in the graph $G$ and each road connects two towns as the edge. So there are exactly $\frac{n(n-1)}{2}$ undirected edges in this graph.
We need to prove that in all cases, we need to do the operation of checking connection between two vertices exactly $\frac{n(n-1)}{2}$ times to make sure the connectivity of each pair of vertices.
This can be done by using induction on number $n$ or using the candy distribution idea.

Remark. This problem is inspired by the Problem 3 of the International Olympiad in Informatics (IOI) 2014.

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 and solution reproduced as published; topic and difficulty added by this site.