All Activity

After two years of war the Russians still haven't found Zorro

Yeah, that's not a very interesting definition of the state. Try the one I described. 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.

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: To explain the winning strategy, I'll first point out the following: So, to win the game:

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.

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?

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

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 L2, L3 and so on. The last lantern can be referred to as LT, with T = Total number of lanterns minus 1. Each time they walk round the lanterns and return to L0 will be referred to as a circuit. So who wins? So what's the winning stragegy? But how can we prove the strategy will always work for any number of lanterns? I just want to give a big thank you to witzar for posting the problem - I really enjoyed this one!

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

Was there an easier method? Concave

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

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.

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.

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. 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). 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. 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.

@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.

I couldn't follow that, harey.

Just saw your post harey.

recreating the results of the code...

Hello everyone, I’ve created a little puzzle that follows the cryptographic principle of zero-knowledge proof. Let P = xx, the age of Peter To find xx, I will provide you with means to verify the statements of the puzzle, without giving you any direct informations about the ages of the characters. The ages of the characters are not given but can be found. Although there are an infinite number of answers that could verify the information I provide, there is one answer that can be verified to 99% assuming the puzzle is honest and verifiable, and that Peter has a realistic age and life. How old is Peter ? - Peter has 5 children, Matthew, Nancy, Phil, Quinlan and Ryan - Peter’s age is the sum of the ages of all of his children - The concatenation of his children’s ages forms a palindrom - Peter’s age is a semi-prime number - 2 of his children are the same age - One of his children is half the age of one of his older siblings - Quinlan is younger than Phil - Only two of his children have a job - At least 2 of his children have a palindrome age - Matthew can’t read - Peter didn’t have a child before the age of 30 - If x is the age of the child < 10, then we’ll write 0x, such that a 1 year-old child = 01

sorted configurations with 6 lanterns (and added devil best choices I omitted before) 5 lanterns 4 lanterns 3 lanterns 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).

On the "ugly strategy"

Edit: Oops. I guess switch to 1 meaning off and 0 meaning on to match the story. Who wins? Ugly Strategy with not much intuition as to how/why it works. (Obviously, I don't consider this as the answer...) Yay code Code output for 4 lanterns 5 lanterns 6 lanterns

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?