Pesadas con Balanza de Dos Platillos

¿Qué es un problema de pesadas?

Los problemas de pesadas buscan identificar un objeto diferente (moneda falsa, bola más pesada, bolsa adulterada) usando la menor cantidad de pesadas en una balanza de dos platillos, que solo puede dar dos tipos de respuesta:

• Equilibrio: ambos platillos pesan igual.
• Desequilibrio: un platillo baja (más pesado) y el otro sube (más liviano).

Principio fundamental: los 3 resultados posibles

Cada pesada tiene 3 resultados posibles: $A = B$, $A > B$ o $A < B$.

$$N_{casos} \le 3^{n}$$

Con $n$ pesadas se distinguen hasta $3^{n}$ situaciones. Por eso la estrategia óptima es dividir en tres grupos lo más iguales posible.

Método general: dividir en tres

1. Divide los $N$ objetos en tres grupos $G_{1}$, $G_{2}$, $G_{3}$ (con y iguales).

Regla de oro: nunca pongas diferente cantidad de objetos en cada platillo, salvo que el problema lo indique.

Caso 1: Moneda más pesada (conocida)

Si se sabe que la falsa es más pesada:

$$N_{max} = 3^{n}$$

• $n=1$: hasta 3 monedas (1 vs 1, dejando 1 fuera).
• $n=2$: hasta 9 monedas (3 vs 3, dejando 3 fuera).
• $n=3$: hasta 27 monedas (9 vs 9, dejando 9 fuera).

Caso 2: Moneda diferente (peso desconocido)

Si no se sabe si es más pesada o liviana, cada moneda aporta 2 casos ($pesada$ o $liviana$):

$$2 \cdot m \le 3^{n} - 3 \quad \Rightarrow \quad m_{max} = \frac{3^{n} - 3}{2}$$

• $n=2$: hasta 3 monedas.
• $n=3$: hasta 12 monedas (famoso problema de las 12 monedas).

Es clave usar el sentido del desequilibrio de la primera pesada para saber en la segunda si se busca lo pesado o lo liviano.

Caso con pesas calibradas

Para formar un peso exacto $P$ con el menor número de pesas:

• Pesas en un solo platillo: sistema binario $1, 2, 4, 8, \dots, 2^{k}$; cubre hasta $2^{k+1}-1$.

$$P = a_{0} \cdot 1 + a_{1} \cdot 2 + a_{2} \cdot 4 + \cdots + a_{k} \cdot 2^{k}, \quad a_{i} \in \{0,1\}$$

• Pesas en ambos platillos: sistema ternario $1, 3, 9, 27, \dots, 3^{k}$ (más potente).

Errores frecuentes

• Dividir en dos en lugar de tres: se desperdicia el caso $G_{1} = G_{2}$.
• Olvidar el grupo fuera de la balanza: el equilibrio también es información.
• Pesar de uno en uno: siempre se pesa por grupos.
• Asumir que es más pesada cuando el problema no lo especifica: considerar ambos casos (pesado y liviano).

Ideas clave para el examen

• Cada pesada = 3 resultados ⇒ máxima información dividiendo en tres.
• $N_{max} = 3^{n}$ si se sabe que el objeto es más pesado.
• $m_{max} = \frac{3^{n}-3}{2}$ si no se sabe si pesa más o menos.