Problem of the Week #83: Monday March 4th, 2025
As before, these problems are the results of me following my curiosity, and I make no promises regarding the topics, difficulty, solvability of these problems.
Please register for an account if you would like to join the discussion below or share your own problems.
This problem continues from the problem last week.
a). Here are 4 connected lights (where flipping one switch on a light will change the state of itself and its neighbours) in a circle, initially all off. Prove that if we can turn on the top left light by itself, we can achieve any state of the lights.
b). Find, with proof, all k>3 where we can achieve any state of k connected lights in a circle, initially all off.
c). In this network of 3×3 connected lights, initially all off, how many states do we need to check to prove or disprove that we can achieve all possible states of the lights?
d). In this network of 2×3 connected lights, list all achievable states if all lights are initially off.
e). In the previous network of 2×3 connected lights, list all achievable states of only the top left light is initially on.
f). Prove that in any network of connected lights, initially all off, both i) the number of ways to turn on all lights without flipping any switch twice, and ii) the number of states of all lights that are achievable, must be powers of 2.
g). Share your own problem inspired by this one.
h). Give one of these questions to a friend/colleague/student/family member to start a mathematical discussion.