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 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 $2016$ questions. 

(Proposed by Konstantin Knop)
To prove that there is no algorithm which enables us to determine whether it is possible to travel from any town to any other by a sequence of roads in fewer than \(2016\) questions, we will use concepts from graph theory and combinatorics.

1. **Definitions and Setup:**
   - Let \(V\) be the set of \(64\) towns.
   - Let \(K\) be the set of pairs of towns for which we have inquired about the existence of a road.
   - Let \(E\) be the subset of \(K\) where the inquiries have been answered affirmatively (i.e., there is a road).
   - Define a pargraph \(\mathcal{H} = (V, K, E)\).

2. **Tree-Pluripotent Pargraph:**
   - A pargraph \(\mathcal{H} = (V, K, E)\) is tree-pluripotent if for any \(u \in \binom{V}{2} \setminus K\), \(\mathcal{H}\) is consistent with a total pargraph whose underlying graph is a tree containing \(u\) as an edge.
   - Consistency means that the pargraph \(\mathcal{H}\) can be extended to a total pargraph (where \(K = \binom{V}{2}\)) that is a tree.

3. **Proposition 1:**
   - Given a tree-pluripotent pargraph \(\mathcal{H} = (V, K, E)\) with \(K \subsetneq \binom{V}{2}\), the minimal realization of \(\mathcal{H}\) is disconnected.
   - **Proof:**
     - By hypothesis, there exists \(u \in \binom{V}{2} \setminus K\).
     - There exists a total pargraph \(\widetilde{\mathcal{H}} = (V, \binom{V}{2}, \widetilde{E})\) consistent with \(\mathcal{H}\) whose underlying graph is a tree containing \(u\) as an edge.
     - The minimal realization of \(\mathcal{H}\) is a subgraph of this tree that lacks at least one edge (namely \(u\)), and is therefore disconnected. \(\blacksquare\)

4. **Proposition 2:**
   - Given a tree-pluripotent pargraph \(\mathcal{H} = (V, K, E)\) and \(u_0 \in \binom{V}{2} \setminus K\), there exists a tree-pluripotent pargraph \(\widetilde{\mathcal{H}} = (V, K \cup \{u_0\}, \widetilde{E})\) consistent with \(\mathcal{H}\).
   - **Proof:**
     - If every total pargraph consistent with \(\mathcal{H}\) whose underlying graph is a tree contains the edge \(u_0\), then \(\widetilde{\mathcal{H}} = (V, K \cup \{u_0\}, \widetilde{E} \cup \{u_0\})\) is the desired tree-pluripotent pargraph.
     - If there exists a total pargraph \(\mathcal{H}' = (V, \binom{V}{2}, E')\) consistent with \(\mathcal{H}\) whose underlying graph is a tree not containing the edge \(u_0\), then:
       - For any \(u \in \binom{V}{2} \setminus (K \cup \{u_0\})\), the tree-pluripotency of \(\mathcal{H}\) implies the existence of a total pargraph \(\mathcal{H}'' = (V, \binom{V}{2}, E'')\) consistent with \(\mathcal{H}\) whose underlying graph is a tree containing the edge \(u\).
       - If the edge \(u\) fails to occur in the underlying graph of \(\mathcal{H}'\), consider the unique path connecting its endpoints, delete an edge in this path not in \(K \cup \{u_0\}\), and adjoin \(u\) to \(E'\) to obtain a total pargraph consistent with \(\widetilde{\mathcal{H}}\) whose underlying graph is a tree containing the edge \(u\).
       - Thus, \(\widetilde{\mathcal{H}}\) is tree-pluripotent. \(\blacksquare\)

5. **Application to the Problem:**
   - Identify the towns with elements of the set \(64 = \{0, \dots, 63\}\).
   - Interpret the state of our knowledge after some number of queries as the pargraph \(\mathcal{H} = (64, K, E)\).
   - Our knowledge suffices when either the underlying graph of any total pargraph consistent with \(\mathcal{H}\) is connected or disconnected.
   - If we have asked \(K \subsetneq \binom{64}{2}\) questions, the pargraph \(\mathcal{H}\) may remain tree-pluripotent.
   - This \(\mathcal{H}\) is consistent with a total pargraph whose underlying graph is connected and one whose underlying graph is disconnected.

6. **Conclusion:**
   - There is no procedure that guarantees knowledge of the connectivity of the graph being probed in fewer than \(\binom{64}{2} = 2016\) questions.

The final answer is \(\boxed{2016}\)