It is well established that the least number of steps of solving the Hanoi tower problem for $n$ disks is $2^{n}-1$. Now consider the following problem:
Player 1 picks a natural number between 1 and $M$ (inclusive), and Player 2 tries to guess it. After each incorrect guess , Player 1 responds "higher" or "lower". Assuming Player 2 has $n$ guesses, what is the largest value of $M$ for which there is an algorithm that guarantees success?
As it turns out the largest value of $M$ that guarantee success is - you guessed it, $2^{n}-1$. The algorithm can informally be described as follows:
Given an interval of numbers $[a,b]$ pick $k=\lfloor \frac{a+b}{2} \rfloor$ as your first guess. If this is the correct answer then stop. If Player 1 responds "higher" then proceed to do the same step for the interval $[k+1,b]$. If Player 1 responds "lower" then repeat the initial step for the interval $[a,k-1]$. Continue to do this for $n$ steps.
The validity of this theorem can be proved by mathematical induction.
Now, as you can see the Tower of Hanoi and the second problem have the same optimal solution. Is this a pure coincidence or does this reveal a deeper connection between the two problems?
In a sense the answer is neither of your suggestions. There is a connection in the number of moves, which you have noted, and there is a connection in that both can be solved by repeatedly roughly cutting them in half (which is where the $2^n$ part comes from).
The cutting in half part of the Tower of Hanoi goes: if I want to move $n$ disks from $A$ to $C$, I can do it by moving $n-1$ disks from $A$ to $B$, one disk from $A$ to $C$ and then $n-1$ disks from $B$ to $C$. But this strategy reveals a whole lot more structure than is encoded by simple guesses.
At each stage in the Tower of Hanoi there is one move which leads to the optimal solution. In the guessing game, either half can be valid. The guessing game can also end early.
I would say there is a connection (the halving process), which is more than coincidence, but not a particularly deep connection.