algorithm - 猜猜游戏的套数是多少？

Question

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

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

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 的所有可能数字，否则无法唯一确定数字。但我不知道如何处理这些信息。

Answer 1

设置 #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:答案有误，见下方评论