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 that results from the Pigeonhole principle, 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][1], 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][1]?

Thank you very much.

  [1]: https://opendsa-server.cs.vt.edu/ODSA/Books/valpo/ece-252dsa/spring-2017/A-B/html/BoundSearch.html