SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Question

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.

Accepted Answer

In general, we can replace 64 and 2016 by n and 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 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 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.