Delantal:
Con el Divertimento de hoy volvemos otra vez al libro One hundred problems in elementary Mathematics, del matemático polaco Hugo Steinhaus (1887-1972) (uno de los libros de problemas elementales más originales de cuantos se hayan publicado, según el gran Martin Gardner). Al igual que en ocasiones anteriores, como Delantal usaremos la entrada pasada de Fondo de armario, la quinta que dedicamos a las Historias del Café Escocés. En ella narramos como las garras de la segunda guerra mundial desgarraron la Tertulia, y buena parte de sus integrantes fueron asesinados en las muchas masacres que asolaron a los polacos durante toda la contienda.
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?
Soluciones:
Envía tus soluciones, antes del domingo 30 de abril, a la dirección ‘divertimentos-blog-imus(arroba)us.es’. La solución aparecerá el miércoles 3 de mayo.
Recuerda no dejar pistas en los comentarios hasta que no se publique la solución del problema.
El problema es ordenar 5 números mediante comparación binaria. Puesto que existen 5!=120 posibles ordenaciones, y cómo las comparaciones describen un árbol binario, el número de pesadas ha de ser al menos 7: 2^6<120<2^7.
Por lo tanto el número de pesadas ha de ser mayor o igual a 7. Veamos que se puede hacer con 7.
Llamamos A,B,C,D y E a los números. En dos pesadas, comparamos A con B y C con D, supongamos A<B y C<D. comparamos A con C, si A<C, se sabe que A<C<D (llevamos 3 pesadas). Ahora con dos pesadas ponemos E en el lugar que le corresponda de {A, C, D} y con otras dos pesadas ponemos B en el lugar que le corresponda de {C,D,E}, con lo cual con 7 pesadas en total tenemos ordenados {B,C, D, E}, pero A es menor que todos ellos, por lo tanto los 5 están ordenados.