Hola
Por ejemplo según tu fórmula para \( 12 \) monedas dices que el número óptimo de pesadas es \( 4 \), pero en realidad lo puedes hacer en \( 3 \).
1) Divide en tres grupos de \( 4 \) la monedas.
2) PESADA UNO. Pesa dos de ellos.
2.1) Si pesan lo mismo, de las \( 4 \) monedas restantes (el tercer grupo) compramos dos de ellas en una
plato de la balanza frente a otra y una de las ocho iniciales (que sabemos normales) en el segundo plato, dejando
una cuarta moneda separada. PESADA DOS.
2.1.1) Si pesan lo mismo, la moneda falsa es la que dejamos al margen y la comparamos con una normal para
ver si es más o menos pesada. PESADA TRES. FIN.
2.1.2) Si pesa más (respectivamente menos) el plato donde están las dos monedas del tercer grupo de cuatro,
comparamos una con la otra (PESADA TRES):
2.1.2.1) Si pesan igual, la falsa era la moneda que habíamos puesto en el paso 2.1 en el otro plato con la
moneda normal y además es menos (respectivamente más) pesada que las normales. FIN.
2.1.2.2) Si pesan más (respectivamente menos) una que otra la falsa es la que pesa más (respectivamente
menos) FIN.
2.2) Si pesan distinto, tenemos un grupo de cuatro que pesó más y otras cuatro que pesaron menos. Hacemos una PESADA DOS, poniendo en cada plato de la balanza dos monedas del grupo ligero y una del pesado; dejando fuera dos del pesado.
2.2.1) Si pesan lo mismo, la moneda falsa es la una de las dos que dejamos al margen; dado que dejamos las más pesadas. Es la que más pesa de ambas y eso se comprueba en una PESADA TRES. FIN.
2.2.2) Si pesan distinto, la moneda falsa es o bien una de las monedas ligeras del plato que pesó menos o bien la pesada del plato que pesó más. Tomamos la dos ligeras y las comparamos. PESADA TRES:
2.2.2.1) Si pesan igual, la falsa era la moneda pesada del plato que pesó más. FIN.
2.2.2.2) Si pesan distinto, la falsa es la que menos pesa de las dos. FIN.
En general se puede demostrar que:
- Si sólo queremos encontrar la moneda falsa pero sin saber si es más o menos pesada, el número necesario de pesadas para \( n \) monedas es \( \lceil log_3(2n+1)\rceil \).
- Si queremos encontrar la moneda falsa pero además saber si es más o menos pesada, el número necesario de pesadas para \( n \) monedas es \( \lceil log_3(2n+3) \rceil \).
Por ejemplo, para \( 13 \) monedas se puede en tres pesadas encontrar la falsa (prácticamente como hicimos antes dejando una moneda al margen; si el método que usamos no encuentra la falsa es que era la dejada al margen); pero no se puede saber si la falsa es más o menos pesada que las normales.
Saludos.
P.D. Puedes leer aquí sobre esto:
https://aprende.olimpiada-informatica.org/algoritmia-introduccion-1-eficiencia