Tenemos 50 trabajadores y la sospecha de que 3 están infectados. ¿Cual es el mínimo número de test que necesitamos hacer para poder determinar a qué tres trabajadores debemos mandar a casa en cuarentena?
Portada
mis comunidades
otras secciones
Comentarios
#37
EXPLICACIÓN CORTA:
Si coges los tres y salen todos negativos, como hay un caso positivo en cada grupo de 10 (pues hay 3 casos en total), sabes que hay un caso positivo en cada uno de los grupos de 5 que no hemos testado.
EXPLICACIÓN LARGA
Digamos que los tres grupos son:
A=
B=
C=
Los divides en:
A1=; A2=
B1=; B2=
C1=; C2=
Hago test a A1, B1 y C1 (3 test). Si salen tres negativos, sé que tengo un caso en A2, un caso en B2 y un caso en C2.
Hago una segunda división:
A21=; A22=
B21=; B22=
C21=; C22=
Hago test a A21, B21 y C21 (3 test). En el peor de los casos, tengo 3 positivos (9 individuos sospechosos), por lo que tendría que hacer 6 test extra.
Total: 5+3+3+6= 17 test
#38 Joer...
Complejo, pero brillante!!!
Muchas gracias
#39 #38 Y me da que erroneo:
La complejidad al resolver se da cuando coinciden varios positivos en una misma columna.
En el caso de #38, varios positivos en una columna complican la solucion:
5 test para los grupos iniciales. Supongamos que quedan 2 columnas solo. Una con 2 infectados y otra con 1 (no sabemos cual es cual)
A=
B=
Los divides en:
A1=; A2=
B1=; B2=
haces 4 test en el peor caso y te quedan 3 grupos.
A21=; A22=
B21=; B22=
C21=; C22=
En el peor caso, suponiendo un positivo en C22, uno en A21 y otro en B22, tienes 6 test en este caso.
C22 lo sacas solo con un test, en A21 y B21 te hacen falta 2 -> 5 mas
5+4+6+5 = 20.
Asi que, con vuestro permiso, retomo mi resolucioon y arreglo el final:
15 test, uno por cada fila y uno por cada columna, el peor caso es que haya 2 infectados en la misma columna / fila (si ninguno repite file ni columna ya estan identificados). Si quito todas las filas y columnas que no tienen ningun infectado me queda una matriz 3x2 con 2 infectados en la dimension del '3' y 1 en la dimension del '2', de modo que con 3 test en el peor de los casos lo tengo hecho:
15 + 3 = 18
Que alguien me corrija si me he equivcocado, que no son horas...
#41 #38 No tengo los bastantes huevos para discutir con vosotros...
#41 Te has equivocado. Creo que te has liado porque la solución completa que propongo está en mi comentario en #31, y el de #38 era solo una aclaración para #0 sobre el primero de los casos. El caso que comentas (2 positivos) explico cómo hacerlo en el caso 3.
Efectivamente, ese es el peor caso y el resultado es 18. He llegado a un montón de soluciones con 18 test, pero de momento no consigo bajar de ahí.
#4 Nooooo
Muchos menos
Si no, vaya mierda de acertijo...
#5 Mmm... Fijo que se me escapa algo. Pero, si haces los test de manera aleatoria y haces, por ejemplo, 46 test que te salen negativo (es improbable, pero posible), ¿cómo sabes cuáles de los otros cuatro trabajadores están enfermos y cuál está sano?
#6 La jugada es que si mezclas las muestras, y hay un positivo en la mezcla, la mezcla es positiva, pero si no lo hay, todo el grupo mezclado es negativo.
¿Qué tal con esa pista? Se pueden mezclar muestras, y en Alemania se hace.
El ahorro o la mayor capacidad de análisis es cuestión de ingenio, parece. Y no sólo de contar con más medios.
#7 Ah, que los test no son individuales. Vale, vale, es como el problema de la moneda trucada y la balanza.
#8 esa era parte de la solución que nunca se me habría ocurrido...
#9, es que esa parte de la solución no es real. Si los test no son 100% fiables, si además reduces mezclando muestras el porcentaje de lo detectable ya ni te digo.
#8 DE hecho en casa hemos hecho modelos probabilísticos de detección de casos mejorando el algoritmo de test grupales metiendo modelos bayesianos. El problema es que los test no ayudan mucho por cómo funcionan.
#0 Solución con 18 test.
Dividimos los 50 en 5 grupos de 10 y les hacemos el test.
Caso 1: 3 positivos. Tenemos 30 casos sospechosos y sabemos que los 3 infectados están en 3 grupos diferentes. De cada uno de los grupos, cogemos 5 personas y les hacemos el test. Tenemos 3 grupos de 5 personas sospechosas. Coges 3 personas del primer grupo de 5 y les haces el test.
Caso 1.1: Positivo. Testas a 2 de ellos por separado. (Peor caso)
Caso 1.2: Negativo. Testas a 1 de los 2 restantes. (Mejor caso)
Repites con otros 2 grupos de 5.
Total: 5+3+3*3=17 test
Caso 2: 1 positivo. Trivialmente, basta hacer 2 test extra. Total: 5+2=7 test.
Caso 3: 2 positivos. Tenemos 20 personas sospechosas. Los dividimos en 4 grupos de 5 y hacemos 4 test más. Con los 3 grupos de 5 personas positivas, hacemos como en el caso 1.
Total: 5+4+3*3=18 test.
#31 No lo acabo de ver, pero espera que lo revise mejor. Seguramente sea culpa mía.
#33 ¿Cuál de los tres casos no te queda claro?
#34 María, jolín... estoy espeso...
De verdad que es culpa mía...
Lo miro...
#34 A ver.. María... Te cuento:
En el caso 1, descartas 20 a la primera entrada.
"Caso 1: 3 positivos. Tenemos 30 casos sospechosos y sabemos que los 3 infectados están en 3 grupos diferentes. De cada uno de los grupos, cogemos 5 personas y les hacemos el test. Tenemos 3 grupos de 5 personas sospechosas. Coges 3 personas del primer grupo de 5 y les haces el test."
Si cuando coges los tres grupos de 5 personas, salen todos negativos, ¿cuantos test estamos haciendo?
Insisto en que soy muy bruto...
Por eso me gusta tanto la solución de #18 Porque la entiendo
#33 Vale, no es culpa tuya, es mía. En el caso 3 faltan consideraciones que no he puesto, pues me he centrado en el peor caso. Explicado mejor:
Caso 3: 2 positivos. Tenemos 20 personas sospechosas. Los dividimos en 4 grupos de 5 y hacemos 4 test más.
Caso 3.1: 3 positivos. Hacemos como en el Caso 1. (Peor caso)
Caso 3.2: 2 positivos. Tenemso 10 sospechosos. Hacemos 7 test extra.
Caso 3.3: 1 positivo. Tenemos 5 sospechosos. Hacemos 2 test extra.
Lo planteas de forma ambigua. ¿Sospechas que tienes tres casos en tu empresa o sospechas de tres trabajadores concretos y quieres hacer test para ver si hay alguno más? ¿Con "saber" te refieres a saberlo con una cierta probabilidad o a tener la certeza?
#2 Sé que tengo tres trabajadores, para simplificarlo, y no sé cuales son. Certeza. Y no sé cuales son.
#3 ¿47 test? Si tienes muy mala suerte, claro.
#4 Si haces 47 tests y te salen dos positivos, ¿Como sabes cual de las otras 3 personas es positiva?
#27 Oye, no te rías de mí, que no había entendido el problema. He encontrado dos soluciones distintas con 19 test. Pero no consigo bajar de ese número.
Solución:
A mí me salen 24.
Partes los 50 en 10 grupos de 5. Con la peor suerte posible, habrá tres grupos positivos y siete negativos. Quedan pues, 15 personas dudosas. Haces cinco grupos de tres. Los mismo. en el peor caso, te pueden quedar 9 personas dudosas, a las que analizas una a una.
Total, 24
Seguro que esos elementos obtuvieron una solución mejor. Pero yo no la tengo.
#2 #11 #13
#15 Así de primeras, diría que la solución óptima no es lineal, sino más bien del tipo:
Empiezo de este modo. Si ocurre esto, hago lo siguiente; si ocurre esto otro, prosigo así... Mañana lo pienso.
#15 #16 Con una solución de ese tipo, me salen 19. Pero creo que es mejorable.
#17 Para mí, la de 18 es superbrillante.
Lo que propones no sé si sirve para todo caso...
#20 Te digo mi solución, que llega a un todal de 19 test en el peor caso, aunque es un poco enrevesada.
Cogemos 10 grupos de 4 personas, les hacemos el test y dejamos 10 personas sin testar.
Caso 1: 3 positivos. Tenemos 12 sospechosos. Además, sabemos que hay 1 caso por grupo. Cogemos 2 personas de cada grupo y les hacemos el test. Ahora tenemos 3 grupos de 2 personas cada uno, con un positivo en cada grupo. Basta hacer 3 test más. Total: 10+3+3=16 test.
Caso 2: 0 positivos. Tenemos 10 sospechosos (los quë habíamos dejado sin testar). Basta hacer 7 test más. Total: 10+7=17 test.
Caso 3: 2 positivos. Tenemos 18 sospechosos (los 10 sin testar en un principio y 2 grupos de 4). Separamos los 10 sin testar en 2 grupos de 5.
Caso 3.1: 0 positivos en los grupos de 5. Basta hacer 5 test más a los 8 de los grupos de 4. Total: 10+2+5=17 test.
Caso 3.2: 1 positivo en los grupos de 5. Tenemos 3 grupos (2 de 4 y uno de 5) con un caso en cada grupo. Cogemos 2 personas de cada grupo de 4 y 3 del grupo de 5 y les hacemos el test. En el peor de los casos, necesitas hacer otros 4 test extra. Total: 10+2+3+4=19 test.
Caso 4: 1 positivo. Tenemos 14 sospechosos. Con los 10 sin testar, hacemos 2 grupos de 4 y 1 de 2. En el peor de los casos, habrá 3 positivos en los 3 grupos de 4. Hacemos como en el caso 1. Total: 10+3+3+3=19 test.
Yo creo que tiene que haber una solución mejor, pero ayer no se me ocurrió ninguna otra.
#15 Empezando como tú, hay otra forma para que salgan 19:
«Partes los 50 en 10 grupos de 5. Con la peor suerte posible, habrá tres grupos positivos y siete negativos. Quedan pues, 15 personas dudosas.» Además, sabes que hay 1 caso en cada uno de los 3 grupos de 5. Coges 3 personas del primer grupo de 5 y les haces el test.
Caso 1: Positivo. Testas a 2 de ellos por separado. (Peor caso)
Caso 2: Negativo. Testas a 1 de los 2 restantes. (Mejor caso)
Repites con otros 2 grupos de 5.
Total: 10+3*3=19 test.
Volvemos al mismo número de #22
#15 21 en el peor de los casos:
50 en 10 grupos de 5: imaginalos como una matriz:
Test cada fila y cada columna: 15 test
Si no hay 2 en la misma fila / columna puedes ver las coordenadas con 15 test.
Si hay 2 en la misma fila / columna eliminas todas las filas / columnas que no tienen ningun infectado y te quedan 2 filas / columnas de 3 elementos: 6 test mas.
15 + 6.
Aun asi es un numero del mismo orden... tampoco es mucho avance...
#18 Eres el putísimo amo.
Me como la boina. Le había dado 500 vueltas.
#19 Uy....
MIRA MAMA! ME DICEN COSAS BUENAS POR INTERNET!!!
No ha tenido merito, me la has dejado votando.
Me he puesto rojo y todo...
En fin, seguro que alguien encuentra alguna solucion mejor...
Solo se me ocurre optimizarla (el peor caso queda igual).....
La matriz de 7 x 7 + 1 que se queda fuera de la matrix:
14 tests en filas / columnas -> si no estan en la misma fila / columna vale con 14.
Sino hay que hacer al que se ha quedado fuera, si es positivo con esos 15 vale, sino se suman las 6 de nuevo y 21 el peor caso
Disclaimer: cosas de los periódicos alemanes...
Por cierto: llegué a leer el razinamiento de la solución, pero no la solución en sí, así que cuando toque, os daré la mía, advirtiendo de que alguien puede mejorarla.
Cuando te dispongas a hacer los test, seguramente tengas ya más de tres trabajadores infectados.
Además, tu no puedes hacer los test, la salud de un empleado es un tema entre empleado y médico, el patrón no puede saber nada, si el empleado no lo desvela.
No creo que sea la respuesta que buscas, pero es la más realista que vas a encontrar.
Edit y PD: posiblemente la respuesta sea, hazselo al español, al francés y al italiano, algo que sería muy del palo de los alemanes.
#13 Método Pantone, ¿eh?
Jjajajajaja
No lo descartes.
Cero test y todos pa'casa.
Creo que puedo demostar, que se puede encontrar un número desconocido de casos en una muestra determinada con 2xlogbase2( N) tests. Es decir que para 64 pacientes, se necesitan solo 12 tests para encontrar quienes son.
Describo el algoritmo:
1-Asignamos una número correlativo a la muestra de cada persona, y cogemos la representación en binaria de ese número.
2-De manera iterativa dividimos las muestras en dos grupos, mezclamos las muestras de cada grupo, y realizamos un test por separado a cada grupo. Es decir Si tenemos 64 muestras tendremos dos grupos de 32. Si tenemos 128 dos de 64.
En cada interacción seleccionamos la pertenencia a un grupo o a otro dependiendo del número de iteración y del bit correspondiente de la representación binaria de la muestra. Así pues En la primera interación agrupamos por el primer bit. En la segunda por el segundo bit, y asi sucesivamente. Si un test da positivo marcamos las muestras que estaban en ese grupo de tests con una crucecita.
Los infectados, son las que han dado positivo en todos los tests que se ha sometida a la muestra. Es decir tienen tantas marcas como iteraciones hemos hecho.
Para cincuenta muestras, el número binario mas grande donde lo podemos meter es 64. Es decir que con 12 tests podemos localizar a todos los positivos.
El algoritmo es optimizable si se hacen los tests de forma secuencial. Es decir que si en la primera interación un grupo sale 0, no es necesario hacer mas tests en ese grupo. Si los dos salen 0. Ya hemos terminado.
Por otro lado, tambien se pueden hacer todos los tests en paralelo, lo que permite ganar tiempo en el proceso de las muestras.
Lo bonito del algoritmo es que escala en base a log2, es decir crece muy poco. Si en lugar 64, tenemos 256, solo necesitamos hacer 16 tests y 1024 personas con 20. y 45 millones de pacientes con 50 tests
Puedes plantearlo como un acertijo. ¿Cuántos tests son necesarios para determinar el número de infectados de forma unívoca si se mezcla la saliva de tres personas en cada test?
#24 ¡Ay que este sub ya es sobre acertijos! creía que iba en serio.
Lectura diagonal...
Partes los 50 en 10 grupos de 5. (10 tests)
En el peor de los casos, tienes 15 sospechosos. Los partes en 5 grupos de tres (5 tests)
-----
En el mejor de los casos, un grupo da positivo y los otros dos negativos. 15 tests.
En el peor de los casos, tienes 9 sospechosos. Los metes a todos en una sala cerrada sin aire acondicionado y les ordenas que chupen los pomos de las puertas.
Has detectado a todos los infectados, que ahora son 9, con 15 tests.
#29 👏 👏 👏 👏
#0 tres test...
#11 Y una suerte d ela hostia, claro
jajajajaja