我很确定你们都知道Guess the Number游戏(这里似乎有很多问题),Alice认为这是一个正整数,Bob试图猜测它.爱丽丝通过说"你得到它","低","高"来回应.Bob可以做的通常策略是进行二进制搜索,这将猜测O(log n)猜测中的数字,其中n是Alice正在考虑的数字.
我一直想知道允许爱丽丝撒谎的变种.
假设现在爱丽丝被允许撒谎一定次数(事先知道爱丽丝和鲍勃),但只有在响应"高","低"时才被允许撒谎(即如果鲍勃正确猜出数字,她必须承认).
Bob是否仍然可以猜出O(log n)猜测中的数字？
如果鲍勃被允许进行其他查询,例如"你到目前为止有多少次撒谎？" (爱丽丝必须如实回应)？O(log n)查询仍然可能吗？
编辑:如果谎言的数量也允许为O(logn),并且其他查询是:你撒谎超过x次怎么办？爱丽丝被允许撒谎他们......
为EDIT道歉.
运行通常的二进制搜索算法.要么得到答案,要么得到不一致(空候选集).如果你出现不一致,Alice必须至少撒谎一次.重启二进制搜索.除非我遗漏了某些东西,否则在O(k*log(n))步骤之后你会得到答案(加上她撒谎多少次的下限).你不需要知道ka先验.