来道关于猜数字的难题

相信猜数字的游戏不少人都见过了。Alice先默想一个1~N之间的数字，然后Bob来猜。每次Bob都只能问一个yes or no的问题，而Alice则要如实相告。问Bob怎样猜可以用最少的轮数确保正确的猜出这个数。

比如下面是一个典型的游戏，N = 4:

Bob: 这个数是奇数么？
Alice: 不是。
Bob: 这个数是2么？
Alice: 不是。
Bob: 我知道了，这个数是4！

那么Bob就猜对了，总共猜了3次。可以证明，即使Bob足够聪明，最坏情况下也要猜3次。
类似的，如果N = 100的话，最坏情况下8次就可以确保猜出。

终于有一天Alice和Bob厌倦了这个无聊的游戏。于是他们更换了规则，允许Alice在回答问题的时候撒一次谎（也可以不撒谎，但不允许撒一次以上的谎）。假设Bob足够聪明，遵循了最优策略来猜，那么他要多少次就能确保猜出Alice所想的数呢？假设N = 100，答案是多少呢？

所有跟帖： 

• cool problem :) -idiot94- ♂ (0 bytes) () 06/11/2008 postreply 16:32:12

• My guess : 2^x / (1+x) >= 100, x + 1 = 12 -ettubrute- ♂ (1426 bytes) () 06/11/2008 postreply 21:29:01

• 很好的分析 -dynamic- ♂ (783 bytes) () 06/12/2008 postreply 11:19:14

• 回复：很好的分析 -HF:- ♀ (745 bytes) () 06/12/2008 postreply 12:16:22

• 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

• Does this mean that 9 guesses is enough? -ettubrute- ♂ (136 bytes) () 06/12/2008 postreply 13:07:32

• why do you think so? -dynamic- ♂ (348 bytes) () 06/12/2008 postreply 13:13:20

• I just realize my mistake -ettubrute- ♂ (0 bytes) () 06/12/2008 postreply 13:17:03

• 回复：很好的分析 -HF:- ♀ (461 bytes) () 06/12/2008 postreply 14:15:52

• for N=100, 10 questions to ask -HF:- ♀ (834 bytes) () 06/12/2008 postreply 20:13:24

• I think that there is a mistake at the eighth guess -ettubrute- ♂ (284 bytes) () 06/12/2008 postreply 20:36:40

• 回复：来道关于猜数字的难题 -大愚- ♂ (148 bytes) () 06/14/2008 postreply 06:01:34

• 信息角度 -hqw2000- ♀ (454 bytes) () 06/17/2008 postreply 18:55:16

• I am not convinced -ettubrute- ♂ (491 bytes) () 06/18/2008 postreply 08:05:42