Adivinar un subconjunto de $\{1,...,N\}$

Question

Elijo un subconjunto aleatorio de $S$ de $\{1,\ldots,N\}$, y usted tiene que adivinar lo que es. Después de cada adivinar $G$, te digo, que el número de elementos en $G \tapa de S$. Cuántas conjeturas necesita?

Answer 1

Un evidente límite superior es de $N$ las consultas, ya que usted puede probar cada elemento de forma individual. Por otro lado, se necesitan al menos $\Omega(N/\log N)$ consultas: $$ N de bits de información necesarios para identificar el destino de subconjunto, y cada consulta puede producir en la mayoría de los $O(\log N)$ bits de información, ya que cada consulta tiene sólo $O(N)$ respuestas posibles. Para ver que el límite superior no está afilada, considere la siguiente estrategia para $N=5$, lo que lleva a más de $4 de$ consultas:

1. Supongo que $\{1,2,3,4,5\}$. Si el resultado es $0$ o $5$, tenemos la respuesta. Si el resultado es $1$ o $4$, la interseccion de búsqueda (por el miembro único o el único elemento que falta) nos da la respuesta en más de tres consultas. Supongamos que el resultado es $2$ (la estrategia para $3$ es el mismo por simetría).
2. Supongo que $\{1,2\}$. Si el resultado es $2$, tenemos la respuesta. Si el resultado es $0$, entonces la interseccion de búsqueda en $\{3,4,5\}$ (para el único elemento que falta) nos da la respuesta en dos más consultas. Supongamos que el resultado es $1$. Entonces sabemos que la respuesta es $\{a,b\}$ $a \in \{1,2\}$ y $b \in \{3,4,5\}$.
3. Supongo que $\{1,3\}$. Si el resultado es $2$, tenemos la respuesta. Si el resultado es $0$, entonces la respuesta es $\{2,b\}$ $b\in\{4,5\}$, y una consulta más, da la respuesta. Supongamos que el resultado es $1$. Entonces sabemos que la respuesta es $\{1,4\}$, $\{1,5\}$, o $\{2,3\}$.
4. Supongo que $\{1,4\}$. La respuesta es $\{1,4\}$ si el resultado es $2$ o $\{1,5\}$ si el resultado es $1$ o $\{2,3\}$ si el resultado es $0$.

Este ejemplo da una mejor cota superior asintótica $4N/5$. Parece probable que la respuesta correcta es estrictamente $o(N)$ (es decir, finalmente, menos de $cN$ para cualquier fijo $c$), pero si es o no es $\Theta(N/\log N)$, yo no puedo decir.

Answer 2

La respuesta es $N$.

Deje que $F(N)$ ser el número de conjeturas necesarios para la determinación de la $S$ de $\{1,...,N\}$ cuando el tamaño de la $S$ es desconocido y dejar que $H(N)$ ser el número de conjeturas necesarios para la determinación de la $S$ de $\{1,...,N\}$ cuando el tamaño de S es conocido. Obviamente $H(0)=0, H(1) = 0, F(0)=0,F(1)=1$.

Supongamos que conocemos el tamaño $|S|.$ Después de una suposición, el problema se reduce a determinar $G \cap$ S de G, donde sabemos que $|G \cap S|$ y $G^C \cap S$ de $G^C \cap \{1,...,N\}$, donde sabemos que $|G^C \cap S|$. Así

$$H(N) = 1+\min_{|G|} H(|G|) + H(N - |G|).$$

Ahora supongamos que $H(N) = N-1$ para $N=1,...,$ n. Entonces por nuestra hipótesis de inducción, $H(|G|) + H(n+1-|G|)=|G|-1 + n-|G| = n-1$ cuando $\min(|G|,N-|G|) > 0$. Cuando $|G|=0$ o $|G|=n+1$, $H(|G|) + H(n+1-|G|)=H(n+1)$, sin embargo, es imposible que $H(n+1) = 1 + H(n+1)$, entonces $|G|=0$ y $|G|=n+1$ no puede ser la minimización de las opciones de $|G|$. Por lo tanto llegamos a la conclusión de que la inducción por que $H(N) = N-1$.

Ahora vamos a demostrar que $F(N) = N$.

Suponga que $F(N) = N$ para $N=1,...,$ n. Tenemos $$F(N) = 1+\min_{|G|} H(|G|) + F(N - |G|).$$ y así, por un razonamiento similar proceso como antes, llegamos a la conclusión de que la inducción por que $F(n+1) = n+1$.

Answer 3

$M$ denota el conjunto solución, $|M|$ denota su cardinalidad (número de elementos).

Tenga en cuenta que si supongo que $\{1\dots N\}$, entonces usted tendrá que responder con $|M|$.

Ahora puedo fuerza bruta su conjunto mediante la eliminación de los elementos de $\{1\dots N\}$, uno por uno. Cada vez que su respuesta disminuye voy ha identificado un elemento de la solución. Por inducción, su respuesta tiene que llegar a cero con el tiempo. Por el tiempo que he se han identificado todo $x\in M$. Me llevará uno de los más supongo que para ganar el juego.

Utilizando el algoritmo descrito más arriba, me imagino que en más de $N+1$ veces.

Estoy bastante seguro de que no se puede hacer mejor que $O(n)$ en el peor de los casos (yo no ofrecen ninguna prueba).