Lights Out em poliedros

Abstract

O jogo solitário Lights Out é um jogo eletrônico jogado por um único jogador em um grid 5x5 em que cada célula contém um botão e uma luz indicadora. Ao pressionarmos um botão deste tabuleiro a luz da célula acionada e de suas células vizinhas trocam de estado, isto é, células acesas apagam-se, enquanto células apagadas se acendem. Considerando que há uma configuração inicial para as células do tabuleiro, isto é, todas as células encontram-se apagas, o objetivo do jogo Lights Out é determinar um conjunto mínimo de células que, ao serem pressionadas, trocam os estados de todas as células do tabuleiro, acendendo-o completamente. O Lights Out pode ser generalizado para tabuleiros de formatos distintos, democraticamente representados por grafos, de modo que as células do tabuleiro são representadas pelos vértices e células adjacentes são representadas pelas arestas do grafo. Investigamos o jogo Lights Out à luz dos poliedros e da teoria de grafos, relacionando assuntos a priori desconectados.