Adivinar el valor de $n$

Question

$A$ $B$ jugar juego, $A$ elija $n$ donde $n \in \{1, 2,\ldots 1001\}=S$.

$B$ tiene que adivinar el valor de $n$ por la elección de un número de subconjuntos de a$S$, $A$ le dirá $B$ el número de subconjuntos de a $B$ elegir que contengan $n$.

Hacer la misma operación para $3$ tiempos, vamos a $k_1, k_2, k_3$ el número de subconjuntos que se $B$ elegir en el $1^{st}, 2^{nd}$ $3^{rd}$ del tiempo, respectivamente.

Encontrar el mínimo valor posible de $ k_1 + k_2+ k_3$ tal que $B$ siempre hace una suposición correcta.

Mi pensamiento :

El $1^{st}$ tiempo $B$ elija $\{1\}, \{1,2\}, \{1, 2, 3\}, \ldots, \{1, 2, 3, \dots, 334\}$.

Si $A$ dice $334$,$n=1$.

Si $A$ dice $1$,$n=334$.

Si $A$ dice $0$,$n\not\in \{1, 2, 3, \dots, 334\}$.

El $2^{nd}$ tiempo $B$ elija $\{335\}, \{335, 336\},\ldots, \{335, 336, 337 \dots, 671\}$.

El $3^{rd}$ tiempo $B$ elija $\{672\}, \{672, 673\},\ldots, \{672, 673, 674 \dots, 1001\}$.

Answer 1

En la primera ronda preguntas seis. \begin{eqnarray*} \{ i \mid i \equiv 1 \pmod 7 \} \\ \{ i \mid i \equiv 1 \pmod 7 \text{ or } i \equiv 2 \pmod 7 \} \\ \vdots \\ \{ i \mid i \equiv 1 \text{ or } 2 \text{ or } 3 \text{ or } 4 \text{ or } 5 \text{ or } 6\pmod 7 \} \\ \end{eqnarray *}

En la segunda ronda preguntas $10$\begin{eqnarray*} \{ i \mid i \equiv 1 \pmod {11} \} \\ \{ i \mid i \equiv 1 \text{ or } 2 \pmod {11} \} \\ \vdots \\ \{ i \mid i \equiv 1 \text{ or } 2 \text{ or } 3 \text{ or } 4 \cdots 10 \pmod {11} \} \\ \end{eqnarray *}

En la tercera ronda preguntas $12$\begin{eqnarray*} \{ i \mid i \equiv 1 \pmod {13} \} \\ \{ i \mid i \equiv 1 \text{ or } 2 \pmod {13} \} \\ \vdots \\ \{ i \mid i \equiv 1 \text{ or } 2 \text{ or } 3 \text{ or } 4 \cdots 12 \pmod {13} \} \\ \end{eqnarray *}

El valor se deduce utilizando el Teorema chino del resto. y el valor óptimo de $k_1+k_2+k_3$...

Answer 2

Una manera de probar un límite más bajo aquí es mediante la observación de en la $i$-ésima ronda, $k_i+1$ potenciales respuestas de $B$. Así, una estrategia de uso de $k_1$ $k_2$, $k_3$ establece en las primeras tres rondas y luego ganar seguro que tiene que satisfacer que $(k_1+1)(k_2+1)(k_3+1) \geq 1001$, puesto que necesita ser capaz de distinguir todas las opciones posibles de $1001$ de $S$.