Here's the original problem:
Alice tells Bob "I have thought of an integer between 1 and 2000. Tell me 1000 numbers. If your set contains my number, I'll give you this prize." Bob really wants the prize so he pleads "May I at least ask you some yes/no questions about your number?" "Hm..." Alice thinks, but then smiles, "Sure, as many as you need. But I may lie some of the time." "Now that's not very helpful..." Bob replies, "...well, come to think of it, as long as you promise not to lie more than nine consecutive times, I'm game." Alice doesn't believe Bob has a strategy, so she agrees.
However Bob has a strategy. How can he find a thousand numbers, one of which is with a 100% certainty Alice's?
It's relatively easy to show that Alice's upper bound of 2000 is irrelevant, and to then find a strategy that reduces the candidates for her number to ${2}^{k}$, where $k$ is the number of consecutive lies she's allowed to tell. In the particular problem, Bob can easily find 512 candidates for Alice's number.
However if $s$ is the minimum size of the final set, it can be shown that if $k\ge2$ then $k<s<2^k$. It can also be shown that for $\lambda \in \mathbb{R}$ and $1<\lambda<2$ there exists a large $k$ for which $\lambda^k<s<2^k$. Still I'm stuck on finding the minimum $s$ for a given $k$.
Here are my thoughts about it (which may be in the wrong direction):
Let's call the set of candidates for Alice's number $C=\{c_1, c_2, ... c_n\}$.
After every answer of hers, we can calculate the number of consecutive lies she has told had her number been any of $C$. Let's call this set $L=\{l_1, l_2, ... l_n\}$.
Each question of Bob can be reduced to "Does your number belong to a specific subset $Q$ of $C$?", which partitions $C$ into two parts ($Q$ and $C \setminus Q$). Alice's answer will increment the corresponding elements of $L$ for one of the parts and set the others to zero. If any member of $L$ becomes $k+1$, its corresponding member of $C$ is eliminated.
This shows us that Alice doesn't need to choose a number. She needs to focus on maintaining $|C|$ as big as possible. Then each of the elements of $C$ is "her number". So her best strategy should not be dependent on a particular member of $C$.
We may now forget the initial problem statement and focus on partitioning $C$ in the aforementioned way and then when it's impossible for Bob to eliminate a member of $C$, $s=|C|$.
I'm lost here, though. I don't have any good ideas except prohibitively complex brute force simulations for a given $k$.
