witzar

My intention was to define repetition (Devil's win) as a repeated state of the lanterns and a repeated position of Devil and Angel, but looks like I failed to do it properly. My apologies.

Evilhubert, your solution is exactly the solution I had in mind, congrats on solving! I'm happy that you found the puzzle enjoyable.

These trivial examples show that for small values of N (the numbers of lanterns) the Angel wins. You seem to be claiming that that the Devil wins for larger values of N, and that all it takes is two OFF lanterns that are not adjacent. So lets analyze the case of three lanterns that are initially OFF, ON, OFF. If the Devil does not switch the 1st lantern ON, then the Angel switches the 2nd lantern OFF, winning immediately after. If the Devil switches the 1st lantern ON, the the Angel does not switch the 2nd lantern, and the Devil cannot switch the 3rd lantern as this would lose immediately. So after the first "pass" the lanterns are in state ON, ON, OFF, and from here the Angel wins by flipping the first two lanterns. But maybe this case is also "trivial and uninteresting", but then what is the smallest N where the Devil can actually win, and what is the initial state?

Let's consider how the game might go for some small numbers of lanterns. If there is only one lantern, then the Angel wins immediately, regardless of it's state. If there are two lanterns, then there are four cases (of initial state of the lanterns): off, off : The Angel wins immediately. on, on : The Angel wins immediately. on, off : The Angel switches the first lantern off, and wins immediately after. off, on : The Devil has a choice what to do with the first lantern. If the Devil switches it on, then he loses immediately after. If the Devil leaves it off, then the Angel switches the second lantern off, and wins immediately after.

Please note the Angel has two ways od winning: 1. Turn all lanterns on. 2. Turn all lanterns off.

In the Garden of Eden, there is a circular pathway, where the Angel and the Devil enjoy an infinite stroll, walking side by side. There are lanterns placed along the pathway (a finite number of them). Each lantern can be in one of two states: on or off. The Angel, a servant of light, has control over the illuminated lanterns. Whenever they pass such a lantern, the Angel decides whether it remains on or off. Conversely, the Devil, a servant of darkness, has control over the lanterns that are dark, and can change their states as they pass.To alleviate their boredom, the Angel and the Devil decide to play a game. The Angel's objective is to bring all the lanterns into complete order, winning immediately if either all lanterns are turned on or all lanterns are turned off. To ensure the game eventually concludes, the celestial beings agree that the game ends if the lanterns return to a previously encountered state. In this case, the Devil is declared the winner. Now, the question is: Who will emerge victorious, and what strategy ensures the win?

There are n binary levers: each lever can be in position 0 or position 1. Exactly one out of 2n possible combinations of levers opens the lock. The lock opens immediately as soon as each lever is in proper position. Changing position of one lever is called a move. Suppose all levers are initially in position 0. What is the minimal number of moves that guarantees opening the lock? In other words: how many moves are required to test each position of levers (the worst case scenario)? Can you also describe the optimal procedure of moving the levers?

Edit:

Well done, gavinksong.