I have an integer X that 1<=X<=N. You can provide a set and ask if X is in it. I may lie but at any time there's not more lie than truth. How small set can you guarantee X is in?
E.g. if N=100, by asking set [1,50] you can know a set of size 50. First answer must be truth, otherwise lie(1) is more than truth(0).