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$.