Jump to content
BrainDen.com - Brain Teasers


  • Posts

  • Joined

  • Last visited

  • Days Won


Posts posted by witzar

  1. 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?

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



  3. 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?

  4. Spoiler

    This is correct, Pickett. No "extra" moves are required (obviously we cannot do better, since there are 2n-1 combinations to test).
    Comparing this problem to Towers of Hanoi looks like a good insight to me, since both problems are naturally defined with exactly the same recurrence.
    I've played a game today where I had to brute-force such lock. I was just testing subsequent binary numbers (thinking of levers as bits), hence I made more moves then optimal. Even after I gave this problem some thoughts, I'd still be afraid to use "optimal procedure", since I feel that the gain in speed is not worth the risk of making a mistake and starting over.


  5. 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?

  6. For example you can encode MM using first digit except bottom segment (6^2=64>=60),

    you just need to agree on some order or the above 6 display elements, so that they represent MM in binary.
    (Each element of display is a binary digit "on"=1, "off"=0.)
    Same way you can use second digit to encode seconds.
    The remaining 4 elements of display (two bottom segments plus two dots) can be used to encode HH (4^2=16>=12).
    I don't see any particular ordering that feels natural.

  7. To display HH:MM:SS in 12-hour format you need ⌈log

    2(12*60*60)⌉ = 16 bits of information, but your display has only 15 elements. Therefore the task is impossible if each element can only be "on" or "off". You need to cheat a little bit, for example add blinking or something like that.



    I miscounted the elements:) The display has 16 not 15 of them, so you

    can use it without cheating.
    • Upvote 1
  8. Let:

    p = prob. of getting killed
    L = value of your life
    S = value of the package

    Expected value of going to work:
    EVW = p*(-L) + (1-p)(500 + 0.2*S)
    Expected value of staying home:
    EVH = S
    You are indifferent to going to work if and only if above EV's are in equilibrium:
    EVW = EVH
    p*(-L) + (1-p)(500 + 0.2*S) = S
    -p*L + 500 + 0.2*S - p*500 - p*0.2*S - S = 0
    p = (500 - 0.8*S)/(500 + L + 0.2*S)

    Note however, that if (500 - 0.8*S) < 0, then also p<0, but probability can't be negative,
    therefore you can't be indifferent to going to work when S > 625 (in such case staying home is always better for every possible value of p).

  9. There are two ways to get exactly four numbers: aaabcd and aabbcd.

    First you can get in 6_choose_3*6*5*4*3 ways, and
    second you can get in 6_choose_4*3*6*5*4*3 ways,
    making total of (6_choose_3+6_choose_4*3)*6*5*4*3 = (20+15*3)*6*5*4*3 = 23400 ways.
    We should not accept the bet if 23400/6^6 > 1/2.
    It's close, but we are slight underdog, so we reject.

  10. This puzzle is inspired by posted by bonanova.

    Again we work on a hexagonal tiling of a plane, and the question is about
    possibility of covering some shape with triminoes.
    Trimino is a "triangle" formed by three unit hexagons sharing common vertex.

    The shape to cover is defined as follows:
    Let's pick a unit hexagon and call it H1.
    Now we recursively define Hn+1 as a sum of Hn and all unit hexagons adjacent to Hn.
    So basically Hn is a "hexagon" with side of length n (unit hexagons).

    Let Dn be Hn with one unit hexagon at it's center removed.
    So, can you cover D2015 with triminoes?

  11. The answer is "no".

    Consider those two squares in the center, that - when removed - disconnect the board into two pieces.
    Those two squares can be covered either by one or by two dominoes.
    In both cases this disconnects the board into two pieces, that cannot be covered by dominoes,
    since they have different number of black and white squares.
    To see this, first inspect the case with one domino (just count black squares and white squares of the upper piece).
    The difference equals 2 in this case.
    Now it is easy to realize that replacing the single domino with two dominoes can fix this difference only by 1 (not enough).
    • Upvote 1
  12. Suppose the bottom-left corner is black (and so are the other corners).

    There is one more black square than white,
    therefore the remaining square should be black.
    The question remains: could it be any black square?
    The answer is "yes".
    To see this you can draw a path for the lame King (the one that cannot move diagonally),
    that visits each square exactly once (there is no requirement for path to be closed this time as in solution to #1).
    Removing one black square breaks the path into two segments of even length (only one segment in case when terminal square of the path is removed),
    and obviously we can easily cover each segment with dominoes.
    • Upvote 1
  13. Consider a lame King (chess piece) that cannot move diagonally.

    It's easy to draw a closed path for him to inspect all his kingdom:
    a closed path that visits each square exactly once (and returns to starting point).
    Obviously such path can be covered by dominoes starting from any square,
    as well as any continuous segment of this path of even length.
    Removing two squares of different color we break the path into two such segments,
    so the answer is "yes".
    • Upvote 1
  14. The answer is "no".

    Consider a rook that can only move on black squares.
    Let's call "reachable" the squares that can be reached by this rook
    (in finite number of moves) from the bottom-left corner.
    Only black squares in rows: 1 (bottom), 3, 5, 7 and 9 are reachable.
    This accounts to 25 (5*5) reachable squares total.
    Now observe that a quadomino, now matter how placed on the chessboard,
    always covers an even (0 or 2) number of reachable squares.
    But 25 is odd.

    • Upvote 1
  15. Let s(t) be the distance Alice covers in time 't'.

    We assume s(t) is a continuous and differentiable function of 't' - a reasonable assumption: Since Alice can't disappear and appear in a different spot in zero time (implying infinite speed), and can't instantaneously change her speed to a completely different value (implying infinite acceleration).

    This is exactly what meant by the last sentence of my answer:

    The question remains: is it possible to run like this?

    I'd also add one more condition: s(0)=0, since the runners start moving when the the race starts.

    Same restrictions should also apply to Bob,

    so another question is: how can he run with a constant positive speed?

    Obviously he can't without braking his speed function at 0.

  16. Alice could run fast for 0.2 mile then slow for the rest of the first mile,

    and repeat this pattern for the whole marathon.
    This way her pace is constant on every 1-mile segment.
    Now, after 26 miles of the race she is 26 seconds behind Bob,
    and she is going to run fast on remaining 0.2 mile segment of the race.
    If she runs fast enough the fast segments, she wins.
    The question remains: is it possible to run like this?

  • Create New...