Sue picks a number from 0 to 3.
Tom asks questions about the number, with yes/no answers. For example, "Is it odd" or "Is it 3?"
If Sue picked X, she is allowed to lie at most X times. For example, if she picked zero, she must always tell the truth. If she chose any other number, she can decide each question whether to lie, until she runs out of lies, after which she must tell the truth.
Tom wants to minimize the average number of questions. Sue wants to maximize it.
I think Sue's best strategy is random. Sometimes choose $0$, sometimes tell the truth when she doesn't have to. What is her strategy, and how many questions does Tom need on average?
Wei Hua Huang posed this in rec.puzzles newsgroup twenty years ago. I think we solved the worst-case number of questions, but not the average.
EDIT:
To compare, suppose Sue can pick 0 or 1, and may lie once if she picks 1.
Tom asks 'Is it 1?'. Suppose Sue says no. If she picked 1, then she has used up her lie. So, whether Sue picked 0 or 1, she has no lies left. Tom asks 'Is it 1?' again, and will get a correct answer.
Suppose Sue says yes to Tom's first question. She can't say yes if she picked $0$, so Tom now knows Sue picked $1$.
So Sue's best strategy is to say no, and it will take Tom two guesses.
We can verify each answer by asking:
Is it true to say, that if you were lying in the last question XOR you lie in this question, then $1$ is equal to $0$?
The answer for that question will be 'YES', if Sue told the truth in previous question and 'NO', if she lied, no matter if she's lying or telling the truth in this question.
Then we have:
Which gives us 4 questions to be sure about the number.
We can also use this method of verification to turn every 'Guess the natural number of a liar' to normal 'Guess the natural number' (number of questions is just doubled)