¿Qué rama de las matemáticas estos tipos de preguntas que caen bajo y lo que sería un buen libro para comenzar a?

Question

Preguntas tales como:

Usted está caminando por una fila de $K$ ($4 \le K \le 25$) luces, algunos de los cuales están en algunos de los cuales están fuera. En esta configuración inicial, no hay ninguna secuencia consecutiva de cuatro luces que están encendidas. Cuando cuatro o más consecutivos luces se encienden, las luces en ese consecutivos bloque se apagará. Usted sólo puede encender las luces que están fuera. ¿Cuál es el número mínimo de luces que usted necesita para encender con el fin de acabar con todos los $K$ luces apagadas?

¿Qué rama hace de este otoño bajo? Lo que sería un buen libro para empezar con el?

Answer 1

Como Qiaochu dijo, puede ser difícil clasificar un problema. Si te gusta los problemas de este sabor, sin embargo, le sugiero que busque un libro sobre la combinatoria. (En particular, usted puede encontrar que usted disfrute de problemas en "combinatoria diseños.")

Me parece "Un Paseo a Través de la Combinatoria" por Miklos Buena para ser inmensamente legible. A pesar de que no cubra los diseños, tiene muchos problemas interesantes que agudizar su combinatoria general de habilidad.

Si desea echar un vistazo a los diseños, a tratar de "Combinatoria Diseños" de W. D. Wallis. Es un poco más avanzado, pero usted puede trabajar a través de él con un poco de paciencia.

Answer 2

Me gustaría provisionalmente la etiqueta de este un problema de optimización combinatoria. Usted tiene un conjunto finito de objetos (el conjunto de posibles condiciones iniciales), y usted está tratando de encontrar uno que maximiza una propiedad determinada (el mínimo número de pasos necesarios para activar las luces apagadas). No estoy seguro de si que le ayudará a encontrar una solución, sin embargo. Mi conjetura es que una solución a este problema se requieren más general del pensamiento abstracto (lo que significa) que las técnicas específicas de determinados campos de las matemáticas.

Algunos pensamientos. Si usted considera que secuencias como

o..o.o..o.o..o. etc.

donde o denota una lámpara que está en y . denota una lámpara que se apaga, no se puede hacer mejor que deshacerse de las lámparas en pares (por encender dos lámparas) o trillizos (girando en tres lámparas). Esto le da un límite inferior de aproximadamente $\frac{2K}{5}$. No tengo una opinión sobre si esta es la óptima.