Guess the number, with lying allowed

Question

I am pretty sure you guys are aware of the Guess the Number game (there seem to be quite a few questions here already) where Alice thinks of a positive integer and Bob tries to guess it. Alice responds by either by saying "You got it", "Low", "High". The usual strategy which Bob can do, is to do a binary search which would guess the number in O(log n) guesses, where n is the number Alice was thinking about.

I have always wondered about the variant where Alice was allowed to lie.

Suppose now Alice was allowed to lie a constant number of times (known before hand both to Alice and Bob), but only was allowed to lie when responding "High", "Low" (i.e. if Bob guesses the number correctly, she has to admit that).

Is it still possible that Bob can guess the number in O(log n) guesses?

What if Bob was allowed additional queries like "How many times have you lied so far?" (which Alice has to respond truthfully)? Are O(log n) queries still possible?

EDIT: What if the number of lies was allowed to be O(logn) too, and the additional queries were: Have you lied more than x times? and Alice was allowed to lie about them...

Apologies for the EDIT.

Answer 1

Run the usual binary search algorithm. Either you get the answer, or you get an inconsistency (an empty candidate set). If you get an inconsistency, Alice must have lied at least once. Restart the binary search. Unless I'm missing something, after O(k*log(n)) steps you will get the answer (plus a lower bound on how many times she lied). You don't need to know k a priori.

Answer 2

I think it's still O(log n), because you specified that Alice can only lie a constant number of times. This means she can at most multiply the amount of guesses Bob makes by a constant.

Imagine that Alice can lie 5 times. Now, no matter when alice lies, she'll end up having to contradict herself. Bob will notice this, and can start his binary search over. Alice is also restricted to lying within O(log n) guesses, or else Bob will guess the number correctly and Alice loses her chance.

So, in the worst case, where Alice lies five times, each /just before/ Bob gets the answer, she has simply caused Bob's binary search to take 6*(log n) guesses (five lies + one correct answer), which is still O(log n).