Encuentra la bola extraña de $18$ bolas, donde $17$ pesan lo mismo.
Hay muchas variantes de este problema. Con quien estoy trabajando es
Existen $17$ bolas que pesan lo mismo, y $1$pelota que podría ser un lastre , ya sea pesado o más ligero que el otro$17$. ¿Cuántos pesa en una balanza necesita para determinar cuál es el impar y si es más pesado o más ligero?
El caso más simple en el que sabe si la bola extraña es más pesada o más ligera se puede encontrar en $3$pesa. La idea es dividir el$18$ bolas en grupos de $6$, decir, $6A$, $6B$, $6C$. Pesar$6A$ y $6B$en escala. Si se equilibran entre sí, entonces$6C$tiene el extraño. Si no se equilibran entre sí, y$6A$ es más bajo en la escala, entonces $6A$ tiene la bola más pesada, y análogamente para $6B$. Entonces se necesita un máximo de$1$ pesar para determinar el grupo de $6$con la bola más pesada. Entonces puedes dividir este grupo de$6$ dentro $3$ grupos de $2$, y usando la misma idea, puede encontrar el grupo impar de $2$ con un máximo de $1$pesar. Entonces te quedas con un grupo de$2$ y se necesita $1$pesar para determinar la bola más pesada. Entonces, en total, necesitas$3$ pesa para este caso.
Pero la variante más difícil de este problema es donde no se sabe si la bola extraña es más pesada o más ligera. En este caso, descubrí que necesita un máximo de$5$ trata de encontrar el impar y de determinar si es más pesado o más liviano, pero no tengo idea de si esto es correcto, o cómo justificar que este es el número mínimo de intentos máximos.
La idea es similar al problema anterior. Dividir$18$ bolas en $6A$, $6B$, $6C$. Esta vez, se necesita un máximo de$2$ intenta encontrar el grupo de $6$. es decir, pesar$6A$ y $6B$ en una escala, si coinciden, entonces $6C$es el grupo extraño. Si$6A$ y $6B$no coincide, entonces necesitamos un peso adicional para determinar el impar. Por lo tanto,$2$ intentos.
Ahora, una vez que encontramos el extraño grupo de $6$, aplicamos la misma idea, que toma otra $2$intentos (máximo). Entonces nos quedamos con un grupo de$2$. Se necesita exactamente$1$ pesar porque puedes tomar $1$ pelota del grupo de $2$ y pesarlo con uno de los otros $16$bolas que sabemos que son las. Si esta bola es la misma, entonces la bola restante es la que sale impar. Entonces se necesita un máximo de$2+2+1 = 5$trata de encontrar esta bola extraña. No necesitamos un peso adicional para determinar si esta bola restante es más pesada o más ligera.
Esto se debe a que cuando encontramos el grupo de $6$, y el grupo subsiguiente de $2$, tomamos el máximo de $2$intentos. Si toma$2$ intenta encontrar el extraño grupo de $6$ , entonces eso significa el segundo peso del $2$ Los intentos nos permiten determinar si esta bola extraña es más pesada o más ligera.
Por ejemplo, considere $6A$, $6B$, $6C$de nuevo. Digamos que primero pesamos$6A$ y $6B$y descubre que no pesan lo mismo. Entonces pesamos$6C$ con cualquiera $6A$ o $6B$. Si pesamos$6A$ con $6C$ y encontrar eso $6A$ no coincide $6C$, entonces $6A$ es el extraño, pero también si $6A < 6C (6A > 6C)$, entonces sabemos $6A$ tiene una pelota que pesa menos (más).
¿Es este el enfoque más óptimo o hay un método que solo toma $4$pesa? Mi instinto me dice que debería haber un$4$ enfoque de pesaje.
los $12$-Bola variante del problema y su solución se publica en http://www.mytechinterviews.com/12-identical-balls-problem. Puede ver que aplican un enfoque análogo rompiendo el$12$ bolas en $3$ grupos de $4$, pero aplican una combinación y combinación interesantes para encontrar el extraño en solo $3$ se mueve.
Respuestas
No revisé la solución para el clásico. $12$ versión de bolas http://www.mytechinterviews.com/12-identical-balls-problem. Pero si funciona, trivialmente conduce a una$4$ solución de pesaje para $18$ estuche de bolas.
Realmente, dado el clásico, ¡hay muy poco trabajo adicional por hacer!
Primero pesas $3A$ vs $3B$. Si están desequilibrados, diga$3A > 3B$, puedes averiguarlo con $3A$ vs $3C$ (todas $3C$son buenos) si la pelota mala es más pesada o más ligera. Entonces seguramente podrás encontrar al culpable entre un grupo de$3$con solo un pesaje más. Total$3$ pesajes.
Y si $3A = 3B$, entonces estás reducido al clásico $12$-problema de bola que se puede resolver con $3$ pesajes adicionales, para un total de $4$.
Pensamientos adicionales: de hecho, $4$ los pesajes pueden resolver $30$ bolas, no solo $18$.
En lo anterior, el $3A \neq 3B$ rama siempre conduce a $3$pesajes totales, lo cual es un desperdicio. Imagina que tienes$9+9+12 = 30$pelotas. El primer pesaje puede ser$9A$ vs $9B$. Si están desequilibrados, de nuevo un segundo$9A$ vs $9C$ (todo bien) te dirá si el malo es pesado o liviano, y luego puedes usar $2$ más pesajes para encontrar al culpable entre $9$ (búsqueda trina), para un total de $4$ pesajes.
Aún más, hace años resolví un caso (una extensión del clásico) donde $13$ bolas (pesadas / ligeras desconocidas) se pueden resolver con $3$ pesajes, siempre que tenga acceso a bolas adicionales conocidas por ser buenas - IIRC que necesita $2$tan buenos extras. Esto significa$9+9+13 = 31$ se puede resolver con $4$ pesajes, porque en el $9A=9B$ caso de que te quedes con $13$ sospechosos, pero muchas bolas extra que se sabe que son buenas.
Sospecho incluso $31$ no es el límite (por $4$pesajes). Cuando pesas$9A$ vs $9C$, solo pueden ocurrir dos resultados (ya que $9A > 9B$). Esto es muy ineficiente y podría ser posible una mayor explotación ...
Probablemente conozcas el clásico límite que con $n$ pesajes solo hay $3^n$ posibles resultados, entonces con $n=4, 3^n = 81$, no puedes resolver $\ge 41$ pelotas ($\ge 82$resultados). no estoy diciendo$40$ es alcanzable, pero hay una gran brecha entre $31$ y $40$...
Pesaje 1 : Pesar$1$-$6$ versus $7$-$12$. Si el resultado es equilibrado , sabemos que la bola impar está en el set.$13$-$18$, que (de hecho) toma $3$más medidas para un total de 4 pesajes.
Si el primer pesaje está desequilibrado , suponga sin falta de generalidad que$1$-$6$ es más pesado que $7$-$12$. Entonces realiza ...
Pesaje 2 : Pesar$1$-$3$ versus $7$-$9$. Si el resultado es equilibrado , la bola impar está en$\{ 4, 5, 6, 10, 11, 12 \}$, que de hecho toma $3$más pesajes, para un total de 5 pesajes.
Si, en cambio, el resultado es desequilibrado , supongamos sin pérdida de generalidad que$1$-$3$ es más pesado que $7$-$9$. Entonces sabemos que la bola extraña está en ese conjunto de seis, lo que de hecho requiere dos pesajes más para un total de 5 pesajes.