Usted tiene 15 bolas, 2 de ellos son radiactivos. Usted tiene que ejecutar 7 pruebas (no más) en las bolas que se ordene la 2 radiactivos queridos garantizado en todo momento. Usted puede probar en grupos, o incluso uno por uno.
Una "prueba" se compone de tomar un subconjunto de las bolas y la comprobación de si este subconjunto contiene un radiactivos bola (uno o más) o no. La prueba no determina el número de radiactivos de bolas en la prueba del subconjunto.
Usted debe hacer la medición de la siguiente manera. "[x,...,y] true/false" significa que la radiactividad se encuentra / no se encuentra cuando la medición de las bolas con el número x,...,y. Las dos últimas líneas de cada uno de los párrafos son las tuplas que son posibles después de la última medición es de tipo verdadero / falso. Es fácil de procesar el resto de posibilidades
measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] true
measurement 3: [1,2,7,8,9,10,11] true
measurement 4: [1,2,7] true
measurement 5: [1,6]
[[1,4],[1,5],[1,6],[2,6]]
[[2,4],[2,5],[4,7],[5,7]]
measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] true
measurement 3: [1,2,7,8,9,10,11] true
measurement 4: [1,2,7] false
measurement 5: [4]
[[4,8],[4,9],[4,10],[4,11]]
[[5,8],[5,9],[5,10],[5,11]]
measurement 1: [1,2,3,4,5] true
measurement 2: [4,5,6] true
measurement 3: [1,2,7,8,9,10,11] false
measurement 4: [12,13,14,15]
[[4,12],[4,13],[4,14],[4,15],[5,12],[5,13],[5,14],[5,15]]
[[3,4],[3,5],[3,6],[4,5],[4,6],[5,6]]
measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] false
measurement 3: [7,8,9,10,11] true
measurement 4: [1,7] true
measurement 5: [7,8]
[[1,7],[1,8],[2,7],[3,7]]
[[1,9],[1,10],[1,11]]
measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] false
measurement 3: [7,8,9,10,11] true
measurement 4: [1,7] false
measurement 5: [2]
[[2,8],[2,9],[2,10],[2,11]]
[[3,8],[3,9],[3,10],[3,11]]
measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] false
measurement 3: [7,8,9,10,11] false
measurement 4: [1,12]
[[1,2],[1,3],[1,12],[1,13],[1,14],[1,15],[2,12],[3,12]]
[[2,3],[2,13],[2,14],[2,15],[3,13],[3,14],[3,15]]
measurement 1 [1,2,3,4,5] false
measurement 2: [6,7,8] true
measurement 3: [6]
[[6,7],[6,8],[6,9],[6,10],[6,11],[6,12],[6,13],[6,14],[6,15]]
[[7,8],[7,9],[7,10],[7,11],[7,12],[7,13],[7,14],[7,15],
[8,9],[8,10],[8,11],[8,12], [8,13],[8,14],[8,15]]
measurement 1 [1,2,3,4,5] false
measurement 2: [6,7,8] false
measurement 3: [9,10] true
measurement 4: [9]
[[9,10],[9,11],[9,12],[9,13],[9,14],[9,15]]
[[10,11],[10,12],[10,13],[10,14],[10,15]]
measurement 1 [1,2,3,4,5] false
measurement 2: [6,7,8] false
measurement 3: [9,10] false
measurement 4: [11]
[[11,12],[11,13],[11,14],[11,15]]
[[12,13],[12,14],[12,15],[13,14],[13,15],[14,15]]
Editar:
¿Cómo se puede comprobar esto? Primero de todos, usted debe verificar que estos párrafos son el nodo de un árbol. A continuación, puede ver cada párrafo comparando cada uno de los 105 pares de cojones [[1,2],...,[14,15]] con las mediciones. Tome la primera a la par [1,2] y el siguiente párrafo
measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] false
measurement 3: [7,8,9,10,11] true
measurement 4: [1,7] true
measurement 5: [7,8]
[[1,7],[1,8],[2,7],[3,7]]
[[1,9],[1,10],[1,11]]
Medición 3 debe ser verdadera, pero esto está mal para este par, por lo que puede omitirse. Llevar a la pareja [1,7]. Medición 1,3,4,5 es verdadera y medición 2 es falsa, por lo tanto está en la penúltima línea. Para el par [1,9] de nuevo la medición 2 es falsa y la medición 1,3,4 es cierto, pero de medición de 5 es falsa, por lo tanto está en la última línea. así que todo nodo del árbol puede ser comprobado. Usted puede hacer estas comprobaciones con un programa simple (yo usé uno escrito en maxima).
Edit: Maxima-Programa De
f(n,ll_found,ll_notfound):=block(
[
remaining:[],
passed
],
for i:1 thru n do (
for j:i+1 thru n do (
passed:true,
for s in ll_found do
if not(member(i,s) or member(j,s)) then
passed:false,
for s in ll_notfound do
if not(not member(i,s) and not member(j,s)) then
passed:false,
if passed then
remaining:endcons([i,j],remaining)
)
),
return(remaining)
);
block([u,v],
for i:1 thru 14 do (
for j:i thru 15 do (
u:length(f(15,[[1,2,3,4,5],makelist(k,k,i,j)],[])),
v:length(f(15,[[1,2,3,4,5]],[makelist(k,k,i,j)])),
if (u<=32 and v<=32) then print([i,j,u,v])
)
)
);
/* measurement 1: [1,2,3,4,5] */
length(f(15,[[1,2,3,4,5]],[]));
length(f(15,[],[[1,2,3,4,5]]));
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] */
length(f(15,[[1,2,3,4,5],[4,5,6]],[]));
length(f(15,[[1,2,3,4,5]],[[4,5,6]]));
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] true
measurement 3: [1,2,7,8,9,10,11] */
f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11]],[])$length(%);
f(15,[[1,2,3,4,5],[4,5,6]],[[1,2,7,8,9,10,11]])$length(%);
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] true
measurement 3: [1,2,7,8,9,10,11] true
measurement 4: [1,2,7] */
f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11],[1,2,7]],[])$length(%);
f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11]],[[1,2,7]])$length(%);
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] true
measurement 3: [1,2,7,8,9,10,11] true
measurement 4: [1,2,7] true
fuenfte Messung: [1,6]
und fertig, da trivial*/
f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11],[1,2,7],[1,6]],[]);length(%);
f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11],[1,2,7]],[[1,6]]);length(%);
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] true
measurement 3: [1,2,7,8,9,10,11] true
measurement 4: [1,2,7] false
trivial da [4,5] * [8,9,10,11]*/
f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11]],[[1,2,7]]);
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] true
measurement 3: [1,2,7,8,9,10,11] false
measurement 4: [12,13,14,15]
und trivial*/
f(15,[[1,2,3,4,5],[4,5,6],[12,13,14,15]],[[1,2,7,8,9,10,11]]);length(%);
f(15,[[1,2,3,4,5],[4,5,6]],[[1,2,7,8,9,10,11],[12,13,14,15]]);length(%);
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] false
measurement 3: [7,8,9,10,11] */
f(15,[[1,2,3,4,5],[7,8,9,10,11]],[[4,5,6]])$length(%);
f(15,[[1,2,3,4,5]],[[4,5,6],[7,8,9,10,11]])$length(%);
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] false
measurement 3: [7,8,9,10,11] true
measurement 4: ,[1,7] */
f(15,[[1,2,3,4,5],[7,8,9,10,11],[1,7]],[[4,5,6]])$length(%);
f(15,[[1,2,3,4,5],[7,8,9,10,11]],[[4,5,6],[1,7]])$length(%);
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] false
measurement 3: [7,8,9,10,11] true
measurement 4: ,[1,7] wahr
fuenfte Messung: [7,8] arbitrary
trivial*/
f(15,[[1,2,3,4,5],[7,8,9,10,11],[1,7],[7,8]],[[4,5,6]]);length(%);
f(15,[[1,2,3,4,5],[7,8,9,10,11],[1,7]],[[4,5,6],[7,8]]);length(%);
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] false
measurement 3: [7,8,9,10,11] true
measurement 4: ,[1,7] false
trivial, da {2,3} * {8,9,10,11}*/
f(15,[[1,2,3,4,5],[7,8,9,10,11]],[[4,5,6],[1,7]]);length(%);
/* measurement 1 [1,2,3,4,5] true
measurement 2: [4,5,6] false
measurement 3: [7,8,9,10,11] false
measurement 4: [1,12] arbitrary
trivial */
f(15,[[1,2,3,4,5],[1,12]],[[4,5,6],[7,8,9,10,11]]);length(%);
f(15,[[1,2,3,4,5]],[[4,5,6],[7,8,9,10,11],[1,12]]);length(%);
/* measurement 1 [1,2,3,4,5] false
measurement 2: [6,7,8] */
f(15,[[6,7,8]],[[1,2,3,4,5]])$length(%);
f(15,[],[[1,2,3,4,5],[6,7,8]])$length(%);
/* measurement 1 [1,2,3,4,5] false
measurement 2: [6,7,8] true
measurement 3: [6] arbitrary
trivial*/
f(15,[[6,7,8],[6]],[[1,2,3,4,5]]);length(%);
f(15,[[6,7,8]],[[1,2,3,4,5],[6]]);length(%);
/* measurement 1 [1,2,3,4,5] false
measurement 2: [6,7,8] false
measurement 3: [9,10] */
f(15,[[9,10]],[[1,2,3,4,5],[6,7,8]]);length(%);
f(15,[],[[1,2,3,4,5],[6,7,8],[9,10]]);length(%);
/* measurement 1 [1,2,3,4,5] false
measurement 2: [6,7,8] false
measurement 3: [9,10] true
measurement 4: [9] arbitrary
trivial */
f(15,[[9,10],[9]],[[1,2,3,4,5],[6,7,8]]);length(%);
f(15,[[9,10]],[[1,2,3,4,5],[6,7,8],[9]]);length(%);
/* measurement 1 [1,2,3,4,5] false
measurement 2: [6,7,8] false
measurement 3: [9,10] false
measurement 4: [11] arbitrary
trivial */
f(15,[[11]],[[1,2,3,4,5],[6,7,8],[9,10]]);length(%);
f(15,[],[[1,2,3,4,5],[6,7,8],[9,10],[11]]);length(%);
Editar:
¿Cómo puedo derivar el resultado? Con ensayo y error. El siguiente Lema que guía nuestras pruebas
Lema 1 (sin prueba): En cada paso del algoritmo se cumple lo siguiente: Deje de $S$ es la lista de los restantes solución posible y $M$ es la lista de bolas para ser medido y $$ n el número de mediciones. Vamos a $ T(S,M)$ es la lista de todos los pares de $S$, donde al menos uno de los elementos de la pareja está en $M$ y dejar que $F(S,M)$ la lista de todos los pares de $S$ donde ningún elemento de la pareja está en $M$. A continuación, la siguiente es una condición necesaria para un algoritmo para resolver todas las instancias del problema. $$\begin{align*} |S|&\leq 2^n\\ |T(S,M)|&\leq 2^{n-1}\\ |F(S,M)|&\leq 2^{n-1} \end{align*}$$
Después de este paso, el nuevo S $T(S,M)$ o $F(S,M)$ en función del resultado de la medición $M$. El nuevo $n$ es $n-1$.
La búsqueda de dos bolas con en la mayoría de los k measuremants de n bolas que llamar a un (n,k)-problema. Queremos encontrar un algoritmo para la (15,7)-problema.
El (15,7)-problema por lo tanto $\binom{15}{2}=105$ posible solución de los pares y, por tanto, un algoritmo para encontrar un par que hacer al menos 7 de las mediciones en el
el worstcase porque $2^6<105<2^7$. Queremos investigar la primera medición. Vamos a arange la lista de todos los posibles bola combinación de los siguientes
triángulo de manera
[1,2] [1,3] [1,4] ... [1,14] [1,15] 14 pairs row 1
[2,3] [2,4] ... [2,14] [1,15] 13 pairs row 2
. . . .
. . . .
. . . .
[13,14] [13,15] 2 pairs row 13
[14,15] 1 pair row 14
si la primera medición se hizo con la lista de dólares[1,\cdots,m]$ entonces $14+13+(15-m)<=2^6$ y $(15-m+1))+...+2+1<=2^6$ deben tener. $2^6=64$ por lo tanto $m$
4 $$ o $5$. si $m=3$ y por tanto $M=[1,2,3]$ entonces $|F(S,M)|=1+2+\cdots + 11=66>2^6=64$, si $k=6$ $M=[1,2,3,4,5,6]$ y $|T(S,M)|=14+13+\cdots + 9 = 69 > 2^6=64$.
si para la primera medición $m=4$ y por tanto $M=[15,14,13,12]$ y el resultado de la medición es falsa, entonces uno debe encontrar con en la mayoría de los $6$
la medición de la radiactivos par en el resto de los $11$ pelotas. así que debemos guardar la (11,6)-problema.
Lema 2: no Existe ningún algoritmo para el (6,4)-problema.
Prueba: Si $M=[1]$ entonces $|F(S,M)|=4+3+2+1=10>8=2^3$. Si $M=[1,2]$ entonces $|T(S,M)|=5+4=9>8=2^3$.
Lema 3: no Existe ningún algoritmo para el (8,5) problema.
Prueba: para la primera medición: $M=[1]$ o $M=[1,2,3]$ no son posibles con los mismos argumentos que en el (6,4) caso. Por lo tanto $M$ debe $[1,2]$. Si el resultado de la medición es falso, el algoritmo debe resolver el (6,4)-problema que es imposible por el Lema 2.
Lema 4: no Existe ningún algoritmo para el (11,6)-problema.
Prueba: si $M=[1,2]$ entonces $|F(S,M)|=36>32=2^5$, si $M=[1,2,3,4]$ entonces $T(S,M)=34>32=2^5$. por lo tanto $M$ debe $[1,2,3]$. Supongamos que la primera medición es falso 8 bolas de restos y nuestro algoritmo debe resolver la (8,5)-problema que es imposible por el lema 3.
Desde Lema 4 el razonamiento antes de llemma 2 en la siguiente de la siguiente manera:
Lema 5: Si existe un algoritmo para la (15,7)-problema de su primera medición debe medir una lista de 5 pelotas.
Podemos suponer que la primera medida está en la lista [1,2,3,4,5]. La segunda medida es en una lista [x,x+1,...,y] que tiene cero, uno o más elementos
en común con [1,2,3,4,5]. Primero probé [6,7,8,9,10,11] pero tuvo problemas para continuar. Por lo tanto he usado mi programa para comprobar cada uno de los 105 N=[x,...,y] si $T(S,N)<=2^5=32$ y $F(S,N) <32$.
las siguientes listas fueron encontrados por el programa [4,5,6]
[5,6,7,8,9]
[6,7,8,9,10,11]
el programa también se encuentra en las listas [7,...,12]
[8,...,13]
[9,...,14] [10,...,15] pero estas listas son básicamente las mismas [6,...,11] después de cambiar el nombre de las bolas.
Me siguió con la lista [4,5,6]. El resto de las mediciones que se encuentran juicio un error con mi función y el lema 1. Si uno busca en la tercera medición después de [1,2,3,4,5] y [4,5,6] uno puede usar el hecho de que los números [1,2,3], [4,5], [7,8,9,10,11,12,13,14,15] son equivalentes en relación a [1,2,3,4,5] y [4,5,6]. esto reduce los casos a investigar.
He aquí una generalización. Vamos a $n(t)$ indicar el número máximo de bolas para que 2 radiactivos pueden ser identificados en $t$ pruebas. miracle173 efectivamente ha demostrado que $n(4) = 5$, $n(5) = 7$, $n(6) = 10$ y $n(7) \geq 15$.
En el "Grupo de prueba con dos y tres defectos" (Anales de la New York Academy of Sciences 576, pp 86-96, 1989) Chang, Hwang, y Weng dar explícita de los procedimientos de prueba que muestra que $n(8) = 22$, $n(9) = 31$, $n(10) = 44$ y $n(11) = 63$. También dan explícita de los procedimientos de prueba de que el rendimiento de los límites inferiores de $$n(t) \geq 89 \cdot 2^{\frac{t}{2}-6}, t \text {, incluso, } t \geq 12;$$ $$n(t) \geq 63 \cdot 2^{\frac{t-1}{2}-5}, t \text{ impar, } t \geq de 13.$$
(Toman como sabe que $n(7) = 15$. Véase también Chang, Hwang y Lin, "Grupo de prueba con dos defectos," Discreta Matemática Aplicada 4 (2), pp 97-102, 1982.)
En la Combinatoria del Grupo de Prueba y Sus Aplicaciones, por Du y Hwang, se muestra que, para $t \geq 4$, tenemos el límite superior $$n(t) \leq 2^{\frac{t+1}{2}} - 1/2.$$
Los límites inferiores y superiores implica que, por ejemplo, $n(12)$ es el 89 o 90.
Este problema va por el nombre de "adaptación de la combinatoria del grupo de pruebas con dos defectos." El Du y Hwang texto parece ser el estándar de referencia para estos tipos de problemas.
Tener dos objetos de destino realmente hace que este problema sea mucho más difícil. Hay ${15 \elegir 2} = 105$ resultados posibles, y con 7 pruebas binarias usted sólo puede distinguir entre un total de 128 posibilidades. Así que usted no tiene un montón de espacio para el error; que bastante tienen para cortar el espacio de la solución en la mitad con cada prueba.
Dicho esto, creo que el mejor algoritmo comienza por probar objetos de 12 a 15. Si esta prueba da "no", entonces usted sabe que ambos objetos se encuentran en las 11 restantes objetos (55 posibilidades). De lo contrario, al menos uno de los objetivos es en estos cuatro (50 posibilidades). Después de que se hace mucho más complicado, pero básicamente, cada vez que intente hacer una prueba que se divide el resto de los posibles resultados como exactamente en la mitad como sea posible. Por ejemplo, si usted ha reducido a 11 de objetos, objetos de prueba 9-11 (28 no, frente a 27 sí). Si al menos uno de 12-15 es radiactivo, de la prueba de 8 a 12 (24 no vs 26 sí).
No puedo pensar en una manera simple de explicar la completa algoritmo, como el equilibrio ternario representación de la tradicional pesaje problema. Pero continuando en este patrón debe darle la respuesta.
No creo que se pueda hacer, pero mi prueba no es completa. Como Pablo Z dice, se ve a la derecha a prueba de 12, 13,14, 15, primero como dividir las posibilidades tan uniformemente como sea posible-50/55. Si el primer examen que detecta la radiactividad puede tener éxito. Ahora a probar 5, 6, 7, 8, 9, 10, 11. Si usted vuelve a encontrar la radiactividad, usted puede hacer búsquedas binarias de 4 y 7 con 5 pruebas. Si no, prueba 1, 2, 3, 4. Si usted encuentra que la radiactividad que usted puede hacer búsquedas binarias de 4 y 4 con 4 pruebas. Si no, usted tiene 4 pruebas para encontrar 2 entre los 12, 13, 14, 15 y sólo puede ir uno por uno.
Si la primera prueba falla, tiene 55 posibilidades y 6 pruebas de la izquierda. Ahora tiene a prueba 9, 10, 11, dejando 28 de posibilidades si la prueba falla y 27 si encuentra la radiactividad. Las pruebas de 10, 11 hojas 36 si se produce un error y la prueba 8, 9, 10, 11 hojas 34 si se realiza correctamente, en ambos casos mayor que 2^5=32. Centrándose en el caso de la prueba de 9, 10, 11 falla tienes que probar 7,8 por una lógica similar. De nuevo en el caso de falla de los 15 posibilidades. Si la prueba es de sólo 6, y no hay 10 posibilidades y si usted prueba 5,6 y tener éxito hay 9. En cualquiera de los casos 3 más pruebas no son suficientes.
El agujero es probar que usted no puede tener éxito mediante la prueba de 11, 12, 13, 14, 15. Si la prueba tiene éxito, usted tendrá 60 posibilidades, por lo que parece poco probable que usted puede conseguir allí, pero no he hecho los detalles.
Añadido: algunos más progreso. Si la prueba de 11,12,13,14,15 y obtener sí parece natural a prueba de 5,6,7,8,9,10 próximo en que se divide el 60 posibilidades de manera uniforme. Si usted obtiene sí, una vez más se fijan. Prueba 5,6,11. Si no, usted tiene dos grupos de 4 y 4 aciertos. Si sí, la prueba 11. Si sí tienes un grupo de 6 y 3 aciertos. Si no, usted dispone de 4+2 y 3 aciertos. Pero, si no obtiene en la prueba de 5,6,7,8,9,10 parece natural a prueba de 2,3,4 como que le dará 15 posibilidades de cualquier manera. Pero no te deja con la búsqueda de 2 de los 6 con 4 conjeturas y no hay una prueba que se hace una división de 7/8 posibilidades. Puede haber algo mejor estrategia.
Si la prueba de 11,12,13,14,15 y conseguir que no se establece. Prueba 8,9,10. Si sí, hay 24 posibilidades. Prueba 4,5,6,7. Sí te da 3+4 con 4 pruebas de la izquierda. Si no, prueba 2,3. Un sí le da 2+3 con 3 pruebas. No le da 4 bolas con 2 a encontrar y 3 pruebas. Prueba de 3 de manera individual. Si 8,9,10 no da, prueba de 6,7. No da 5 bolas para encontrar 2 en 4 pruebas-just do 4 de forma individual. Si sí la prueba de 3,4,5. Sí da 2+3 en 3 pruebas. No se dispone de 4 bolas con 2 a encontrar con 3 pruebas.
Esto es similar a http://mathoverflow.net/questions/59939/identifying-poisoned-wines
No es lo mismo, pero tal vez lo suficientemente cerca como para derivar un poco de inspiración.
Como se señaló en MO, fue aquí la primera: la Lógica del problema: Identificar envenenado vinos de una muestra, minimizando los sujetos de prueba con restricciones
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
