[Buchberger]
Nakano’s Light Puzzle: A Correctness Proof for a Greedy Algorithm
Bruno Buchberger
Technical report no. 26-05 in RISC Report Series, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, Austria. ISSN 2791-4267 (online). RISC Report, May 2026. Licensed under CC BY 4.0 International. [doi] [pdf]@techreport{RISC7250,
author = {Bruno Buchberger},
title = {{Nakano’s Light Puzzle: A Correctness Proof for a Greedy Algorithm}},
language = {english},
abstract = {We consider Nakano’s Problem: Give a (simple and algorithmic) necessary and sufficient conditionfor a configuration of lights (on/off) in a cube to be transformable to the all-off configuration bycertain touches on the faces of the cube. In this paper, we provide a detailed correctness proof for a“greedy” algorithm for Nakano’s problem. With the same proof technique, we also get anotheralgorithmic criterion for Nakano’s problem, which is based on the notion of “parity of box sums”.We discuss the relevance of such proofs for the recent research on automating mathematicalinvention by a combination of Automated Reasoning techniques and Automated Search of Rele-vant Mathematical Literature through Machine Learning.},
number = {26-05},
year = {2026},
month = {May},
howpublished = {RISC Report},
keywords = {Nakano's problem, light puzzle problem, greedy algorithm, correctness proof, automated mathematical invention, canonical simplification, parity lemma, THEOREMA},
length = {58},
license = {CC BY 4.0 International},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Altenberger Straße 69, 4040 Linz, Austria},
issn = {2791-4267 (online)}
}
author = {Bruno Buchberger},
title = {{Nakano’s Light Puzzle: A Correctness Proof for a Greedy Algorithm}},
language = {english},
abstract = {We consider Nakano’s Problem: Give a (simple and algorithmic) necessary and sufficient conditionfor a configuration of lights (on/off) in a cube to be transformable to the all-off configuration bycertain touches on the faces of the cube. In this paper, we provide a detailed correctness proof for a“greedy” algorithm for Nakano’s problem. With the same proof technique, we also get anotheralgorithmic criterion for Nakano’s problem, which is based on the notion of “parity of box sums”.We discuss the relevance of such proofs for the recent research on automating mathematicalinvention by a combination of Automated Reasoning techniques and Automated Search of Rele-vant Mathematical Literature through Machine Learning.},
number = {26-05},
year = {2026},
month = {May},
howpublished = {RISC Report},
keywords = {Nakano's problem, light puzzle problem, greedy algorithm, correctness proof, automated mathematical invention, canonical simplification, parity lemma, THEOREMA},
length = {58},
license = {CC BY 4.0 International},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Altenberger Straße 69, 4040 Linz, Austria},
issn = {2791-4267 (online)}
}
