猜数字，允许说谎

我敢肯定，你们都知道猜数字游戏（这里似乎有不少问题），爱丽丝认为这是一个正整数，而鲍勃试图猜测它。爱丽丝回应说：“你明白了”，“低”，“高”。 Bob可以做的通常策略是进行二进制搜索，它可以猜测O（log n）猜测中的数字，其中n是Alice正在考虑的数字。猜数字，允许说谎

我一直想知道Alice允许说谎的变体。假设现在Alice允许说谎的次数恒定（在Alice和Bob之前都已知），但只有在响应“高”，“低”时才允许说谎（即，如果Bob正确猜测了该数字，她不得不承认这一点）。

Bob仍然有可能猜出O（log n）猜测中的数字吗？

如果Bob允许其他疑问，例如“您到目前为止撒谎了多少次？”会怎么样？（爱丽丝必须如实回应）？ O（log n）查询仍然有可能吗？

编辑：如果谎言的数量也被允许为O（logn），那么额外的查询是：你撒谎超过x次？爱丽丝被允许在他们身边撒谎......

编辑道歉。

来源

2011-04-15 user127.0.0.1

如果允许的谎言的数量 - 比如说k - 是独立于n而固定的，Bob可以简单地问每个问题2k + 1次，并且用O（log（n））消失。 – 2011-04-15 18:00:36

只需按照“多少次你说谎”的每一个“标准”问题 - 并相应地切换答案。结果：同样数量的问题仿佛爱丽丝从不撒谎。 – pmg 2011-04-15 18:01:58

我喜欢它。两个直接的想法（1）根据概率映射空间是什么（2）一个计划试图识别或不正确的答案是什么样的？ – 2011-04-15 18:02:53

运行通常的二进制搜索算法。要么你得到答案，要么你得到不一致（一个空的候选集）。如果你不一致，爱丽丝至少应该撒谎一次。重新开始二进制搜索。除非我错过了一些东西，在O（k * log（n））步后，你会得到答案（加上她说谎的次数的下限）。你不需要先知道k。

来源

2011-04-15 18:06:49 foxcub

我认为它仍然是O（log n），因为你指定爱丽丝只能躺在一个固定的次数。这意味着她最多可以将Bob所做的猜测数量乘以常数。

想象一下，爱丽丝可以撒谎5次。现在，无论爱丽丝何时离开，她最终都不得不自责。鲍勃会注意到这一点，并可以开始他的二进制搜索。 Alice也被限制在O（log n）猜测之内，否则Bob会正确猜测数字，Alice将失去机会。因此，在最差的情况下，在爱丽丝谎言的五次，每次/刚刚/鲍勃得到答案时，她只是导致鲍勃的二进制搜索采取6 *（log n）猜测（五个谎言+一个正确的答案），这仍然是O（log n）。

来源

2011-04-15 18:07:20 Cephron

猜数字，允许说谎

回答

相关问题