óptimo de clasificación

Question

Tengo una solución a la siguiente pregunta, pero soy incapaz de dar una prueba.

Dado el 25 de distintos números enteros, uno puede ordenar de 5 a la vez. ¿Cuál es el menor número de clasificación para obtener el más pequeño de los 3 números?

Answer 1

Hay una solución con 7 clases. Si podemos demostrar que 6 tipos no son suficientes para encontrar el más pequeño de 3 números, hemos terminado.

Cuando se busca el número más pequeño que uno puede eliminar de 4 números con cada tipo (de 5 números). Así que tenemos 6 tipos para eliminar los 24 números para, finalmente, encontrar el número más pequeño de los 25. Ahora vamos a mostrar que uno no puede evitar tener dos candidatos para el segundo número más pequeño después de las 6 clases.

• candidato 1: El segundo más pequeño de la 6ª tipo es un candidato para el segundo número más pequeño en total. (Para algunas estrategias que usted puede tener suerte y estar seguro de que este es el segundo número más pequeño; por ejemplo, si usted tome siempre el número más pequeño de una especie en la siguiente clase y, a continuación, lo que ocurre es que el número más pequeño de la 5ª especie es el segundo en la 6ª especie. Pero uno no puede forzar a esto).
• (potencial) candidato 2: Como se menciona en "el candidato 1" a tal candidato a la 2 para el segundo número más pequeño no tiene que existir. Pero para cada estrategia de una orden de cómo los números van en el tipo puede ser construido, s.t. un candidato 2 existe. Desde una estrategia de trabajo en todos los casos, sólo una construcción de número de pedido es suficiente para rechazarlo. En breve la posibilidad de un segundo candidato para el segundo número más pequeño puede argumentar de la siguiente manera: Entre los números de la 6ª tipo no va a ser el número más pequeño de la 5ª clase. Ahora bien, si este número resulta más pequeño en el 6 de sort (tenga en cuenta que cualquier número en la 6ª tipo podría ser el más pequeño debido a que en los primeros 5 tipo sólo 20 números podrían ser eliminados de ser el más pequeño), el segundo número más pequeño de la 5ª clase es también un candidato para el conjunto del segundo número más pequeño.

Así que necesitamos al menos un 7 de ordenación para encontrar el segundo número más pequeño (bajo cualquier orden de cómo los números se colocan en la clase de una determinada estrategia) y, por tanto, también para encontrar el más pequeño de 3 números.

Apéndice: Supongamos por ejemplo mostrar tales problemáticas número de órdenes de dos estrategias específicas. El orden de los números van en el tipo debe ser tal que el número más pequeño de la 5ª tipo es el número más pequeño (y por lo tanto el segundo número más pequeño de la 5ª tipo va a ser el "candidato de 2" para el conjunto del segundo número más pequeño). Sin pérdida de generalidad podemos suponer que los números a ordenar son 1,2,...25.

Estrategia 1: El número más pequeño de cada especie va en la siguiente clase.

Cuando los números están en el siguiente, casi a la inversa, el fin de 25,24,...8,7,2,1,6,5,4,3 y tomadas una tras otra según sea necesario obtenemos los siguientes tipos:

1. 25,24,23,22,21 -> 21,22,23,24,25
1. 21,20,19,18,17 -> 17,18,19,20,21
1. 17,16,15,14,13 -> 13,14,15,16,17
1. 13,12,11,10, 9 ->  9,10,11,12,13
1.  9, 8, 7, 2, 1 ->  1, 2, 7, 8, 9
1.  1, 6, 5, 4, 3 ->  1, 3, 4, 5, 6

De la clase, sólo ahora 1 < 2 y 1 < 3. Por lo tanto 2 y 3 podría ser el segundo número más pequeño.

Estrategia 2 (la solución de la pregunta original): el grupo de los números 5 y enviar a estos grupos en los 5 primeros tipos. A continuación, tomar el más pequeño de los números de los primeros 5 tipo y ponerlos en la 6ª especie.

Cuando los números están en el siguiente casi estricto orden ascendente 6,7,...25,1,2,...5 y tomadas una tras otra según sea necesario obtenemos los siguientes tipos:

1.  6, 7, 8, 9,10 ->  6, 7, 8, 9,10
2. 11,12,13,14,15 -> 11,12,13,14,15
3. 16,17,18,19,20 -> 16,17,18,19,20
4. 21,22,23,24,25 -> 21,22,23,24,25
5.  1, 2, 3, 4, 5 ->  1, 2, 3, 4, 5
6.  1, 6,11,16,21 ->  1, 6,11,16,21

Después de que el 6 de ordenar sólo sabemos 1 < 2 y 1 < 6, por lo tanto 2 y 6 podría ser el segundo número más pequeño.

Como hecho para estas 2 estrategias es posible (por la anterior prueba) para generar una orden de cómo los números van en un tipo tal que después de la 6 de ordenar tanto el segundo número más pequeño de la 5ª especie y el segundo número más pequeño de la 6ª tipo son candidatos para el conjunto del segundo número más pequeño.