时间戳

首页 > 解决方案 > 猜猜猜猜游戏的组数？

algorithm - 猜猜猜猜游戏的组数？

问题描述

我在 math.stackexchange 上问过这个问题，但没有得到任何答案。

问题是要解决一个两人猜数字游戏。设第一人称A，第二人称B。xA在 1 和一个上限之间选择一个数字n。B以 (L,R) 的形式向A提出查询，如果数字存在于 (L,R) 区间内， A将回答是/否。

B将需要询问一组查询来唯一确定数字x。所以问题是找到这样不同的查询集的数量，以便B能够唯一地确定x，而不管 的值是什么x。 A将查询的答案作为整个系列返回——B仅在完成所有查询后才批量获得是/否响应。

例如，假设n是 2。可能的查询集是，

{(1,1)}, 
{(2,2)}, 
{(1,1),(2,2)},
{(1,1),(1,2)},
{(2,2),(1,2)}, 
{(1,1),(2,2),(1,2)}

问题：如何确定这些查询集中的哪一个将唯一标识A可能选择的任何整数？

我可以认为是我们需要以某种方式将所有可能的数字从 1 到基本上隔离n，否则不可能唯一地确定数字。但我不知道如何处理这些信息。

标签： algorithmmath

解决方案

设置 #1 来检测一个数字：

1设置所有单对：{{1,1},{2,2},...,{N,N}}

设置 #2 来检测一个数字：

N单对集合，除了一对：{{1,1},{2,2},..,{x-1,x-1},{x+1,x+1},..,{N,N}}

不能帮助识别数字的对：

N-1长度为 2 的对：{1,2},{2,3},,{N-1,N}

N-2长度为 3 的对：{1,3},{2,4},,{N-2,N}

...

2与长度的对N-1：{1,N-1},{2,N}

1与长度的对N：{1,N}

无用对的总数为：

K = (N-1) + (N-2) + ... 2 + 1 = N*(N-1)/2

无用集合的总数为：

Z = C(K,0) + C(K, 1) + ... + C(K, K) = 2^K

查询集数

为了找到答案，我们需要将所有正确的集合与所有其他类型的集合结合起来。

ANSWER = (Number of set #1 + Number of sets #2) * Z = (1 + N) * (2^K)

UDP：答案是错误的，请参阅下面的评论

推荐阅读