Lanterns of Eden.

[witzar]

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?

[Evilhubert]

OK, let's say that a repeated pattern of lit/unlit lanterns is a win for the devil, regardless of the position of the angel and devil. Let's also say that if the angel and devil make a complete circuit of the path without either of them changing any lanterns, the devil wins (otherwise the angel can just stall indefinitely without ever getting any closer to his goal).

In this scenario, the solution is:

Spoiler

The devil will win for most initial configurations. 

Specifically, the angel will win in one of the below 3 scenarios:

1. There are less than 3 lanterns
2. Initially, all the lanterns are lit except one
3. The lit lanterns are all adjacent to each other without any gaps, AND the players start at the beginning of that stretch of lit lanterns, so the angel can turn them all off before the devil gets a chance to do anything

In all other scenarios the devil will win

To explain the winning strategy, I'll first point out the following:

Spoiler

If there is ever only one lit lantern (and the angel can't turn it off IMMEDIATELY) the devil will win. Imagine lantern #87 is the one that's lit. The devil will turn on #86 only. Then, the angel HAS to turn off #87. If he doesn't, the devil will leave all the other lanterns off until they get to #86 again. Then, if the angel turns #86 off then it's a repeated position. And if he leaves it on then they've gone a complete circuit without anything changing.

So given the angel has to turn off #87, then only #86 will be lit. Then the devil will turn on #85 only. Then the angel will have to turn off #86 and the whole cycle repeats with the location of the lit lantern moving around the path until eventually it gets back to #87

So, to win the game:

Spoiler

The devil can mostly just chill and not do anything, and the angel will be obliged to turn off at least one lit lantern on each circuit, getting ever closer to having only one lit lantern. The only thing the devil needs to worry about is if the lit lanterns are all in an unbroken sequence, as per scenario 3 in the first spoiler.

If this happens, then all the devil needs to do is turn on only the lantern immediately before the sequence of lit lanterns. The angel will then be obliged to turn one or more lanterns off on the next circuit. If he creates any gaps in the sequence, the devil can just go back to not doing anything until the angel has turned off more lanterns till there are no more gaps any more. Then the devil can repeat the process with the new, shorter sequence.

So the only option left for the angel is to turn off one or more lanterns at the end of the sequence. Again, the devil will turn on only the light right before the start of the sequence, and the position of the sequence moves around the path until it approaches the same spot again, similar to what happens if only one lantern is lit. Then the angel's only options will be to create gaps, or else to turn off two lanterns at the end of the sequence, and the devil can repeat the same strategy.

Eventually, the number of lit lanterns will reduce until there is only one left, and the devil will get the win.

 

[EventHorizon]

19 hours ago, Evilhubert said:

OK, let's say that a repeated pattern of lit/unlit lanterns is a win for the devil, regardless of the position of the angel and devil. Let's also say that if the angel and devil make a complete circuit of the path without either of them changing any lanterns, the devil wins (otherwise the angel can just stall indefinitely without ever getting any closer to his goal).

Yeah, that's not a very interesting definition of the state.  Try the one I described. 

On 4/1/2024 at 1:48 PM, EventHorizon said:

(just the lantern configuration looking forward from the pair's position)

So if the angel and devil are approaching lantern 5, the state would be the state of lantern 5, followed by the state of lantern 6,..., ending with the state of lantern 4.

This would be equivalent to cyclically bit shifting the binary number so the next lantern the angel and devil will visit is at the front.

Say there are 5 lanterns: 1 is on, 2 is on, 3 is off, 4 is off, 5 is off.  If the angel and devil are approaching lantern 4, the state is 00110.  This is because looking forward from the pair's position they see off,off,on,on,off.