很好的分析

来源: dynamic 于 2008-06-12 11:19:14 [] [旧帖] [给我悄悄话] 阅读数 : 0 (783 bytes)
回答: 来道关于猜数字的难题 由 dynamic 于 2008-06-11 15:50:59

除了最后一步过于理想化之外，前面的分析都是做这道题目的关键。最后一步的问题在于似乎把这个题目看成了一个静态的问题，而事实上在Bob寻找最佳的猜数策略的同时，Alice也在试图找最佳的撒谎策略，使得Bob需要猜的次数尽量多。按照这个式子，当n足够大的时候撒谎和不撒谎需要的次数一样多，显然是不可能的。

要解这个问题首先要考虑的是如何表示一个状态。你上面的集合和图表的表示方式已经切中了要害。不过这里有很重要的一点：我们不应该考虑Alice猜的那个数，转而应该考虑她没猜的那些数。每一步Alice告诉我们的信息其实是“我没猜集合S中的数”。那么我们在S中的每个数上画一个叉。一旦一个数得到了两个叉，我们就确定它不是Alice猜的数了。而Bob可以确定Alice的数当且仅当其它的数都得到了两个叉或以上。

所以一个合适的状态就是：当前多少个数得到了一个叉，多少个数零个叉（剩下的数都已经被排除，可以不做考虑）。

所有跟帖： 

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

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

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

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

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

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

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

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

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

请您先登陆，再发跟帖！