I'm interested on the following nice problem that is somewhat standard in CS, but I was surprised on the lack of references on the optimal algorithm to this problem.
Ana and Banana plays the following game: Banana creates a tree on vertices $1$, $2$, $\dots$, $n$ while not giving any information about it to Ana (except the fact that it has $n$ vertices $1$, $2$, $\dots$, $n$ and that it's a tree). After the graph was created, Ana is allowed to choose any two vertices $A$, and $B$ and ask Banana the value of $\text{dist}(A, B)$. Assuming that Banana always answers honestly, what is the minimum amount of queries required for Ana to find two vertices such that its distance is maximal in this graph regardless of how Banana creates this tree.
As the title says, we can by BFS show that we can find the diameter in $2n-4$ moves, the strategy is to simply start at a random vertex $A$, make queries to all the others vertices of the tree, pick the one vertex $X$ that maximizes the $\text{dist}(A, X)$ giving $n-1$ queries, then repeat the process with $X$ and notice that we don't need to make all the $n-2$ queries to find $B$ that maximizes $\text{dist}(B, X)$, as we can just notice that the information will be redundant.
The proof that this algorithm works can be given by contradiction and can be found here. Moreover, I have the heavy suspicion that $2n-4$ is the best possible. Let the minimum number be $f(n)$, then it is easy to see that $f(3) = 2$, and to prove that $f(4) = 4$, say that we have a graph with vertices $1$, $2$, $\dots$, then connect two vertices if Ana asks for their distance and label their edge with the distance. So, assume FTSOC that $f(4) = 3$, then we either have a vertex with degree $3$, or an "N" shape (notice that this graph can't be disconnected, so there are just two cases of tree to check). In the first case, put the label $1$, $2$, $1$ in some order, in case an "N" shape occurs, then label the middle diagonal with $2$. and the rest with $1$.
Update: It is possible to show the bound of $n$, re-imagine this problem as if B creates the tree as A makes queries, then B can always answer $1$ to a query of A if this query won't represent a cycle in the distance graph that I used in the above paragraph, and if it creates a cycle, B can just say the distance of the existing path. This shows that at least $n-1$ are necessary, I imagine that an approach can be made to show that achieving something like $n + \log n$ is possible.
Showing, however, that this is the best possible bound is very hard, the order of the queries matter, and so induction can't be applied very directly (I wouldn't rule out the possibility of some induction like argument). I'm thankful for a solution/references/improvements on this problem.
