Posibles Duplicados:
Óptima algoritmo para encontrar el extraño esferasTiene 12 bolas y sabe que todos pesan lo mismo a excepción de 1 que es más pesado o más ligero que todos los demás (no sé cuál). ¿Cómo puede asegurarse de que usted sabe que la pelota es el más pesado/más ligero en solo 3 pesos?
La forma en que me acerqué fue dividir el 12 de bolas en tres grupos de 4 y pesan dos de los conjuntos. Si los conjuntos equilibrada la balanza, entonces sé que la pelota que estoy buscando debe estar en el set de 4 bolas no pesaba, otra cosa, me caso omiso de dicho conjunto y arbitrariamente elegir el más pesado de conjunto de 4 (frente a la elección de las más ligeras del conjunto). Me separé de la más pesada juego de 4 bolas en 2 y a pesar de que, etc...
Repetir este proceso hasta que todos los 3 intentos han sido "utilizados", incluso si todo lo que pasó a ser en su favor (la elección arbitraria que tiene en la elección de la más pesado o más ligero conjunto pasa a ser la opción correcta) en la final todavía puede terminar encima de tener que elegir entre 2 bolas. Un 50% de probabilidad es bueno, pero me pregunto, ¿hay una manera de asegurarse de que el 100%?
Respuestas
¿Demasiados anuncios?
Es difícil creer que este clásico del rompecabezas no está documentada ya en el MSE, pero por lo que vale, aquí está uno de los estándar de la "estática" de las soluciones. "Estática" significa que los pesajes son fijadas de antemano sabemos que la moneda (o la pelota, o lo que sea) va en cada brazo de la balanza en cada paso, independientemente de los resultados de las anteriores pesajes. Esto parece un problema más difícil de resolver, pero en realidad, esto hace que el proceso de encontrar una solución un poco más fácil que la más natural de caso-por-caso de análisis.
Crear una 3-por-12 matriz. Las filas corresponden a los pesajes, las columnas corresponden a las monedas. Cada entrada en la matriz L (la moneda va a la izquierda de la escala en este pesaje), R (la moneda va a la derecha) o o (la moneda es la izquierda en este pesaje).
Ahora bien, si una moneda es pesada, hará todos los pesajes en las que se ha L a izquierda-pesado, todas aquellas en las que se R se haga pesado, y todos aquellos en los que es O para estar en equilibrio. Para luz de la moneda es la otra manera alrededor. De manera que cada par de (una moneda, un sesgo de peso), se crea una secuencia de resultados, y usted sólo tiene que asegurarse de que todas las secuencias son diferentes para todos los (una moneda, un sesgo de combinaciones. En otras palabras, las columnas de la matriz deben ser diferentes, y por otra parte, ninguno de ellos debe ser inversos el uno del otro (ya que si la moneda x es la inversa de la moneda y, usted no puede decir una pesada moneda de x a partir de un poquito de moneda y).
He aquí un ejemplo de la solución (yo uso +, - y los espacios en blanco en lugar de R, L y S, ya que es más fácil de captar creo) que tiene un poco de estructura por lo que es fácil para verificar los requisitos.
1 2 3 4 5 6 7 8 9 A B C
+ + - + - - + -
+ + + - - - - +
+ - + + - - - +
EDIT: para explicar una vez más lo que todo esto significa, en primer pesaje que pit monedas de 1, 4, 6 y 10 en contra de las monedas de 5, 7, 9 y 12. El segundo pesaje tiene 2, 4, 5, 11 en contra 6, 7, 8, 10 y la última tiene 3, 5, 6, 12 en contra 4, 8, 9, 11. Para los pesajes son siempre 4 contra 4, y como se ha mencionado, el resultado de pesaje #1 no importa en absoluto de cómo elegimos para controlar los otros pesajes. Todo es estático.
Si la moneda de 1 es pesado, por ejemplo, vamos a llegar "a la Izquierda, equilibrada, balanceada". Ninguna otra moneda puede hacer que por ser pesado (no hay otra columna como ésta y no otra moneda puede hacer por medio de la luz (ya que no hay una columna que dice "espacios en blanco").
Aquí es la primera solución que se me ocurrió. Puede ser una alternativa más limpia para ser encontrado.
Pesan cuatro contra cuatro para empezar. Si son iguales, usted puede encontrar fácilmente la extraña bola de los cuatro restantes por que pesan en contra de dos conocidos de bolas, entonces conocida pelota.
Si las escalas son desiguales, vamos a llamar al encendedor de una escala de 1 y el más pesado de la escala 2. Mantener tres bolas en la escala de 1, entonces cambio el cuarto con una bola de escala 2. Quite el resto de las bolas de tres en la escala de 2 y reemplazarlos con los conocidos bolas.
Si las escamas ahora el balance, usted sabe que la extraña bola fue eliminado de la escala 2, y es más pesada que la de los demás. Si la escala de 1 es todavía más claro, usted sabe que el impar de bolas es uno de los tres mantienen las bolas en la escala 1, y es más claro que el resto. Si la escala 2 es más ligero, la extraña bola debe ser uno intercambiados entre las dos escalas.
En los tres casos, se puede determinar la extraña bola en uno más de pesaje.
Alon la respuesta es buena, pero me desconcertante en cuanto a por qué es que podemos lidiar con 13 bolas y no el 14. Después de todo, en tres pesajes hay 27 combinaciones posibles (la balanza puede ir de cualquier manera, o ser de nivel). La respuesta de 13 bolas, nos permite descubrir la mala de la bola (13 opciones) y de doce de estos para decir si es pesada o ligera - un total de 25 de las posibilidades - lo que ha sucedido a la que le faltan dos?
El problema es que estamos obligados a utilizar ocho bolas en cada pesaje - si podemos utilizar nueve bolas que sería capaz de utilizar todas las posibilidades. Esto se puede lograr si tenemos un extra de bola, X, que sabemos que tienen el peso correcto. Con bolas de ABCDEFGHIJKLMN y X pesan como sigue:
- ABCDX v IJKLM
- AEFIX v CDHLM
- CGIJL v FHKMX
Este esquema nos permite identificar si alguna de las bolas ABCDEFGHIJKLM es el malo, y si es así si es pesado o ligero. Si todos los pesajes salen nivel, entonces N es el malo, pero no sabemos si es pesado o ligero.
