Question 175
In a country there are 64 cities. There are roads joining certain pairs of cities, but Bob does not know which ones (roads do not cross but may possibly pass over one another; moreover, roads can be travelled in both directions). Alice, on the other hand, knows the network perfectly. Bob may choose any pair of cities and ask Alice whether they are joined directly by a road. Bob's goal is to determine whether it is possible to travel from any city to any other (possibly using several successive roads). Show that there is no algorithm (that is, no strategy depending on Alice's successive answers) allowing him to know this for certain in fewer than 2016 questions.