División real monedas en mitad

Question

Hay $n$ monedas, algunos son reales y otros falsos. Real de las monedas de todos los tienen iguales positivo de peso, y monedas falsas tienen cero peso. El número de monedas es $2k$ algunos $k\geq 1$, pero no sabe $k$. Su tarea es la de dividir las monedas en dos mitades, de manera que cada mitad contiene $k$ real de las monedas.

Se le da una escala que, entre dos conjuntos de monedas, le dice a usted que en conjunto es más pesado (o si son iguales). ¿Cuál es el número óptimo de pesajes, en términos de $n$, después de lo cual usted puede hacer la tarea?

Tenga en cuenta que tenemos en la mayoría de las $n$ pesajes: podemos empezar con un vacío de escala y agregar una moneda en un tiempo de al lado que es más ligero (si los dos lados son iguales, entonces no importa.)

Si $k=1$, entonces solo tenemos $\Theta(\log n)$ pesajes. Podemos dividir las monedas en la mitad y sopesar las dos mitades. Si las dos mitades son iguales, hemos terminado. Otra cosa, por lo recurse en el más pesado de la mitad, el cual debe contener real de las monedas. Pero en la pregunta que no sabe $k$.

Answer 1

Usted puede hacerlo en $\Theta(\log n)$ pesajes. Colocar la mitad de las monedas de la izquierda, la mitad de la derecha, y peso. Si ambos lados son iguales, hemos terminado.

De lo contrario, vamos a dividir ambos lados hasta en dos mitades, de intercambio de sus mitades izquierda, y pesar de nuevo:

aaaabbbb     ccccdddd

ccccbbbb     aaaadddd

Si la escala de saldos, hemos terminado. Si la escala invierte los lados nos recurse a la izquierda mitades, y dejar las mitades derecha en la escala para el resto del proceso. Si el equilibrio no se modifica, se recurse en las mitades derecha y dejar el resto en la escala para el resto del proceso.

La razón por la que esto funciona es si se intercambian dos porciones de igual tamaño en la escala puede cambiar la escala, a continuación, mediante el intercambio de un subconjunto de los del mismo tamaño de las porciones puede equilibrar la balanza, porque hay una cantidad de bienes monedas.