Solución: El menor número de comparaciones

Publicamos la solución al divertimento El menor número de comparaciones. En esta ocasión, Rafael Jiménez Llamas, Francisco García Cortés, Abraham del Valle Rodríguez (alumnos de la Facultad de Matemáticas) y Alberto M. P. han propuesto soluciones correctas.

Divertimento:

Disponemos de una balanza primitiva, con la cual podemos comparar el peso de dos objetos.

Tenemos cinco objetos con pesos distintos. ¿Cuál es el menor número de comparaciones necesarias para ordenarlos por su peso?

Solución:

Comparamos dos parejas por separado, y después comparamos los objetos más pesados en cada pareja. Con tres comparaciones, obtenemos una configuración como esta:
\begin{array}{ccccc}
A & < & B & < & C \\
& & & & ∨ \\
& & & & D
\end{array}
El quinto objeto lo colocamos entre A, B y C comparándolo con B en primer lugar; si es más pesado que B lo comparamos con C, y en caso contrario con C. En cinco comparaciones llegamos a una de las siguientes configuraciones:

Caso 1.
\begin{array}{ccccccc}
A & < & B & < & C & < & E \\
& & & &∨ \\
& & & & D
\end{array}
Comparamos D con A. Si D<A, hemos terminado en 6 comparaciones, y si A<D comparamos D con B, y acabamos en 7 comparaciones.

Caso 2.
\begin{array}{ccccccc}
A & < & B & < & E & < & C \\
& & & & & &∨ \\
& & & & & & D
\end{array}
En este caso ubicamos D entre A, B y E en dos comparaciones, y son un total de 7 comparaciones.

Caso 3.
\begin{array}{ccccccc}
E & < & A & < & B & < & C \\
& & & & & &∨ \\
& & & & & & D
\end{array}
Es análogo al caso 2.

Caso 4.
\begin{array}{ccccccc}
A & < & E & < & B & < & C \\
& & & & & &∨ \\
& & & & & & D
\end{array}
Es análogo al caso 2.

En cualquier caso, siete comparaciones son suficientes.

Además, como hay 5!=120 formas de ordenar los objetos, y el número de comparaciones \(n\) debe cumplir \(2^n \geq 120\), se tiene que \(n \geq 7\), es decir, son necesarias 7 comparaciones.