Optimally determining connectivity of a graph.
Source: Tournament of the Towns 2016, Spring A level, Senior.
September 30, 2016
combinatoricsalgorithmConnected graphsgraph theory
Problem Statement
There are 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 or not. Our aim is to determine whether it is possible to travel from any town to any other by a sequence of roads. Prove that there is no algorithm which enables us to do so in less than questions. (Proposed by Konstantin Knop)