Jump to content
BrainDen.com - Brain Teasers


  • Posts

  • Joined

  • Last visited

  • Days Won


Posts posted by witzar

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


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

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

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

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

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

  8. 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
  9. 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
  10. 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
  11. 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
  12. 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.

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

  14. If at least one of m or n is odd, player 1 wins. First he removes middle line, then do actions symmetrical to player 2's actions with the removed line.

    This is incorrect.

    Consider 3*3 for example. After player 1 removes middle line, player 2 removes some line perpendicular to line just removed, leaving player 1 with 2*2.


    if m and n both even, player 2 wins. Every move player 1 make, player 2 make symmetrical move with center point.

    This is correct. :)
  • Create New...