La moneda falsa

[[Héctor Randolph]]

Se tienen 3^n monedas de oro, es decir, el número de monedas es potencia de 3, con n>=1.

Ejemplo: 3, 9, 27, 51, ...

Una de ellas es una moneda falsa, la moneda falsa pesa menos que las otras.

Para descubrir cuál de ellas es falsa, se cuenta con una balanza.

La idea es pesar las monedas en la balanza para compararlas hasta descubrir cuál de ellas pesa menos y entonces esa será la moneda falsa.

El reto consiste en diseñar un algoritmo que nos permita determinar cuál es la moneda falsa comparando pesos y que minimíze el número de veces que utilizamos la balanza.

Se puede supononer que los platos de la balanza soportan infinitas monedas, no hay límite en este sentido, la idea es utilizar lo menos posible la balanza.

En resumen:

¿Cuántas veces tendrías que utilizar la balanza en tu algoritmo para localizar la moneda falsa si el total de monedas es 3^n?

Saludos

[RbrtSmith]

Dividimos en 3 montones con el mismo nº de monedas, cogemos 2 al azar, los comparamos

Si pesan igual descartamos ambos y pasamos a aplicar el algoritmo al que no pesamos

Si uno pesa menos que otro, descartamos el que pesa más y el que quedó fuera y apligamos el algoritmo al que pesa menos.

Seguro que los hay mucho más eficientes, pero este funcionaría.

Edito para decir que tendría que usar el algoritmo n veces.

[[Héctor Randolph]]

Hola RbrtSmith!

Gracias por participar, efectivamente el algoritmo funciona y es eficiente garantizas que siempre encontrarás la moneda falsa en n pasos.

De hecho es el mismo algoritmo que ya aplicaría. ¿Habrá uno mejor?

Saludos

[marcoszorrilla]

Pues yo utilizaría el método dicotómico.
Dividir en 2, siempre, al final me quedaré con la que pesa menos.

Un Saludo.

[[Lepe]]

Si que hay un método mucho más eficiente y en un solo paso:

Tiras todas las monedas al rio, la que flote es la falsa .

PD: ...Esto se llama optimización del uso de la balanza

saludos

[mamcx]

Ya que la balanza soporta tambien N platos de pesos, se supone que se puede hacer todo el pesado en una sola tirada...

Por lo tanto, se leen los pesos en un while, guardando de entrada el primer peso y comparando con el siguiente.. no? O con un algoritmo de esos que ya sugirieron. El asunto es que de acuerdo al enunciado, simple y llanamente se usa 1 vez la balanza... o es que estoy perdido?

[roman]

Empezado por Lepe

Si que hay un método mucho más eficiente

Pues será eficiente pero ¿qué harás, una vez pasado el alborozo inicial, cuando te percates de que en el fondo- inalcanzable -del río yacen buenas piezas de oro, mientras los rayos del sol se reflejan en la falsa moneda recordándote que no todo lo que brilla es oro?

// Saludos

[[Héctor Randolph]]

Empezado por Lepe

Si que hay un método mucho más eficiente y en un solo paso:

Tiras todas las monedas al rio, la que flote es la falsa .

Bueno, me parece un poco radical pero nada te impide hacerlo.

En realidad hacen falta personas en el mundo con la capacidad de asimilar las cosas desde otro punto de vista, no lo sé, tal vez algún día nos des la sorpresa al recibir el premio Nobel.

Lo digo por la historia que transcribo a continuación. (bastante larga por cierto)

***********************************************

LA HISTORIA DEL BARÓMETRO

Sir Ernest Rutherford, presidente de la Sociedad Real Británica y Premio Nobel de Química en 1908, contaba la siguiente anécdota: Hace algún tiempo, recibí la llamada de un colega. Estaba a punto de poner un cero a un estudiante por la respuesta que había dado en un problema de física, pese a que este afirmaba con rotundidad que su respuesta era absolutamente acertada. Profesores y estudiantes acordaron pedir arbitraje de alguien imparcial y fui elegido yo. Leí la pregunta del examen y decía:

Demuestre como es posible determinar la altura de un edificio con la ayuda de un barómetro.

El estudiante había respondido:

Lleva el barómetro a la azotea del edificio y átale una cuerda muy larga. Descuélgalo hasta la base del edificio, marca y mide. La longitud de la cuerda es igual a la longitud del edificio.

Realmente, el estudiante había planteado un serio problema con la resolución del ejercicio, porque había respondido a la pregunta. Correcta y completamente. Por otro lado, si se le concedía la máxima puntuación, podría alterar el promedio de su año de estudios, obtener una nota más alta y así certificar su alto nivel en física; pero la respuesta no confirmaba que el estudiante tuviera ese nivel. Sugerí que se le diera al alumno otra oportunidad. Le concedí seis minutos para que me respondiera la misma pregunta pero esta vez con la advertencia de que en la respuesta debía demostrar sus conocimientos de física.

Habían pasado cinco minutos y el estudiante no había escrito nada. Le pregunte si deseaba marcharse, pero me contesto que tenia muchas respuestas al problema. Su dificultad era elegir la mejor de todas. Me excusé por interrumpirle y le rogué que continuara. En el minuto que le quedaba escribió la siguiente respuesta:

Tome el barómetro y láncelo al suelo desde la azotea del edificio. Calcule el tiempo de caída con un cronómetro. Después se aplica la fórmula altura = 0,5 por la constante de gravedad por T al cuadrado. Y así obtenemos la altura del edificio. En este punto le pregunte a mi colega si el estudiante se podía retirar. Le dio la nota más alta.

Tras abandonar el despacho, me reencontré con el estudiante y le pedí que me contara sus otras respuestas a la pregunta.

Bueno, respondió, hay muchas maneras, por ejemplo:

Tomas el barómetro en un día soleado y mides la altura del barómetro y la longitud de su sombra. Si medimos a continuación la longitud de la sombra del edificio y aplicamos una simple proporción, obtendremos también la altura del edificio.

Perfecto, le dije, ¿¿y de otra manera??

Sí, contestó, este es un procedimiento muy básico para medir un edificio, pero también sirve. En este método, tomas el barómetro y te sitúas en las escaleras del edificio en la planta baja. Según subes las escaleras, vas marcando la altura del barómetro y cuentas el numero de marcas hasta la azotea.
Multiplicas al final la altura del barómetro por el numero de marcas que has hecho y ya tienes la altura.

Este es un método muy directo. Por supuesto, si lo que quiere es un procedimiento mas sofisticado, puede atar el barómetro a una cuerda y moverlo como si fuera un péndulo. Si calculamos que cuando el barómetro esta a la altura de la azotea la gravedad es cero y si tenemos en cuenta la medida de la aceleración de la gravedad al descender el barómetro en trayectoria circular al pasar por la perpendicular del edificio, de la diferencia de estos valores, y aplicando una sencilla formula trigonométrica, podríamos calcular, sin duda, la altura del edificio.

En este mismo estilo de sistema, atas el barómetro a una cuerda y lo descuelgas desde la azotea a la calle. Usándolo como un péndulo puedes calcular la altura midiendo su periodo de presesión. En fin, concluyó, existen otras muchas maneras.

Probablemente, la mejor sea : Tomar el barómetro y golpear con el la puerta de la casa del conserje. Cuando abra, decirle: señor conserje, aquí tengo un bonito barómetro. Si usted me dice la altura de este edificio, se lo regalo.

En este momento de la conversación, le pregunte si no conocía la respuesta convencional al problema (la diferencia de presión marcada por un barómetro en dos lugares diferentes nos proporciona la diferencia de altura entre ambos lugares) evidentemente, dijo que la conocía, pero que durante sus estudios, sus profesores habían intentado enseñarle a pensar.

El estudiante se llamaba Niels Bohr, físico danés, premio Nobel de Física en 1922, mas conocido por ser el primero en proponer el modelo de átomo con
protones y neutrones y los electrones que lo rodeaban. Fue fundamentalmente un innovador de la teoría cuántica.

[mamcx]

No hay nada que desconcierte mas que el responder *exactamente* lo que se pregunta y no *exactamente* lo que se implica...

No podria contar la cantidad de risas que me ha provocado el responder asi... sera por nerdo o yo se que:

"Me das tu telefono?"

- No, lo necesito...

"Has visto las llaves?"

Si, las he visto...

"Me las pasas"

No... las he visto pero no se donde estan...

"Donde estas?"

Aqui!!!

"Como amanecistes?"

Dormido, y progresivamente, desperte...

"Me prestas el baño"

Si me lo devuelve, si.

"Se largo el agua!"

Que raro, porque yo siento que me moja...

"Como estas?"

De pie

"Que haces?"

Pues hablar contigo...

"Como te sientes?"

Pues con mis dedos....


e idioteces por el estilo.... Sacan de quicio a todo el mundo...