很好的分析

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

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

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