Número mínimo de preguntas para identificar un subconjunto

Question

Esta es una pregunta de curiosidad.

Hace poco me encontré con el siguiente problema :

Dados tres enteros $k,m, n$ tal que $m+k\leq n$ . Un amigo elige un subconjunto $S\subseteq\lbrace1,\ldots,N\rbrace$ con $k$ elementos, y tienes que adivinar cuál es. Puedes hacerle preguntas concretas de la forma: para cada pregunta eliges un subconjunto $G \subseteq\lbrace1,\ldots,N\rbrace$ con $m$ elementos y preguntarle si tiene elementos en común con $G$ y obtienes una respuesta "Sí" o "No". ¿Cuántas preguntas necesitas para encontrar el subconjunto?

---

Intento

Estuve trabajando en esta cuestión durante algún tiempo sin ningún avance, dejé $f(n,m,k)$ sea el número mínimo de preguntas necesarias. Me interesaba especialmente $f(8,4,4)$ . Logré encontrar una fórmula para casos muy específicos por ejemplo :

1. Obviamente $f(n,m,0)=0$
2. $f(n,n-1,1)=n-1$ y $f(n,1,k)=n-1$
3. $f(n,n-2,1)=f(n,2,1)=\lfloor \frac n 2 \rfloor+1$
4. Algunas fórmulas complicadas para $k=2$ pero no estoy seguro de que sean correctos nada para $k\geq 3$ .
5. Parece que $f(n,m,k)=f(n,n-m,k)$ pero no pude probarlo.

He añadido la condición $m+k\leq n$ porque a veces no es posible encontrar el subconjunto (creo que es suficiente para asegurar la existencia de una solución, pero no estoy seguro de que sea necesario).

Pregunta : ¿Existe un algoritmo para resolver el problema? para calcular $f(n,m,k)$ ? o cualquier fórmula para $k=3,4$ ?

Answer 1

Podemos obtener estimaciones asintóticas. Para cualquier $m$ y $k$ , si $n$ es lo suficientemente grande (digamos $n > km$ ), tenemos $$ \left\lfloor\frac{n-k}m\right\rfloor \le f(n,m,k) \le \left\lfloor \frac nm \right\rfloor + f(km,m,k) $$ así que en particular $f(n,m,k) = \frac nm + O(1)$ como $n\to \infty$ .

El límite inferior se debe a que, aunque se adivinen conjuntos disjuntos cada vez, el primer $\lfloor\frac{n-k}m\rfloor-1$ las respuestas podrían ser "no" y, sin embargo, no reducir las cosas a una sola opción.

Para el límite superior, comience por adivinar intervalos disjuntos de longitud $m$ hasta que $k$ las respuestas son "sí", o bien $k-1$ respuestas son "sí" y hay como máximo $m$ elementos restantes. (Esto requiere como máximo $\left\lfloor \frac nm \right\rfloor$ pasos). A continuación, la unión de los $k$ Los intervalos con respuestas afirmativas son un conjunto de tamaño $km$ que contiene todos los elementos de $S$ para que podamos utilizar el $f(km,m,k)$ estrategia en él, que toma un número de conjeturas independiente de $n$ . (Podríamos hacerlo mejor aquí, ya que podemos aprovechar muchos elementos que sabemos que no están en $S$ pero esto es sólo un límite superior).