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]

There's a solution that I find simple and elegant enough to be satisfying

In my explanation, I'm going to think of the lanterns as numbered. The first lantern our celestial beings come to after starting the game will be Lantern 0. The next will be Lantern 1, then L₂, L₃ and so on. The last lantern can be referred to as L_T, with T = Total number of lanterns minus 1. Each time they walk round the lanterns and return to L₀ will be referred to as a circuit.

So who wins?

Spoiler

The angel

So what's the winning stragegy?

Spoiler

First of all, consider the scenario where all the lit lanterns are next to each other, without any gaps (which means that all the unlit lanterns must also be next to each other, without any gaps), AND the angel and devil have just come to the first of the lit lanterns (i.e. first in the direction they are walking in). If this happens then the angel can simply turn off all the lit lanterns, meaning all the lanterns will end up unlit, and the devil won’t have any chance to stop it. If the angel gets a chance to do this, he (obviously) should.

But other than the above specific scenario, the angel just follows a simple rule – on each circuit, turn off all lit lanterns until the devil turns an unlit lantern on. After that, don’t turn any more lanterns off for the rest of the circuit. If the devil turns a lantern on before the angel has turned any off, then the angel should just do nothing on that circuit.

And that’s it. There are some tweaks the angel can make to achieve victory more quickly, but this simple approach will still guarantee the win eventually.

But how can we prove the strategy will always work for any number of lanterns?

Spoiler

You can think of each lantern as a binary digit, with lit lanterns being 1s and unlit ones being 0s. By combining all the digits together, beginning with L 000 and going up to L TTT, we can create a binary number. Let’s call it the Eden Value, or EV. If the angel follows his strategy the EV will increase with every circuit, until either it eventually it reaches EQUATION which is the maximum value the EV can reach when all lanterns are lit, or else the angel will get a chance to turna all the lanterns off somewhere along the way.

So how do we know the EV will increase with each circuit? Well, in the case where the devil turns a lantern on before the angel has turned any off, it’s simple. The angel won’t turn any lanterns off that circuit, so all the lanterns that were previously lit will remain lit, plus the one (or more) that the devil turned on will now be lit as well, so the EV has clearly increased.

But what if the devil doesn’t turn any lamps on until the angel has turned one (or more) off? Remember that if the angel follows his strategy, the devil has to turn on at least one lamp each circuit, otherwise they will all be turned off and the angel will win. Also think about the values of successive binary digits – 1, 2, 4, 8, 16 and so on. The value of each digit is always one more than the sum of all the preceding digits. So if the devil turns a lantern on after the angel has already turned some off, the value of the lantern that was turned on will always be greater than the combined values of all the lanterns that were turned off, no matter how many of them there were. So again, the EV is guaranteed to increase.

So there you have it. I have a hunch that this isn’t the only way to arrive at the solution, and if anyone has a neat little recursive proof I’d love to see it.

I just want to give a big thank you to witzar for posting the problem - I really enjoyed this one!

[phil1882]

this game seems to be impossible for the angel to win. if 50% or more lanterns are dark, the devil flips a dark lantern. otherwise, leave it alone.

 

[harey]

Spoiler

I assume that if they make a turn without changing the state of any lantern. a "previously encountered state" occurs (otherwise, they could walk around endlessly).

Strategy for the devil: turn on the lanterns the angel switched off.

The angel must turn off a subset of the set of the lit lanterns (and not all subsets are suitable). As the possibilities are finite, the angel cannot avoid a repetition.

In some rare cases, the angel wins, i.e.: (off) on on on.

 

Edited January 28 by harey

[k-man]

Spoiler

Here are my thoughts...

How can the Angel win? Since the Angel can only turn the lanterns OFF then the only way for him to win is to get all the lanterns to be OFF. He can never win with all lanterns being ON because that would require help from the Devil to turn ON the final lantern and we can't count on that.

So, the last winning move by the Angel must be to turn OFF the final lantern. How does the angel get to the scenario when all the lanterns are OFF except one? The previous lantern must have been also ON and the Angel must turn it OFF. Because if the previous lantern was already OFF then the Devil would see that he is about to lose and he would turn it ON! The same reasoning follows for the lantern before that and so on... So, for the Angel to win there must be all three conditions:

1. a continuous sequence of lit lanterns that he can turn off
2. all the other lanterns must be already off
3. they must be in front of the first lit lantern in that sequence

So, the Devil's strategy is to prevent this from happening and it's easy to do. All the Devil needs to do is to ensure that there is always at least 2 lit lanterns and not next to each other. If they go through a lit sequence and the Angel turns them all off just turn on the next lantern and continue to the next lit sequence. If the next sequence got turned off by the Angel then again just turn on the following lantern. This can continue for a while, but since the number of states is finite the Devil will eventually win.

 

[witzar]

Please note the Angel has two ways od winning:

1. Turn all lanterns on.

2. Turn all lanterns off.

[witzar]

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.

 

 

Edited February 8 by witzar

[k-man]

1 hour ago, witzar said:

Please note the Angel has two ways od winning:

1. Turn all lanterns on.

2. Turn all lanterns off.

Since the Angel cannot turn ON a lantern that is currently OFF (only the Devil can do that), as long as there is at least one lantern in the OFF state from the beginning, the Angle cannot win by having all lanterns ON. This would require the Devil to turn ON the final lantern that will deliver the win to the Angel. Assuming the Devil wants to win, this will never happen, so the only way the Angel can win in practice is when all the lanterns are OFF. 

 

58 minutes ago, witzar said:

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.

 

 

These are some trivial and uninteresting examples and I'm not sure how they help.

[witzar]

3 hours ago, k-man said:

These are some trivial and uninteresting examples and I'm not sure how they help.

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?

[EventHorizon]

Edit: Oops.  I guess switch to 1 meaning off and 0 meaning on to match the story.

Who wins?

Spoiler

The angel will win.

Ugly Strategy with not much intuition as to how/why it works.  (Obviously, I don't consider this as the answer...)

Spoiler

Find the current configuration (looking ahead from where the pair are) in the following string of lanterns (1-on 0-off), and make the lantern match the lantern just to the right past where the current configuration was found.

11111111111011111011111101111011111110111011101111111101101110111101101111011101101111101101101101111111110101101111110101110111110101111011110101111101110101101101110101110101111110110101101110110101110110110101111010110101111111010101101111010101110111010101111011010101101011010101111101010101101101010101110101010101011111111110010111111110011011111110011101111110010101111110011110111110010110111110011010111110011111011110010111011110011011011110011101011110010101011110011110011111101110010111101110011011101110011101101110010101101110011110101110010110101110011010101110011111001110010111001110011111110110010111110110011011110110011101110110010101110110011110110110010110110110011010110110011100110110011111010110010111010110011011010110011101010110010101010110011110010110010110011111100110010111100110011011100110011101100110010101100110011001111111101001011111101001101111101001110111101001010111101001100111101001111011101001011011101001101011101001110011101001111101101001011101101001101101101001110101101001010101101001100101101001111001101001011001101001101001111110101001011110101001101110101001110110101001010110101001100110101001111010101001011010101001101010101001110010101001111100101001011100101001101100101001110100101001010100101001111111001001011111001001101111001001110111001001010111001001100111001001111011001001011011001001101011001001110011001001010011001001111101001001011101001001101101001001110101001001010101001001100101001001111001001001011001001001101001001001001111111110001011111110001101111110001001111110001110111110001010111110001100111110001111011110001011011110001101011110001001011110001110011110001010011110001111101110001011101110001101101110001001101110001110101110001010101110001100101110001111001110001011001110001101001110001001001110001110001111110110001011110110001101110110001001110110001110110110001010110110001100110110001111010110001011010110001101010110001001010110001110010110001010010110001111100110001011100110001101100110001001100110001110100110001010100110001100100110001111000110001011000110001111111010001011111010001101111010001001111010001110111010001010111010001100111010001111011010001011011010001101011010001001011010001110011010001010011010001100011010001111101010001011101010001101101010001001101010001110101010001010101010001100101010001111001010001011001010001101001010001001001010001110001010001010001111110010001011110010001101110010001001110010001110110010001010110010001100110010001111010010001011010010001101010010001001010010001110010010001010010010001100010010001111100010001011100010001101100010001001100010001110100010001010100010001100100010001000111111110000101111110000110111110000100111110000111011110000101011110000110011110000100011110000111101110000101101110000110101110000100101110000111001110000101001110000110001110000111110110000101110110000110110110000100110110000111010110000101010110000110010110000100010110000111100110000101100110000110100110000100100110000111000110000101000110000110000111111010000101111010000110111010000100111010000111011010000101011010000110011010000100011010000111101010000101101010000110101010000100101010000111001010000101001010000110001010000111110010000101110010000110110010000100110010000111010010000101010010000110010010000100010010000111100010000101100010000110100010000100100010000111000010000101000010000111111100000101111100000110111100000100111100000111011100000101011100000110011100000100011100000111101100000101101100000110101100000100101100000111001100000101001100000110001100000100001100000111110100000101110100000110110100000100110100000111010100000101010100000110010100000100010100000111100100000101100100000110100100000100100100000111000100000101000100000110000100000100000111111000000101111000000110111000000100111000000111011000000101011000000110011000000100011000000111101000000101101000000110101000000100101000000111001000000101001000000110001000000100001000000111110000000101110000000110110000000100110000000111010000000101010000000110010000000100010000000111100000000101100000000110100000000100100000000111000000000101000000000110000000000100000000000111111111111

Yeah, it's a cool shifting grey code.  I haven't quite figured it out yet.

Yay code

Spoiler

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <memory.h>

using namespace std;

int move(int conf, int setvalue);
void printconf(int conf);

int lanterns;
int movemask;
int lastspot;

int main(int argc, char *argv[])
{    
    if (argc >= 2) lanterns = atoi(argv[1]);
    else {cout << "Need number of lanterns to use." << endl; return 0;}
    
    if ((lanterns < 2) || (lanterns > 20)) {cout << "Lantern number must be between 2 and 20."; return 0;}
    movemask = (1 << lanterns)-1;
    lastspot = 1 << (lanterns-1);
    
    int *bestchoice = new int[1 << lanterns];
    int **next = new int*[2];
    next[0] = new int[1 << lanterns];
    next[1] = new int[1 << lanterns];
    int *winstates = new int[1 << lanterns];
    int *stepstowin = new int[1 << lanterns];
    
    //initialize
    for(int i = 0; i < (1<<lanterns); i++) {bestchoice[i] = -1; winstates[i] = 0; next[0][i] = move(i,0); next[1][i] = move(i,1); stepstowin[i] = -1;}
    winstates[0] = 1;
    winstates[movemask] = 1;
    stepstowin[0] = 0;
    stepstowin[movemask] = 0;
    
    
    
    //fixed point algorithm
    while(true)
    {
        int changed = 0;
        for(int i = 0; i < (1<<lanterns); i++)
        {
            if (winstates[i]) continue;
            if (i%2)
            {//devil's choice
                //if both choices results in win states for angel, mark as win state for angel
                if (winstates[next[0][i]] && winstates[next[1][i]])
                {
                    changed=1; winstates[i]=1;
                    if (stepstowin[next[0][i]] < stepstowin[next[1][i]]) stepstowin[i] = stepstowin[next[1][i]]+1;
                    else stepstowin[i] = stepstowin[next[0][i]]+1;
                }
            }
            else
            {//angel's choice
                if (winstates[next[0][i]]){changed=1; bestchoice[i]=0; winstates[i]=1; stepstowin[i]=stepstowin[next[0][i]]+1;}
                if (winstates[next[1][i]]){changed=1; bestchoice[i]=1; winstates[i]=1; stepstowin[i]=stepstowin[next[1][i]]+1;}
            }
        }
        
        
        int all = 1;
        for(int i = 0; i < (1<<lanterns); i++) all &= winstates[i];
        
        //print status
        if (all) // (true)
        {
            cout << endl << endl;
            for(int i = 0; i < (1<<lanterns); i++)
            {
                cout << winstates[i] << " "; printconf(i); cout << " | "; printconf(next[0][i]);
                if (i%2) {cout << " D";} else {cout << " A";}
                if (bestchoice[i]==-1) cout << "? ";
                if (bestchoice[i]==0) cout << "< ";
                if (bestchoice[i]==1) cout << "> ";            
                printconf(next[1][i]);
                cout << " | " << stepstowin[i];
                if (i%2)
                {
                    cout << "    | " << stepstowin[next[0][i]] << " " << stepstowin[next[1][i]];
                }
                cout << endl;
            }
        }
        
        if (all) {cout << "All states are win states for the angel." << endl; break;}
        
        if (changed == 0)
        {
            break;
        }
    }
    
    
    //print configurations in order of steps to win
    cout << endl;
    for(int j = movemask-1; j >= 0; j--)
    {
        for(int i = 1; i < (1<<lanterns); i++) //started at 1 to skip all lanterns off configuration
            if (stepstowin[i] == j)
            {
                printconf(i);
                cout << "    " << j << "    " << i << endl;
            }
    }
    
    //print full shifting grey code
    cout << endl;
    for(int j = movemask-1; j >= 0; j--)
    {
        for(int i = 1; i < (1<<lanterns)-1; i++) //started at 1 to skip all lanterns off configuration
            if (stepstowin[i] == j)
            {
                cout << (i%2);
            }
    }
    printconf(movemask);
    cout << endl;
    
    
    
    
    delete[] next[0];
    delete[] next[1];
    delete[] next;
    delete[] winstates;
    delete[] bestchoice;
    delete[] stepstowin;
    
    return 0;
}

int move(int conf, int setvalue)
{
    return ((conf >> 1) + (setvalue * lastspot)) & movemask;
}

void printconf(int conf)
{
    for(int j = 0; j < lanterns; j++)
    {
        if (conf & (1<<j)) cout << "1";
        else cout << "0";
    }
}

Code output for 4 lanterns

Spoiler

1 0000 | 0000 A? 0001 | 0
1 1000 | 0000 D? 0001 | 4    | 0 3
1 0100 | 1000 A< 1001 | 5
1 1100 | 1000 D? 1001 | 8    | 4 7
1 0010 | 0100 A< 0101 | 6
1 1010 | 0100 D? 0101 | 12    | 5 11
1 0110 | 1100 A< 1101 | 9
1 1110 | 1100 D? 1101 | 14    | 8 13
1 0001 | 0010 A> 0011 | 3
1 1001 | 0010 D? 0011 | 7    | 6 2
1 0101 | 1010 A> 1011 | 11
1 1101 | 1010 D? 1011 | 13    | 12 10
1 0011 | 0110 A> 0111 | 2
1 1011 | 0110 D? 0111 | 10    | 9 1
1 0111 | 1110 A> 1111 | 1
1 1111 | 1110 D? 1111 | 0    | 14 0
All states are win states for the angel.

1110    14    7
1101    13    11
1010    12    5
0101    11    10
1011    10    13
0110    9    6
1100    8    3
1001    7    9
0010    6    4
0100    5    2
1000    4    1
0001    3    8
0011    2    12
0111    1    14
1111    0    15

111010110010001111

5 lanterns

Spoiler

1 00000 | 00000 A? 00001 | 0
1 10000 | 00000 D? 00001 | 5    | 0 4
1 01000 | 10000 A< 10001 | 6
1 11000 | 10000 D? 10001 | 10    | 5 9
1 00100 | 01000 A< 01001 | 7
1 10100 | 01000 D? 01001 | 15    | 6 14
1 01100 | 11000 A< 11001 | 11
1 11100 | 11000 D? 11001 | 20    | 10 19
1 00010 | 00100 A< 00101 | 8
1 10010 | 00100 D? 00101 | 18    | 7 17
1 01010 | 10100 A< 10101 | 16
1 11010 | 10100 D? 10101 | 25    | 15 24
1 00110 | 01100 A< 01101 | 12
1 10110 | 01100 D? 01101 | 27    | 11 26
1 01110 | 11100 A< 11101 | 21
1 11110 | 11100 D? 11101 | 30    | 20 29
1 00001 | 00010 A> 00011 | 4
1 10001 | 00010 D? 00011 | 9    | 8 3
1 01001 | 10010 A> 10011 | 14
1 11001 | 10010 D? 10011 | 19    | 18 13
1 00101 | 01010 A< 01011 | 17
1 10101 | 01010 D? 01011 | 24    | 16 23
1 01101 | 11010 A< 11011 | 26
1 11101 | 11010 D? 11011 | 29    | 25 28
1 00011 | 00110 A> 00111 | 3
1 10011 | 00110 D? 00111 | 13    | 12 2
1 01011 | 10110 A> 10111 | 23
1 11011 | 10110 D? 10111 | 28    | 27 22
1 00111 | 01110 A> 01111 | 2
1 10111 | 01110 D? 01111 | 22    | 21 1
1 01111 | 11110 A> 11111 | 1
1 11111 | 11110 D? 11111 | 0    | 30 0
All states are win states for the angel.

11110    30    15
11101    29    23
11011    28    27
10110    27    13
01101    26    22
11010    25    11
10101    24    21
01011    23    26
10111    22    29
01110    21    14
11100    20    7
11001    19    19
10010    18    9
00101    17    20
01010    16    10
10100    15    5
01001    14    18
10011    13    25
00110    12    12
01100    11    6
11000    10    3
10001    9    17
00010    8    8
00100    7    4
01000    6    2
10000    5    1
00001    4    16
00011    3    24
00111    2    28
01111    1    30
11111    0    31

11110110101110010100110001000011111

6 lanterns

Spoiler

1 000000 | 000000 A? 000001 | 0
1 100000 | 000000 D? 000001 | 6    | 0 5
1 010000 | 100000 A< 100001 | 7
1 110000 | 100000 D? 100001 | 12    | 6 11
1 001000 | 010000 A< 010001 | 8
1 101000 | 010000 D? 010001 | 18    | 7 17
1 011000 | 110000 A< 110001 | 13
1 111000 | 110000 D? 110001 | 24    | 12 23
1 000100 | 001000 A< 001001 | 9
1 100100 | 001000 D? 001001 | 30    | 8 29
1 010100 | 101000 A< 101001 | 19
1 110100 | 101000 D? 101001 | 33    | 18 32
1 001100 | 011000 A< 011001 | 14
1 101100 | 011000 D? 011001 | 39    | 13 38
1 011100 | 111000 A< 111001 | 25
1 111100 | 111000 D? 111001 | 45    | 24 44
1 000010 | 000100 A< 000101 | 10
1 100010 | 000100 D? 000101 | 22    | 9 21
1 010010 | 100100 A< 100101 | 31
1 110010 | 100100 D? 100101 | 43    | 30 42
1 001010 | 010100 A< 010101 | 20
1 101010 | 010100 D? 010101 | 51    | 19 50
1 011010 | 110100 A< 110101 | 34
1 111010 | 110100 D? 110101 | 53    | 33 52
1 000110 | 001100 A< 001101 | 15
1 100110 | 001100 D? 001101 | 36    | 14 35
1 010110 | 101100 A< 101101 | 40
1 110110 | 101100 D? 101101 | 59    | 39 58
1 001110 | 011100 A< 011101 | 26
1 101110 | 011100 D? 011101 | 55    | 25 54
1 011110 | 111100 A< 111101 | 46
1 111110 | 111100 D? 111101 | 62    | 45 61
1 000001 | 000010 A> 000011 | 5
1 100001 | 000010 D? 000011 | 11    | 10 4
1 010001 | 100010 A> 100011 | 17
1 110001 | 100010 D? 100011 | 23    | 22 16
1 001001 | 010010 A> 010011 | 29
1 101001 | 010010 D? 010011 | 32    | 31 28
1 011001 | 110010 A> 110011 | 38
1 111001 | 110010 D? 110011 | 44    | 43 37
1 000101 | 001010 A< 001011 | 21
1 100101 | 001010 D? 001011 | 42    | 20 41
1 010101 | 101010 A> 101011 | 50
1 110101 | 101010 D? 101011 | 52    | 51 49
1 001101 | 011010 A< 011011 | 35
1 101101 | 011010 D? 011011 | 58    | 34 57
1 011101 | 111010 A< 111011 | 54
1 111101 | 111010 D? 111011 | 61    | 53 60
1 000011 | 000110 A> 000111 | 4
1 100011 | 000110 D? 000111 | 16    | 15 3
1 010011 | 100110 A> 100111 | 28
1 110011 | 100110 D? 100111 | 37    | 36 27
1 001011 | 010110 A< 010111 | 41
1 101011 | 010110 D? 010111 | 49    | 40 48
1 011011 | 110110 A> 110111 | 57
1 111011 | 110110 D? 110111 | 60    | 59 56
1 000111 | 001110 A> 001111 | 3
1 100111 | 001110 D? 001111 | 27    | 26 2
1 010111 | 101110 A> 101111 | 48
1 110111 | 101110 D? 101111 | 56    | 55 47
1 001111 | 011110 A> 011111 | 2
1 101111 | 011110 D? 011111 | 47    | 46 1
1 011111 | 111110 A> 111111 | 1
1 111111 | 111110 D? 111111 | 0    | 62 0
All states are win states for the angel.

111110    62    31
111101    61    47
111011    60    55
110110    59    27
101101    58    45
011011    57    54
110111    56    59
101110    55    29
011101    54    46
111010    53    23
110101    52    43
101010    51    21
010101    50    42
101011    49    53
010111    48    58
101111    47    61
011110    46    30
111100    45    15
111001    44    39
110010    43    19
100101    42    41
001011    41    52
010110    40    26
101100    39    13
011001    38    38
110011    37    51
100110    36    25
001101    35    44
011010    34    22
110100    33    11
101001    32    37
010010    31    18
100100    30    9
001001    29    36
010011    28    50
100111    27    57
001110    26    28
011100    25    14
111000    24    7
110001    23    35
100010    22    17
000101    21    40
001010    20    20
010100    19    10
101000    18    5
010001    17    34
100011    16    49
000110    15    24
001100    14    12
011000    13    6
110000    12    3
100001    11    33
000010    10    16
000100    9    8
001000    8    4
010000    7    2
100000    6    1
000001    5    32
000011    4    48
000111    3    56
001111    2    60
011111    1    62
111111    0    63

11111011011101010111100101100110100100111000101000110000100000111111

 

[EventHorizon]

On the "ugly strategy"

Spoiler

I guess I knew why it works.  The grey code is ordered such that both moves the devil can make result in configurations further in the grey code (one moving one space forward, the other further).  This was ensured by how I used the fixed point algorithm.  What I don't know it is why such an ordering exists, how to explain it simply, and an easy way to know what move to make without searching through binary vomit.

Edit: Another consequence is, for the angel, one move is one further in the grey code and the other move is back somewhere.  So one wrong move and the devil wins.

 

[EventHorizon]

sorted configurations with 6 lanterns (and added devil best choices I omitted before)

Spoiler

1 111110 | 111100 D> 111101 | 62    | 45 61
1 111101 | 111010 D> 111011 | 61    | 53 60
1 111011 | 110110 D< 110111 | 60    | 59 56
1 110110 | 101100 D> 101101 | 59    | 39 58
1 101101 | 011010 D> 011011 | 58    | 34 57
1 011011 | 110110 A> 110111 | 57
1 110111 | 101110 D< 101111 | 56    | 55 47
1 101110 | 011100 D> 011101 | 55    | 25 54
1 011101 | 111010 A< 111011 | 54
1 111010 | 110100 D> 110101 | 53    | 33 52
1 110101 | 101010 D< 101011 | 52    | 51 49
1 101010 | 010100 D> 010101 | 51    | 19 50
1 010101 | 101010 A> 101011 | 50
1 101011 | 010110 D> 010111 | 49    | 40 48
1 010111 | 101110 A> 101111 | 48
1 101111 | 011110 D< 011111 | 47    | 46 1
1 011110 | 111100 A< 111101 | 46
1 111100 | 111000 D> 111001 | 45    | 24 44
1 111001 | 110010 D< 110011 | 44    | 43 37
1 110010 | 100100 D> 100101 | 43    | 30 42
1 100101 | 001010 D> 001011 | 42    | 20 41
1 001011 | 010110 A< 010111 | 41
1 010110 | 101100 A< 101101 | 40
1 101100 | 011000 D> 011001 | 39    | 13 38
1 011001 | 110010 A> 110011 | 38
1 110011 | 100110 D< 100111 | 37    | 36 27
1 100110 | 001100 D> 001101 | 36    | 14 35
1 001101 | 011010 A< 011011 | 35
1 011010 | 110100 A< 110101 | 34
1 110100 | 101000 D> 101001 | 33    | 18 32
1 101001 | 010010 D< 010011 | 32    | 31 28
1 010010 | 100100 A< 100101 | 31
1 100100 | 001000 D> 001001 | 30    | 8 29
1 001001 | 010010 A> 010011 | 29
1 010011 | 100110 A> 100111 | 28
1 100111 | 001110 D< 001111 | 27    | 26 2
1 001110 | 011100 A< 011101 | 26
1 011100 | 111000 A< 111001 | 25
1 111000 | 110000 D> 110001 | 24    | 12 23
1 110001 | 100010 D< 100011 | 23    | 22 16
1 100010 | 000100 D> 000101 | 22    | 9 21
1 000101 | 001010 A< 001011 | 21
1 001010 | 010100 A< 010101 | 20
1 010100 | 101000 A< 101001 | 19
1 101000 | 010000 D> 010001 | 18    | 7 17
1 010001 | 100010 A> 100011 | 17
1 100011 | 000110 D< 000111 | 16    | 15 3
1 000110 | 001100 A< 001101 | 15
1 001100 | 011000 A< 011001 | 14
1 011000 | 110000 A< 110001 | 13
1 110000 | 100000 D> 100001 | 12    | 6 11
1 100001 | 000010 D< 000011 | 11    | 10 4
1 000010 | 000100 A< 000101 | 10
1 000100 | 001000 A< 001001 | 9
1 001000 | 010000 A< 010001 | 8
1 010000 | 100000 A< 100001 | 7
1 100000 | 000000 D> 000001 | 6    | 0 5
1 000001 | 000010 A> 000011 | 5
1 000011 | 000110 A> 000111 | 4
1 000111 | 001110 A> 001111 | 3
1 001111 | 011110 A> 011111 | 2
1 011111 | 111110 A> 111111 | 1
1 111111 | 111110 D? 111111 | 0    | 62 0

5 lanterns

Spoiler

1 11110 | 11100 D> 11101 | 30    | 20 29
1 11101 | 11010 D> 11011 | 29    | 25 28
1 11011 | 10110 D< 10111 | 28    | 27 22
1 10110 | 01100 D> 01101 | 27    | 11 26
1 01101 | 11010 A< 11011 | 26
1 11010 | 10100 D> 10101 | 25    | 15 24
1 10101 | 01010 D> 01011 | 24    | 16 23
1 01011 | 10110 A> 10111 | 23
1 10111 | 01110 D< 01111 | 22    | 21 1
1 01110 | 11100 A< 11101 | 21
1 11100 | 11000 D> 11001 | 20    | 10 19
1 11001 | 10010 D< 10011 | 19    | 18 13
1 10010 | 00100 D> 00101 | 18    | 7 17
1 00101 | 01010 A< 01011 | 17
1 01010 | 10100 A< 10101 | 16
1 10100 | 01000 D> 01001 | 15    | 6 14
1 01001 | 10010 A> 10011 | 14
1 10011 | 00110 D< 00111 | 13    | 12 2
1 00110 | 01100 A< 01101 | 12
1 01100 | 11000 A< 11001 | 11
1 11000 | 10000 D> 10001 | 10    | 5 9
1 10001 | 00010 D< 00011 | 9    | 8 3
1 00010 | 00100 A< 00101 | 8
1 00100 | 01000 A< 01001 | 7
1 01000 | 10000 A< 10001 | 6
1 10000 | 00000 D> 00001 | 5    | 0 4
1 00001 | 00010 A> 00011 | 4
1 00011 | 00110 A> 00111 | 3
1 00111 | 01110 A> 01111 | 2
1 01111 | 11110 A> 11111 | 1
1 11111 | 11110 D? 11111 | 0    | 30 0

4 lanterns

Spoiler

1 1110 | 1100 D> 1101 | 14    | 8 13
1 1101 | 1010 D< 1011 | 13    | 12 10
1 1010 | 0100 D> 0101 | 12    | 5 11
1 0101 | 1010 A> 1011 | 11
1 1011 | 0110 D< 0111 | 10    | 9 1
1 0110 | 1100 A< 1101 | 9
1 1100 | 1000 D> 1001 | 8    | 4 7
1 1001 | 0010 D< 0011 | 7    | 6 2
1 0010 | 0100 A< 0101 | 6
1 0100 | 1000 A< 1001 | 5
1 1000 | 0000 D> 0001 | 4    | 0 3
1 0001 | 0010 A> 0011 | 3
1 0011 | 0110 A> 0111 | 2
1 0111 | 1110 A> 1111 | 1
1 1111 | 1110 D? 1111 | 0    | 14 0

3 lanterns

Spoiler

1 110 | 100 D> 101 | 6    | 3 5
1 101 | 010 D< 011 | 5    | 4 1
1 010 | 100 A< 101 | 4
1 100 | 000 D> 001 | 3    | 0 2
1 001 | 010 A> 011 | 2
1 011 | 110 A> 111 | 1
1 111 | 110 D? 111 | 0    | 6 0

Edit: Another thing of note.  The devil and angel both choose between the same 2 options once each (except the choice between 000...00 and 000...01 for angel and 111...10 and 111...11 for devil, due to angel win conditions).

[EventHorizon]

recreating the results of the code...

Spoiler

We work backwards.  If you haven't seen the configuration of lanterns (excluding the furthest one), then it must be the angel's choice... because if it was the devil's choice he would have chosen the other choice to avoid helping the angel.  If we have seen the configuration before, then it must have been the devil's choice this time... otherwise the angel would have chosen something better.

I'll show this with 4 lanterns.

The final result is off,off,off,off.  I'll represent this by 0000... opposite of the code.  I wrote the code after misremembering the story as the angel goes around with the power to light lanterns and the devil to extinguish.

(000)0 - We haven't seen 000 before, so must have been the angel's choice, so prepend a 1.

(100)00 - new conf, angel's choice, add 1.

(110)000 - new conf, angel's choice, add 1.

(111)0000 - new conf, but since 1111 would have been a win state it's the devil's choice, add 0.

(011)10000 - new conf, angel's choice, add 1.

(101)110000 - new conf, angel's choice, add 1.

(110)1110000 - seen before, devil's choice, add 0.

(011)01110000 - seen before, devil's choice, add 0.

(001)101110000 - new conf, angel's choice, add 1.

(100)1101110000 - seen before, devil's choice, add 0.

(010)01101110000 - new conf, angel's choice, add 1.

(101)001101110000 - seen before, devil's choice, add 0.

(010)1001101110000 - seen before, devil's choice, add 0.

(001)01001101110000 - seen before, devil's choice, add 0.

(000)101001101110000 - seen before, but 0000 is a win state so cannot continue.

It just happens that 000101001101110000 covers all lantern configurations (except 1111, which is a win state anyway).

So, we just need to prove this happens for any number of lanterns.  An easy way to determine the angel's choice would be nice too.

 

[harey]

Spoiler

As I am a nice guy, I let you the role of the angel.

Let's start with one lantern lit, i.e. 33.

Situation 1: 33
Before you turn 33 off, I have to light a lantern:

Situation 2: 13 33 (we are in 13)
As I shall not light more lanterns, you have to turn off:
a) 13 in next turn -> situation 1
b) 33 in this turn or the next one

Situation 3: 13 (we are in 33)
Before you turn 13 off, I have to light a lantern:

Situation 4: 13 43 (we are in 43)
You have to turn off:
a) 43 the in next turn -> situation 3
b) 13 in the next turn

Situation 5: 43 (we are in 13)
I light 33.

Situation 6: 33 43 (we are in 33)
a) If you turn of 43, in the next turn, I light 13-> Situation 2
b) You must wait; I light 13.

Situation 7: 13 33 43 (we are in 13)
You turn off:
a) 13-> Situation 6
b) 33-> Situation 4
c) 43-> Situation 2

Two lanterns:
I let you switch of one lantern and we are in the case of one lantern. Recursion...

 

[EventHorizon]

I couldn't follow that, harey.

Spoiler

Since you use some numbers >32, I assume there are 6 lanterns.

I couldn't find a 33 that has one lantern lit from my code output.

"110100    33    11" <-- This state is 33 steps from the angel winning in my code, it has 3 on and 3 off.

"100001    11    33" <-- Internal representation is 33, 4 lanterns are lit since 0 means on due to misremembering the story.

 

14 hours ago, harey said:

Before you turn 33 off, I have to light a lantern:

I don't know how I'd turn a configuration off, so 33 refers to a single lantern?

14 hours ago, harey said:

b) 33 in this turn or the next one

I don't know how to interpret this.  Turn off 33 in two different possible turns?

 

Clearly I am very confused.  Could you rewrite your post with the string of lanterns shown each step?  You could either use 1 as on (makes sense) or 1 as off (like my code due to my misremembering the story).  Or like you did before ("(off) on on on")

Or perhaps just explain in more detail?

 

[harey]

@EventHorizonMy post is unrelated to yours.

The number of lamps is not important, just a little bit more that those I quote.

"Let's start with one lantern lit, i.e. 33.":

This is not a binary number, it is the 33rd lantern assuming the starting position is the 1st lantern (conveniently chosen), following the lantern 32 and followed by the lantern 34.

[EventHorizon]

First, let's nail down the definition of configuration so we know exactly when the devil wins.

It cannot simply be the state of the lanterns, since not changing a lantern on a given step would then repeat the configuration.

So the location of the devil and angel need to be part of it.  There are two ways I see of incorporating this.

1. Include which lantern number the devil and angel are at and the string of lantern states.  Which could be notated by a location marked in a string of lantern states (e.g., "01101;001") or a number and the string (6,01101001).
2. The lantern numbers don't matter, just look forward from the lantern the angel and devil are at (e.g., ";00101101").  And then you don't need the location marker ";" because it is always at the front.

Option 1 has more states, lanterns x 2^lanterns compared to just 2^lanterns.  Let's choose option 2 since less states means more of a chance of repeat and gives the devil a better chance.  That is the notation I used for my code.

On 1/28/2024 at 4:35 PM, harey said:

I assume that if they make a turn without changing the state of any lantern. a "previously encountered state" occurs (otherwise, they could walk around endlessly).

I notice that you use the word "turn" to sometimes mean one whole stroll around all the lanterns.  That is something that threw me off a little.  I'd call that a revolution or a full rotation.

Alright, time to put the devil in his place.

Spoiler

So given your situations, going back to a situation doesn't take into account the location of the angel and devil.  This is actually very important since the angel's first goal is to make the devil have two lit lanterns closer and closer.  Once they are together they act simply as one as far as the devil is concerned.  Then you need to light another, which the angel makes you move closer to the pair of lit lanterns, etc.

Lets see how this works.  After you have lit a second lantern, being the angel, I look at which segment of the circle has less distance between the two lit lanterns.  I turn off the lantern at the beginning of that segment.  This means you either turn on the next one after that, leaving a segment with one less lantern, or wait and leave an even smaller distance to the remaining lit lantern.  Obviously, you need to light one before letting me turn that one off or I would win.

Here's an example from my code's 6 lantern output:

111110 <one lit lantern (interpret 0 as "on" and 1 as "off")
111101 <one lit lantern
111011 <one lit lantern
110110
101101
011011
110111 <back to one lit lantern, but it is 1 lantern closer than the last time.
101110 <devil lit the next one

In this way the angel forces the devil to light lanterns closer together until they are right next to each other.  A process which is then repeated, without the need to find which segment is shorter... since the pair together make the configuration unique.  So just move the new one around until it meets the pair of lit lanterns.

It looks like there are other tricks the devil pulls, but as my code showed the configurations can be ordered in such a way that the devil's choice is always between one step forward and many steps forward towards the angel's eventual winning state.

 

[EventHorizon]

And by "put the devil in his place", I didn't mean you @harey.  I reread that and remembered you said "As I am a nice guy, I let you the role of the angel."  So if you found that belittling, I apologize, as that was not my intent.  I am sure you see things I don't and vice-versa.

[harey]

Here's an example from my code's 6 lantern output:

111110 <one lit lantern (interpret 0 as "on" and 1 as "off")
111101 <one lit lantern

You suppose the devil turns the lantern 5 on. But what if he turns the lantern 4 and not 5 on?

111110 <one lit lantern (interpret 0 as "on" and 1 as "off")
111010 your turn

 

P.S. I am not touchy (did not even think it could be interpreted this way), but I think things over. In the last time, I wrote a lot of nonsense, i.e. my first answer.

[EventHorizon]

34 minutes ago, harey said:

P.S. I am not touchy (did not even think it could be interpreted this way), but I think things over. In the last time, I wrote a lot of nonsense, i.e. my first answer.

Good.  Yeah, I overthink everything and can get rather paranoid.

37 minutes ago, harey said:

You suppose the devil turns the lantern 5 on. But what if he turns the lantern 4 and not 5 on?

111110 <one lit lantern (interpret 0 as "on" and 1 as "off")
111010 your turn

Spoiler

The bit on the left is the lantern the angel and devil are currently at.  Numbering lanterns doesn't quite work well with the configuration continually rotating.  Assuming the devil doesn't light any more lanterns until the angel extinguishes one, it would go like this.

111110 (Initial configuration) Devil's choice since they are at an off lantern (leftmost bit).  The devil doesn't light the lantern.
111101 Devil's choice and he lights the lantern (the rightmost 0 on the next line).
111010 Devil's choice and leaves it off.  (Is this the situation you intended?)
110101 Devil's choice and leaves it off.  (I believe the Devil lights this lantern in my code's output. 110101 -> 101010)
101011 Devil's choice and leaves it off.
010111 Angel's choice and extinguishes it.  Back to 1 lit lantern.
101111 Devil's choice and if he doesn't light it the angel will extinguish the last lit lantern on the next step.
011110 Angel's choice and leaves it on.  Now there are two lit lanterns next to each other.
111100

Here's if the Devil lights the lantern two away on the other side (and keeps no more than 2 lit lanterns).
111110 D 1->1
111101 D 1->1
111011 D 1->1
110111 D 1->0
101110 D 1->1
011101 A 0->0 Angel needs to wait to turn off the other lit lantern.
111010 D 1->1
110101 D 1->1
101011 D 1->1
010111 A 0->1 Back to 1 lit lantern
101111 D 1->0 Needs to light or lose at the next lantern.
011110 A 0->0 Two lit lanterns next to each other.
111100

 

[phil1882]

actually this seems pretty straight forward to me, the angel simply turns off all lit lanterns and wins.

[EventHorizon]

1 hour ago, phil1882 said:

actually this seems pretty straight forward to me, the angel simply turns off all lit lanterns and wins.

Spoiler

Here's the last example from above, but with the angel turning off the first lantern it sees lit.

111110 D 1->1
111101 D 1->1
111011 D 1->1 ***(state that is repeated)
110111 D 1->0
101110 D 1->1
011101 A 0->1 Angel turns off this lantern.
111011 *** A state is repeated.  Angel loses.

 

[witzar]

3 hours ago, Evilhubert said:

There's a solution that I find simple and elegant enough to be satisfying

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

[harey]

I had this solution in mind, unfortunately, it fails because of repeated situations.

Starting situation: 6 lanterns, only lantern 6 is lit.

First round:
lantern 1: no action
lantern 2: devil turns it on
remaining lanterns: angel does not do anything (If the devil turns a lantern on before the angel has turned any off, then the angel should just do nothing on that circuit. )

Situation: Lanterns 2 and 6 are lit

2nd round:
lantern 1: no action
lantern 2: angel turns it off (on each circuit, turn off all lit lanterns until the devil turns an unlit lantern on)

Now, only the lantern 6 is lit: the game ends if the lanterns return to a previously encountered state

What am I missing?

[witzar]

26 minutes ago, harey said:

What am I missing?

 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.

[EventHorizon]

On 3/24/2024 at 8:40 AM, witzar said:

 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.

 

Spoiler

It is interesting that the angel still wins even with a much more favorable definition of state for the devil than was intended (just the lantern configuration looking forward from the pair's position).

The strategy given for the angel to win with the intended definition of a state doesn't work when applied to the other (e.g., 1001010101 -> 0101010101 first two get flipped then march through a bunch of repeated states).  So there's still some things to uncover about this, but it's an interesting problem with either definition.  Good job Evilhubert.