Número mínimo de preguntas

Question

Estoy tratando de resolver el problema siguiente: $49$ distintos números se escriben en una tarjeta de celular de $7\times7$. Se permite para recoger las células de $3$ en el tablero y averiguar el conjunto de números escritos en ellos con una sola pregunta. ¿Cuál es el número mínimo de preguntas necesarias para preguntar para saber qué número está escrito en cada célula?

Answer 1

Organizar cada celda de la cuadrícula, en un bucle circular de todos modos que desee. Únicamente para determinar los números en $3$ células distintas, necesitará $3$ preguntas. Inicio de una arbitraria de la célula en el bucle circular, y el índice de ellos. La pregunta será sobre las células indexado $1,2,3$. El próximo será sobre las células indexado $3,4,5$ y así sucesivamente, y usted va a terminar en las células indexado $49,1,2$. Contando con ellos, usted va a necesitar 25 preguntas. El número de células no importa, de cualquier cuadrícula que contiene la $n$ células, usted necesitará $[n/2]$ preguntas si incluso, o $[n/2] + 1$, si es impar.

Answer 2

Aquí es una manera de encontrar un límite inferior. Se utiliza la idea de la 'árbol de decisión'. Al principio, cuando usted no ha pedido alguna pregunta hay $49!$ configuraciones posibles de la junta. Cuando se haga la primera pregunta que usted podría recibir $\frac{49*48*47}{3*2*1} = 18424$ respuestas diferentes. Ahora imaginemos un árbol de raíces $T$ donde los nodos son los conjuntos de todas las configuraciones posibles de la junta (el nodo raíz es, por supuesto, el conjunto de todos los $49!$ configuraciones). Los bordes de los árboles serán los diferentes respuestas que recibes cuando haces una pregunta. Así que cada nodo tiene $\leq 18424$ bordes. Usted puede ver fácilmente que el nodo $P$ es el padre del nodo $C$, $C \subseteq P$ (debido a que cada pregunta elimina algunas de las posibilidades). Usted hace cuando usted consigue un nodo $L$ contiene sólo una configuración posible (la configuración que usted está buscando). Este nodo es una hoja del árbol porque usted no tiene que hacer más preguntas. Por lo $T$ árbol debe tener al menos $49!$ hojas (una por cada una de las configuraciones posibles). El menor número de preguntas que usted necesita preguntarse a determinar la configuración a continuación, es el menos posible de la altura del árbol. El árbol con la altura mínima del curso es el de completar uno (cada nodo tiene exactamente $18424$ niños). En este tipo de árboles hay un práctico fórmula que vincula la altura de la $h$, el número de hojas de $l$ y el número de hijos por nodo $n$. Es decir, $$l = n^{h}$$

En su caso $49! \leq l = 18424^h$. Así que si mis cálculos son correctos $h \geq 15$. Ahora para comprobar si este es el mínimo que usted debe tratar de encontrar un verdadero algoritmo para resolver el problema de usar $15$ preguntas.