Optimizar el número de días para encontrar una cookie envenenada

Question

A un amigo mío se le hizo esta pregunta para una entrevista y no pudo resolverla en ese momento. Pensé que compartiría lo mismo.

Hay miles de cookies con uno de ellos envenenado. Usted tiene acceso a 10 ratas de laboratorio por día. Cada rata puede mordisquear cualquier número de las cookies y cada cookie puede ser mordiscada por cualquier cantidad de ratas. Después de una rata mordisquea una galleta envenenada, se tarda un día en ver los efectos posteriores a en la rata si se envenenó.

Optimizar en el número de días. Pude encontrar un algoritmo para encontrar la cookie envenenada en 2 días, aunque creo que existe una forma de hacerlo en 1 día

Answer 1

Creo que lo tengo.

Imagina un árbol binario con las 1024 cookies como raíz (Este número acaba siendo más limpio, pero esto funcionará para cualquier número menor que 1024). Divida esas 1024 cookies en dos grupos de 512, cada uno de esos grupos es el hijo de la raíz. Luego divide cada uno de esos grupos de 512 en grupos de 256 y deja que esos sean los hijos de cada uno de ellos, y así sucesivamente. Deberías terminar con 11 niveles del árbol.

Asigne cada rata a un nivel del árbol, excepto la raíz. Cada rata comerá solo las galletas en las ramas izquierdas de su nivel. Al día siguiente, recorra el árbol y, por cada rata que murió, siga la rama izquierda, para cada rata que vivió, siga la rama derecha. La cookie resultante debe ser la envenenada.

Answer 2

Ésta es la solución "fácil" en tres días:

• En primer lugar, permite que cada rata para picar 100 cookies.
• Después de un día, permita que cada rata mordisque 10 de las galletas comidas por la rata muerta.
• Después de dos días, permita que cada rata mordisquee una de las galletas comidas por la segunda rata muerta.
• Después de tres días, sabrá qué cookie está envenenada.

Ahora para la solución de "duro" en un solo día:

• Número todas las cookies en binario.
• Cada rata es para picar en aquellas cookies cuya representación binaria tiene un bit establecido en el índice de la rata. Entonces, por ejemplo, rat 1 mordisqueará todas las cookies impares.
• Dicho de otra manera, cookie 37 será mordisqueado por las ratas 1, 3 y 6. Entonces, si esas exactamente tres ratas mueren al día siguiente, usted sabe que la cookie 37 fue la envenenada.