回复：很好的分析

Here is a simple strategy, perhaps not the the optimal one.

Asking Alice to write the number in binary representation, with K=ceil(log2(N)) digits (fill the leading digits with 0 if the number Alice picked has less than K digits), then ask Alice, for each of the K digits, whether it is 0.
After the K questions, asked her: whether she has ever lied in the first K questions. If no, we know the answer already(the 'no' can not be a lie here).
If yes (now, she has lied, either in one of the first K questions or this last question, anyway, she can not lie going forward), we need further log2(K+1) questions to figure out on which question she lied.
So in the worst case, K+log2(K+1) questions needed, where K = ceil(log2(N))

所有跟帖： 

• brilliant answer... however that question is not allowed -dynamic- ♂ (154 bytes) () 06/12/2008 postreply 13:08:34

• 回复：brilliant answer... however that question is not allowed -HF:- ♀ (475 bytes) () 06/12/2008 postreply 13:24:54