Yo tengo una solución para el siguiente rompecabezas, que creo que es la respuesta correcta, pero no he sido capaz de venir para arriba con una manera de demostrar que es la respuesta correcta. Sé muy poco acerca de la teoría de grafos, y menos aún sobre la teoría de Ramsey, pero esto se siente aplicable.
Usted está acampando con sus amigos. Tienes una linterna para cualquier emergencia y han traído a 8 baterías junto con usted. Su hermano llama para decirle que cuatro de las baterías ya están muertos. Su linterna requiere dos baterías para funcionar. ¿Cuál es el menor número de pares que se necesita para poner a prueba para garantizar que usted puede conseguir la linterna?
Tenga en cuenta que la última vez que la carga de trabajo de las pilas en la linterna cuenta como una prueba, incluso si usted ya sabe que la pareja funciona.
Mi solución es la siguiente (spoiler):
La partición de las baterías en cuatro distintos pares. La prueba de cada par. Si ninguna de ellas funciona, genial, eres listo. Si ninguno de ellos el trabajo, usted sabe que cada pareja tiene exactamente una buena batería, y una de las malas de la batería.
Ahora tome dos de los cuatro pares. Prueba de la batería de cada uno de un par con batería de cada uno de los otros pares. I. e., si los pares son $(A,B)$$(C,D)$, luego de la prueba $(A,C)$, $(A,D)$, $(B,C)$, y $(B,D)$. Dado que uno de $A$ $B$ obras, y una de $C$ $D$ trabajo, uno de estos cuatro procesos de trabajo.
Por lo que el número total de pruebas es de ocho, y usted está garantizado para encontrar al menos un par de pilas en buen estado.
Nota: Sisi ha ofrecido una mejor solución en los comentarios que puede hacer en siete pruebas.
Sé que mi solución funciona para encontrar un trabajo par, pero ¿cómo puedo demostrar que no existe una manera de hacerlo en menos intenta (o, si hay una solución mejor, ¿cómo podría usted demostrar que ella es la mejor solución)?
