Hay $6561$ bolas de las que $1$ es pesado. Encuentra el número mínimo de veces que hay que pesar las bolas para averiguar la bola pesada.
¿Cómo puedo resolver esto paso a paso?
Respuestas
¿Demasiados anuncios?
tom
Puntos
1397
Bueno, aquí hay un método.
Si tienes 3 bolas, entonces pesa dos de ellas. Si una de ellas es más pesada que la otra, entonces has encontrado la más pesada. Si son iguales, entonces la restante debe ser la pesada.
Esto requiere 1 pesaje.
Ahora considere $3\times 3 = 9$ bolas.
Pesa 3 de ellos contra otros 3, dejando 3 a un lado. Si un grupo de 3 es más pesado que el otro grupo, entonces la bola pesada debe ser una de esas 3, y el problema vuelve a ser el anterior. Si los dos grupos pesan lo mismo, entonces la bola pesada debe ser una de las 3 que no pesaste, y de nuevo sabes que la bola pesada es 1 entre 3, y lo resuelves como arriba, con una pesada más.
En cualquier caso, se necesitan dos pesajes.
Ahora considere $3\times 3\times 3 = 27$ pesos. Divídelas en 3 grupos de nueve, e identifica el grupo de nueve bolas que contiene la pesada. Esto se reduce al problema anterior.
Esto requiere 3 pesajes.
Y podemos seguir así para siempre.
Si tiene $3^n$ bolas entonces tomará $n$ pesajes para encontrar la bola correcta.
Y $3^8 = 6561$ . Así que la respuesta es C.
Lo único es que ¿cómo sabemos que no hay un método aún más eficaz? No veo ninguna prueba de que esto sea lo mejor que podemos hacer. Tal vez alguien más pueda completar ese detalle...
Bernhard
Puntos
638
La optimización de este método se desprende, entre otras cosas, de la teoría de la información: Hay 6.561 posiciones posibles para la bola pesada, y cada pesada da exactamente tres posibles informativo resultados: el lado izquierdo es más pesado, el derecho es más pesado, ambos lados tienen el mismo peso. Si escribimos esto en términos de entropía, obtenemos
$$ H(1\ weighing) = \log(3). $$
Ya que las pesadas son independientes, $n$ las ponderaciones tienen entropía
$$ H(n\ weighings) = n\cdot H(1\ weighing) = n\log(3) = \log(3^n).$$
Hay 6561 posiciones posibles para la pelota, así que
$$ H(position) = \log (6561).$$
La posición de la bola determina completamente todas las pesadas, por lo que $H(n\ weighings|position)=0$ . Lo que necesitamos es que las n pesadas también nos permitan determinar la posición de la bola, es decir, queremos que $H(position|n\ weighings)=0$ . Pero
$$ H(position|n\ weighings) = H(position,n\ weighings) - H(n\ weighings)$$
y
$$ H(position,n\ weighings) = H(n\ weighings|position) + H(position) = H(position). $$
Por lo tanto,
$$ H(position|8\ weighings) = H(position) - H(8\ weighings) = \log (6561)-H(n\ weighings)$$
Esto es exactamente cero si $n\ge8$ y mayor que cero si $n<8$ . De ello se desprende que ocho ponderaciones son óptimas.
(Quedan algunas preguntas interesantes sobre lo que ocurre con esta explicación teórica de la información si no sabemos si la bola impar es más pesada o más ligera. He enlazado algunas entradas de blog interesantes en mi entrada de blog (que es no una buena entrada sobre este tema).
