Organizar los números naturales $1$ a través de $n$ en un orden aleatorio (el orden es desconocido y se tiene una distribución uniforme). Ahora hacer una secuencia de hipótesis en cuanto a que el número está en que ranura, un número y una ranura en un tiempo. Le dijo después de cada adivinar si es correcto o no. El juego termina cuando el orden de la $n$ números ha sido determinada. Para el peor caso y el caso promedio, respectivamente, hay una estrategia que tenga menor número de suposiciones que el trivial de la eliminación?
Respuesta
¿Demasiados anuncios?
Bobson
Puntos
636
No hay ninguna estrategia que lleva menos de $n(n-1)/2$ en el peor de los casos. Considere la posibilidad de una estrategia (un menú de lo que preguntas, basadas en la historia de las respuestas anteriores). Considere un caso en el que todas las preguntas resultar en respuestas negativas (puede haber muchos de estos casos, si la estrategia aleatoriamente las preguntas). Supongamos que la estrategia concluye que la permutación es $P=(k_1,k_2,...,k_n)$. Es decir, el número de $1$ está en la ranura $k_1$, $2$ en la ranura $k_2$, ... y de número de $n$ en la ranura $k_n$. Considere la posibilidad de otra permutación $P'$ obtenido a partir de $P$ por intercambio de posiciones de los números de $i$$j$. La única forma en que la estrategia podría haber determinado que la permutación es $P$ e no $P'$ es preguntar a uno de los siguientes dos preguntas: (1) número de $i$ en la ranura $k_j$? o (2) número de $j$ en la ranura $k_i$? Por lo tanto, para cada par $(i,j)$, la estrategia debería haberle preguntado al menos una pregunta. Desde entonces, no se $n(n-1)/2$ pares, la estrategia debería haberle preguntado al menos $n(n-1)/2$ preguntas.
