Un problema de pesas "original" (correción)
Antonio Torrecillas
Me permito poneros un problema de balanzas y pesadas que en su momento
me pareció bastante original.
Tenemos 5 bolas de diferentes pesos y una balanza. Con 6 pesadas hay que
saber cual es la "mediana", es decir la tercera por orden de peso. No es
fácil!
Espero que paséis un buen rato con él y aprovecho para desearos Felices
Fiestas
Antonio T.
Sergio Cinos Rubio
Ahora que hago memoria... Para ordenar n objetos con una balanza no se
necesitaban como máximo 2x-3 pesadas? Según esto necesitaríamos 7 pesadas...
"Antonio Torrecillas" <ator...@pie.xtec.es> escribió en el mensaje
news:3A40140D...@pie.xtec.es...
Antonio González
>
> Me permito poneros un problema de balanzas y pesadas que en su momento
> me pareció bastante original.
>
> Tenemos 5 bolas de diferentes pesos y una balanza. Con 6 pesadas hay que
> saber cual es la "mediana", es decir la tercera por orden de peso. No es
> fácil!
Me salen un mínimo de 5 y un máximo de 7 y no veo cómo
reducirlo a 6.
Steinhaus, en sus Instantáneas Matemáticas, dice que para
ordenar 5 objetos hacen falta 8 pesadas. Cómo aquí no
necesitamos ordenar todos, podemos eliminar una, pero no
veo cómo eliminar otra.
Antonio
Antonio Torrecillas
Como hay 5*4*3*2*1=120 ordenaciones posibles y cada pesada discrimina 2 casos,
... para ordenar 5 pesas son necesarias (quien sabe si tambien suficientes) 7
pesadas pues 2^7=128.
Pero si te fijas, en el enunciado sólo se pide decir cual es la mediana, (la
tercera, la intermedia, ...) y no se pide ordenar las 5 pesas. Esto es posible
con 6 pesadas (y no creo que con menos se pueda hacer)
Un saludo y anímate a pensar el problema!
Antonio T.
Ps: Este problema está sacado de un curso de doctorado en software de hace 11
años, pero no necesita ningún conocimiento especial.
Ps: Sergio, ¿estás seguro de ese 2x-3 como cota superior para ordenar x
elementos? Explícamelo si eres tan amable.
En/Na Sergio Cinos Rubio ha escrit:
Antonio Torrecillas
Hace poco te he dicho que me expliques eso del 2x-3, pero lo he pensado un poco
y no me salen las cuentas. Quise responder rápido a tu comentario y la rapidez
está reñida con la correción. Ahora completo el mensaje anterior.
He calculado un poco y me sale que eso de "2x-3" pesadas es falso.
Por ejemplo: para ordenar 6 elementos:
- Por una lado hay 6*5*4*3*2*1=720 casos diferentes
- Si haces 2*6-3 = 9 pesadas sólo tienes 2^9 = 512 casos
Evidentemente no puedes hacer un proceso que tiene 512 casos para distinguir un
caso de 720 posibles.
Un saludo.
Ps: Yo pensaba que para hacer una ordenación hacen falta "del orden de" x·ln(x)
comparaciones (pesadas). Una manera fácil de ver esto es ordenar (x-1) números y
luego el siguiente lo comparo con el "medio", con el "medio de la mitad
correcta", ... y así sucesivamente (y pensaba que no había proceso que mejore
este resultado).
En/Na Sergio Cinos Rubio ha escrit:
> Salu2 again
Maese Samsagaz
> "Antonio Torrecillas" <ator...@pie.xtec.es> escribió en el mensaje
> news:3A40140D...@pie.xtec.es...
> > Hola,
> >
> > Me permito poneros un problema de balanzas y pesadas que en su momento
> > me pareció bastante original.
> >
> > Tenemos 5 bolas de diferentes pesos y una balanza. Con 6 pesadas hay que
> > saber cual es la "mediana", es decir la tercera por orden de peso. No es
> > fácil!
>
> Me salen un mínimo de 5 y un máximo de 7 y no veo cómo
> reducirlo a 6.
No es una ordenación, sólo hay que encontrar la central y con una leve
modificación del método de la burbuja sale fácil. Mira mi respuesta en otro
hilo a ver si te parece que está bien.
Antonio Torrecillas
Ante todo te agradezco que te hayas puesto a pensar en el problema, pues
cuando uno pone algo en esta lista lo hace bien con la esperanza de que se lo
resuelvan (en el caso de no saber cómo hacerlo), bien con la esperanza de ver
diferentes formas de enfocar el problema (en el caso de conocer una solución).
Pues bien, yo conozco una solución del problema que obtuve hace más de 10
años. Recuerdo que una persona encontró otra solución mucho más elegente en
aquellos tiempos y hoy "repensando" el problema se me ha ocurrido una solución
increiblemente simple.
Como creo que lo mejor de los problemas es resolverlos y no os quiero
"estropear" este bonito problema, esperaré unos días antes de dar alguna
solución.
Me dices que te sobra una pesada: como idea te recordaré que no hace falta
saber el orden ente las dos primeras ni tampoco el orden entre las dos
últimas. Estas dos podrían se las pesadas que puedes "eliminar". O tambien
puede ser que debas rehacer el proceso.
Un saludo
Antonio T.
Ps: Acabo de escribir un razonamiento que muestra que para ordenar 5 pesas son
necesarias 7 pesadas y me preguntaba si también son suficientes (es decir,
decía que hacen falta un mínimo de 7 pesadas, pero no sabía si con 7 se puede
hacer). Por lo que tú dices son 8 las pesadas que te permiten ordenar esos 5
elementos.
Ps: No entiendo eso del mínimo de 5 pues es evidente que puedes tener la
suerte de saber la mediana en sólo 4 pesadas. Seguramente te refieres a otra
cosa. (¿puede ser a el "mínimo" según el proceso que propones y que, como es
natural, yo desconozco?)
En/Na "Antonio González" ha escrit:
Antonio González
> Hola Sergio,
>
> Como hay 5*4*3*2*1=120 ordenaciones posibles y cada pesada discrimina 2
casos,
> ... para ordenar 5 pesas son necesarias (quien sabe si tambien
suficientes) 7
> pesadas pues 2^7=128.
>
Para 5 son suficientes 8 pesadas (y necesarias 4). Es una cuestión de
bisección.
El mínimo número de pesadas es n-1, porque ocurre cuando se dan
todos los casos favorables.
-Se pesan A y B, supongamos que A pesa más, esto da la ordenación
A>B
-Se pesa C con A. Si C pesa más ya tenemos
C>A>B
-Se pesa D con C. Si D pesa más
D>C>A>B
-Se pesa E con D. Si E pesa más
E>D>C>A>B
Por supuesto esta estrategia no es óptima. Si no se dan todos
los casos favorables, el número de pesadas es mayor que en
la estrategia óptima (que garantiza un mínimo de 5 y un máximo
de 8 pesadas).
El número máximo de pesadas para n objetos es
N=1+kn-2^k, con k=1+[log_2 n]
Antonio
Antonio
Sergio Cinos Rubio
> Hola de nuevo Sergio,
>
> Hace poco te he dicho que me expliques eso del 2x-3, pero lo he pensado un
poco
> y no me salen las cuentas. Quise responder rápido a tu comentario y la
rapidez
> está reñida con la correción. Ahora completo el mensaje anterior.
>
> He calculado un poco y me sale que eso de "2x-3" pesadas es falso.
> Por ejemplo: para ordenar 6 elementos:
> - Por una lado hay 6*5*4*3*2*1=720 casos diferentes
> - Si haces 2*6-3 = 9 pesadas sólo tienes 2^9 = 512 casos
Porqué 2^9?
> Evidentemente no puedes hacer un proceso que tiene 512 casos para
distinguir un
> caso de 720 posibles.
>
> Un saludo.
>
> Ps: Yo pensaba que para hacer una ordenación hacen falta "del orden de"
x·ln(x)
> comparaciones (pesadas). Una manera fácil de ver esto es ordenar (x-1)
números y
> luego el siguiente lo comparo con el "medio", con el "medio de la mitad
> correcta", ... y así sucesivamente (y pensaba que no había proceso que
mejore
> este resultado).
Te estas equivocando de algoritmo.
Por programación se que hay varios algoritmos para ordenar, y uno en
concreto da x·ln(x). (no recuerdo su nombre, puede ser Heapshot?).
Más tarde descubrí que el algoritmo que yo he utilizado es el "Quicksort",
que se basa en colocar en su lugar el objeto inicial del vector de objetos,
y luego pasar a izquierda todos los mayores y a derecha todos los menores.
Con cada sub-vector se sigue un proceso similar.
No obstante, me consta que este no es mi fuerte, seguiré dandole vueltas :)
PD: Ya recuerdo el 2x-3. Para ordenar 2 elementos, se necesita una pesada
(funciona). Para ordenar 3, 3 pesadas (funciona). Pero para 4, acabo de
descubrir un caso en el que necesitaría 6 pesadas. Y si no me equivoco, para
5 deberían ser 10 pesadas (porque en el peor de los casos, gastas 4 pesadas
para dejar 4 bolas sin ordenar)
Antonio Torrecillas
te respondo entre líneas:
En/Na Sergio Cinos Rubio ha escrit:
> "Antonio Torrecillas" <ator...@pie.xtec.es> escribió en el mensaje
> > Hola de nuevo Sergio,
> > He calculado un poco y me sale que eso de "2x-3" pesadas es falso.
> > Por ejemplo: para ordenar 6 elementos:
> > - Por una lado hay 6*5*4*3*2*1=720 casos diferentes
> > - Si haces 2*6-3 = 9 pesadas sólo tienes 2^9 = 512 casos
>
> Porqué 2^9?
En 9 pesadas con dos posibilidades (A pesa más que B o al revés) en cada una hay
2*2*2*2*2*2*2*2*2 posibilidades
> > Ps: Yo pensaba que para hacer una ordenación hacen falta "del orden de"
> > x·ln(x) comparaciones (pesadas). Una manera fácil de ver esto es ordenar
> > (x-1)números y luego el siguiente lo comparo con el "medio", con el "medio
> > correcta", ... y así sucesivamente (y pensaba que no había proceso que
> > de la mitad mejore este resultado).
>
> Te estas equivocando de algoritmo.
> Por programación se que hay varios algoritmos para ordenar, y uno en
> concreto da x·ln(x). (no recuerdo su nombre, puede ser Heapshot?).
>
> Más tarde descubrí que el algoritmo que yo he utilizado es el "Quicksort",
> que se basa en colocar en su lugar el objeto inicial del vector de objetos,
> y luego pasar a izquierda todos los mayores y a derecha todos los menores.
> Con cada sub-vector se sigue un proceso similar.
>
> No obstante, me consta que este no es mi fuerte, seguiré dandole vueltas :)
No, no es tu fuerte (te lo digo con todo mi respeto), hay cientos de algoritmos
con complejidad del orden de x·lnx y el Quicksort es uno de ellos.
> PD: Ya recuerdo el 2x-3. Para ordenar 2 elementos, se necesita una pesada
> (funciona). Para ordenar 3, 3 pesadas (funciona). Pero para 4, acabo de
> descubrir un caso en el que necesitaría 6 pesadas. Y si no me equivoco, para
> 5 deberían ser 10 pesadas (porque en el peor de los casos, gastas 4 pesadas
> para dejar 4 bolas sin ordenar)
Para 5 según un "post" anterior son 8. Con el razonamiento que te he explicado
se puede demostrar que debe ser mayor que 7. Para ver que es 8 debes dar el
algoritmo. Cuando dices que "deberian se 10" me imagino que dices que hay un
proceso que lo hace en 10, pero ya sabes que puede haber (y hay en este caso)
algo mejor.
Un saludo
Antonio T.