Falsificación de moneda problema variante - dos billetes falsos

Question

Así que hay una falsificación de moneda variante que me encontré y no estoy seguro exactamente de cómo resolverlo.

Se va como sigue:

Tiene ocho monedas, dos de los cuales son falsos. Uno de los dos es un poco más pesado de lo normal, el otro es un poco más ligero. Los dos falsificación de monedas tienen el mismo peso combinado como dos normales monedas.

Usted tiene un saldo pendiente. Cuántos pesajes son necesarios para identificar tanto los más pesados y ligeros de la moneda?

Que puedo hacer en cinco, pero tengo la fuerte sospecha de que puede hacer en menos.

EDIT: Solución para cinco pesajes:

Etiqueta tus monedas de la 1 a la 8. Pesa 1 contra 2, 3 contra 4, 5 contra 6, 7 en contra 8. Si tenemos tres equilibrada escalas y un desequilibrio en la escala, sabemos que dos monedas falsificados. Si tenemos dos equilibrada escalas y dos desequilibrio de las balanzas, suponer sin pérdida de generalidad que el 1 era más pesado que el 2 y 3 es más pesado que el 4. De esto podemos deducir que, o bien 1 es la pesada de la falsificación y la 4 es la luz de la falsificación, o 2 es la luz de la falsificación y la 3 es la pesada de la falsificación. Por lo tanto, nos pesa 1 contra 4. Si ellos están en equilibrio, entonces 2 es la luz de la falsificación y la 3 es la pesada de la falsificación. De lo contrario, 1 es pesado y 4 es la luz.

EDIT: Como se ha mencionado por Mees de Vries, a continuación, 3 pesos con 3 posibles resultados de cada uno sólo puede distinguir entre el 27 de escenarios posibles. Tenemos 56 el total de configuraciones posibles, y por lo tanto 4 pesajes debe ser óptima, si es posible.

Answer 1

Sí, 4 ponderaciones es posible. Aún más, esto sigue siendo cierto incluso si no se sabe si el peso combinado de los 2 falsificaciones es más pesado, más ligero, o mismo que el de 2 normal monedas

---

La notación

En primer lugar, vamos a introducir una notación.

Las monedas están etiquetados 1 través 8. H, Ly n denota la pesada de la falsificación, la luz de la falsificación, y una moneda normal, respectivamente.

Las ponderaciones se denota, por ejemplo, 12-34 de ponderación de las monedas 1 y 2 contra 3 y 4. El resultado es denotado 12>34, 12=34o 12<34 si 12 es más pesado, el peso es el mismo, y más ligero que el 34, respectivamente.

1234:H medio H está entre las monedas 1, 2, 3y 4. Del mismo modo, 1234:L medio L está entre las monedas 1, 2, 3y 4.

Debido a la muy simétrica de la naturaleza del problema. Un montón de sin-pérdida de la generalidad de supuestos. Como tal, no van a ser llamados.

---

Algoritmo

Comience 12-34 y 56-78.

---

Caso 1: Doble desequilibrado (12>34, 56>78)

En este caso, sabemos que o 12:H, 78:L o 56:H, 34:L. Hacer 13-57 el próximo.

Si 13>57 , luego 1:H, 7:L o 1:H, 8:L o 2:H, 7:L. Estos pueden ser distinguidos por 28-nn.

Si 13=57, entonces con un simple 2-8 a distinguir 2:H, 8:L y 6:H, 4:L

---

Caso 2: Balanced-unbalanced (12>34, 56=78)

En este caso, sabemos que 12:H y/o 34:L. Hacer 1-2 el próximo.

Si 1>2, a continuación, 1:H, 234:L. Una simple 2-3 resuelve.

Si 1=2, luego 3:H, 4:L o 4:H, 3;L. Por lo 3-4.

---

Caso 3: Doble equilibrado (12=34, 56=78)

Esto significa que tanto H y L está dentro de la misma pareja. Hacer 135-246.

Si 135>246, luego 1:H, 2:L, 3:H, 4:Lo 5:H, 6:L. Hacer 1-3 a distinguir.

Si 135=246, luego 7:H, 8:L o 8:H, 7:L. Hacer 7-8 a distinguir.

Answer 2

Si usted tiene seis monedas, creo que se necesitan al menos cuatro de los pesajes. (Lo que implica que se necesitará más pesajes si usted tiene 8 monedas.)

Pesan tres contra tres. Si equilibrada, tanto de las falsificaciones están en un lado. Pesan dos de un lado. Si equilibrada, esas son las buenas monedas; de lo contrario, uno o ambos de la moneda es una falsificación. A partir de aquí, se toma en la mayoría de los dos más pesajes para determinar qué moneda es que.

Pesaje de dos contra dos en el inicio es subóptima. Si desequilibrada, se dice que al menos uno de los cuatro es una falsificación, puede ser tanto de las falsificaciones están en lados opuestos. El pesaje de los otros dos le dice que si el primer pesaje había una o dos de las falsificaciones. Si sólo uno era una falsificación, y luego pasar a otro de pesaje averiguar de qué lado tenía la falsificación, entonces se necesitan dos más que el humo fuera de la falsificación de monedas.

Por último, si usted pesa más de un par en el arranque, si desequilibrada, entonces usted tiene una o dos de las falsificaciones allí. Pesan otro par. Si equilibrada, a continuación, aquellos que son conocidos buenas monedas, pero entonces usted puede ir a través de más de tres pesajes para el humo fuera de la falsificación de monedas, porque usted tiene que probar ambas monedas en la primera que pesan en contra de una moneda. Si sólo uno es falso, entonces usted no sabe que en el unweighed par es la otra falsificación.