I have the following problem:

Let Alice and Bob be two people playing games.

Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ per game, within any range given by Alice at some moment of the game.

The game Alice and Bob decided to play today takes place as it follows:

• Alice tells Bob a number $n$, with $n \geq 0$ and $n \in \mathbb{N}$.
• Alice tells Bob she will use Robo to generate a number $k \in \mathbb{N}$, with $0\leq k \leq n$ as range for $k$. Alice does not give any information about the actual generated value of $k$ to Bob.
• Alice challenges Bob to find out $k$.
• Alice only allows Bob to ask her questions of type "is $a_i = k$ ?", where $a_i$ represents some number Bob chooses to ask Alice about during his $i$-th question. Alice will only answer to these questions with "YES" or "NO".
• The advantage Bob has is that he can ask Alice as many questions of type "is $a_i = k$ ?" he wants.

Since Alice and Bob want to have time to play more games of this type, they need your help to find out what is the minimum number of questions Bob can ask Alice before Bob can be 100% sure of the value of $k$, i.e. what is the function $T(n)$ that tells them how many questions Bob must ask with his best game strategy in order to find out any possible $k$ Robo could generate in one game.

Since it is obvious that the problem asks for a lower bound within the worst-case scenario of the problem, I highly suspect (although I am unable to design a proof for it) that the problem is $\Omega(n)$ (i.e. the answer to the problem is $T(n) = n$), where $n$ is the number given initially as input.

My intuitive approach was the following:

1. The problem seemed very similar to me with the Unordered List Element Search problem, where Linear search (for as much as I know) is the optimal algorithm, with a lower bound of $\Omega(n)$, where $n$ is the number of elements in the array.

2. Bob can always discover $k$ after $n$ questions with his best strategy, i.e. the problem has a trivial $O(n)$ bound as long as we introduce the following conditions to the problem:

   • $\forall i, j: ( a_i \neq a_j )$ (Bob never repeats the same question)
   • $\forall i: ( a_i \in \mathbb{N} \land 0 \leq a_i \leq n )$ (Bob never asks for numbers outside of the range of $k$)

3. From {1} and {2}, we could deduce that we can replace the elements of the array of a Unordered List Element Search problem instance with the numbers Bob is asking Alice about in some instance of the game above.

I was kind of confident with this approach, but after reading this article, I seriously started thinking that maybe I could not simply solve it this way, since the difference between the two problems is that the above-presented problem contains a non-deterministic segment, i.e. the generation of $k$, and the proof to its lower bound may or may not be a little bit more sensible to this detail.

For this reason, I have the following question:

• Can anyone help me give a proof of the answer to the initial problem, a proof that has no "flaws" in the sense of the above-cited article?

Thank you very much.