Q9 Matemática  (Tournament Of Towns 2016)

Existem cidades de $64$ em um país e alguns pares de cidades são conectados por estradas, mas não conhecemos esses pares. Podemos escolher qualquer par de cidades e descobrir se elas estão conectadas ou não. Nosso objetivo é determinar se é possível viajar de uma cidade a outra por uma sequência de estradas. Prove que não existe um algoritmo que nos permita fazê-lo em perguntas com menos de $2016$. (Proposto por Konstantin Knop)