Esta respuesta no contiene la prueba de que usted pide, pero una serie de pensamientos y observaciones sobre el problema que están demasiado largo para caber en un comentario. Estoy escribiendo esto en la esperanza de que pueda ayudar a alguien a evitar bajando la incorrecta rutas que hice.
En primer lugar, aquí es un error de argumento de por qué al menos 5 es necesario. En un conjunto de 20 monedas, hay $\binom{20}{2}=20\cdot19/2=190$ pares que deben ser clasificados. En una comparación de 10 monedas, $\binom{10}{2}=10\cdot9/2=45$ pares en la clasificación. Por lo tanto, necesitamos al menos $\lceil{190/45}\rceil = 5$ pasos.
Por desgracia, este argumento es falso, ya que no todos pair debe ser comparado directamente con el fin de ser clasificado. Si $a<b$$b<c$, podemos deducir $a<c$ sin control.
Hay un segundo argumento que también es falso. Si tiene 4 elementos, y se puede comparar dos de ellos uno contra el otro, y puede cambiarlas si están en el orden equivocado, entonces el número mínimo de comparaciones por pares/swap para ordenar los 4 elementos es de 5. La forma de hacerlo es como sigue:
Poner los elementos en una fila y el nombre de las cuatro ubicaciones $A,B,C,D$.
Sort$\{A,B\}$$\{C,D\}$, por lo que tenemos $A<B$, $C<D$.
A continuación, ordenar $\{A,C\}$ también $\{B,D\}$, por lo que el$A<C$$B<D$.
Ahora tenemos $A<\{B,C\}<D$, y por último una especie de $\{B,C\}$ órdenes de ellos.
Tenga en cuenta que el dado 5 pasos de solución para 20 monedas es exactamente este procedimiento aplica a 4 series de 5 monedas. Por lo tanto, los 5 pasos que son necesarios para ordenar 4 series de 5 monedas.
Este argumento es insuficiente, porque se supone que hemos de limitarnos a conjuntos de 5 monedas que son pares comparados y clasificados. Esto no significa necesariamente que todas las demás opciones de monedas para ordenar a cada paso no podría llevar a una reducción de la solución.
Este segundo argumento que me hizo pensar que puede ser posible que por algún algoritmo que utiliza sólo cuatro de 10 monedas de comparación de medidas, un conjunto de 4 monedas se encontró que no podría haber sido ordenados porque sólo las comparaciones por pares se habían hecho en las 4 monedas y necesita al menos 5 de esos que siempre será capaz de ordenarlas. Desafortunadamente, esto hace que el mismo error que la primera falso argumento. Algunas de las comparaciones con otras monedas podría proporcionar suficiente información para ordenar el conjunto de 4 monedas con menos de 5 pares de comparaciones entre ellos.
Para obtener una mejor sensación para el problema que me escribió un programa de ordenador para la fuerza bruta algunas pequeñas variantes.
Deje $n$ el número total de monedas para ser ordenada (es decir, 20 en el problema original).
Deje $k$ el número de monedas que se comparan en cada paso (es decir, 10 en el problema original).
Deje $s$ el número de $k$-moneda comparaciones .
Aquí hay la menor de las soluciones se encuentran:
k n s Example solution
2 2 1 01
2 3 3 01 02 12
2 4 5 01 23 02 13 12
2 5 9 01 02 03 04 12 34 13 24 23
k n s
3 3 1 012
3 4 3 012 013 023
3 5 4 012 013 014 234
3 6 6 012 345 134 013 235 234
3 7 6 012 345 146 013 256 234
k n s
4 4 1 0123
4 5 3 0123 0124 0234
4 6 3 0123 0145 2345
4 7 4 0123 0456 1245 3456
4 8 5 0123 4567 0145 2367 2345
k n s
5 5 1 01234
5 6 3 01234 01235 02345
5 7 3 01234 01256 03456
5 8 4 01234 01235 01267 34567
5 9 5 01234 01235 01678 02367 45678
5 10 6? 01234 56789 23789 01256 01489 34567
5 11 6? 01234 56789 2378A 01256 0489A 34567
k n s
6 6 1 012345
6 7 3 012345 012346 012356
6 8 3 012345 012367 014567
6 9 3 012345 012678 345678
6 10 4 012345 012367 012389 456789
6 11 5? 012345 56789A 012345 123678 456789
6 12 5? 012345 6789AB 012678 3459AB 345678
Aquellos con un signo de interrogación no se han calculado a través de debido a las limitaciones de tiempo, por lo que las soluciones con el menor número de pasos puede existir.
Fue sólo cuando vi los resultados de la $n=5$ $k=2$ el caso que me di cuenta de que he hecho la suposición de que los pasos posteriores no dependen de los resultados de los pasos anteriores. Siempre es posible ordenar los 5 elementos utilizando en la mayoría de los 7 comparaciones por pares, no el 9 se muestra en la tabla.
Si usted tiene $A<B<C$ y un desconocido $D$, entonces usted puede utilizar una búsqueda binaria para encontrar el lugar adecuado para insertar $D$ en comparaciones de dos en lugar de tres. En primer lugar comparamos $D$$B$, y dependiendo del resultado de comparar con cualquiera de las $A$ o $C$. Esto permite a los 5 elementos se ordenan utilizando sólo el 7 comparaciones en lugar de 9, porque se trata de dos inserciones.
Esencialmente los resultados en la tabla de arriba son para el menor de ordenación de la red, donde las monedas en lugares fijos se comparan y ordenan. La mejor clasificación de la red para 5 elementos de hecho tiene 9 comparaciones/swaps.
No es inconcebible que un menor existe una estrategia sin esta suposición, pero que hace que sea mucho más difícil de analizar de lo que ya es.
Bien podría ser una clara prueba de que los 5 pasos es mínima, pero no he sido capaz de encontrar aún.
