Jump to content
BrainDen.com - Brain Teasers

Evilhubert

Members
 View Profile  See their activity

  • Posts

    5

  • Joined

  • Last visited

 Content Type 

Posts posted by Evilhubert

  1. Lanterns of Eden.

    in New Logic/Math Puzzles

    Posted

    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.

     

  2. Lanterns of Eden.

    in New Logic/Math Puzzles

    Posted

    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?

    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!

  5. Propositional Logic Problem

    in New Logic/Math Puzzles

    Posted

    Can I ask for a bit of clarification? There are a few things that could be interpreted in a couple of different ways

    • When you say "or", do you mean AND/OR or Exclusive OR?
    • When you say "IF" do you mean simply "IF", or "IF and only IF"?
    • If the IF condition in a character's statement is not met (e.g. A says "If B is lying, then C is involved", but B is actually telling the truth), is that character considered to be telling the truth, lying, or neither? (obviously this becomes clear if the IF statements are interpreted as 'if and only if', but I'm asking in case they are not)
×
×
  • Create New...