Jump to content
BrainDen.com - Brain Teasers

harey

Members
  • Posts

    212
  • Joined

  • Last visited

  • Days Won

    8

Posts posted by harey

  1. 1 hour ago, CaptainEd said:

    Harey, can we assume as Molly Mae did, that there is no maze, but only a simple path? I assumed otherwise, that it can be a maze, so I imagined a figure H, with only two cells with cement (top center and bottom center).

    I do not really understand what you mean by "simple path", but I think the answer is no. The figure H is OK, but you can very well have:

    * * *    * * c   * * *
    c * c   c * *   * c *
    * * *    * * *   * c * ...

    Your list must work for all these cases, as well as for all grids where there is/are one/three/four cement blocks. i.e. the solution Molly Mae proposed would not work for the first maze (so it does not matter anymore that it works for the 2nd and 3rd).

    Even calculating the number of possibilities for 2 blocks gives me headaches. 7 * 6 / 2? Wrong, the robot must be free to leave the corner and the lower right corner must remain accessible.

    To get insane...

  2. 3 hours ago, Molly Mae said:
      Hide contents

    Case: n=3

    Solution: RRDDRRDDRD (alternately: DDRRDDRRDR), We did it!

     

      Hide contents

    It can happen: RRddrrddrd (in lowercase instructions the robot cannot execute)

     

  3. 13 hours ago, CaptainEd said:

    I gather that when it sees Left, it goes as far left as possible until it hits cement.

    An interesting variant. The problem states "there is a path", but it does not state "there is a path for the robot".

    I think it is easier we stay with moving just to the next square.

  4. Each square of an n x n grid of squares is either filled with cement blocks or left empty, such that there is at least one path from the top left corner to the bottom right corner of the grid. Outside the grid everything is filled with cement. A robot is currently located at the top left corner and wants to get to the bottom right corner, but it only knows the value of n and doesn't know the layout of the grid. It also has no method of observing its surroundings, and it is your job to give it instructions to ensure it ends up at its destination. Your instructions should be a finite list of directions (Up, Down, Left, Right) - the robot will try to move in the indicated directions in order, and, if there is a cement wall in the way at some step, it will simply fail to move in the corresponding direction and continue on with the next instruction in the list. Since the robot has no way of sensing whether it has reached its destination, it might reach the destination somewhere in the middle of your list of instructions and then later leave. The goal is to give a list of instructions, depending only on n, such that after following your instructions the robot is guaranteed to end its journey in the bottom right corner of the grid.

    The bad news: I do not know the solution and I cannot ask for hints.

  5. Evident after translating it to college version:

    Spoiler

    From a shuffled stack of 26 red and 26 black cards, R red and B black cards were drown. Prove that after drawing additional k cards (k=0...51-R-B), p(the card on the top of the stack is red) does not change.

    Proof by induction. Lets call r the number of remaining red cards and b the number of remaining black cards.

    a) p(red   is on top) = r/(r+b); p(then red is on top)=(r-1)/(r+b-1)
    b) p(black is on top) = b/(r+b); p(then red is on top)=(r  )/(r+b-1)

    a) becomes: p=r/(r+b) * (r-1)/(r+b-1)  = r*(r-1)/denom
    b) becomes: p=b/(r+b) * (r)/  (r+b-1)] = b* r   /denom

    In both cases, denom=(r+b) * (r+b-1)

    Summing up the numerators:
    r*(r-1) + b*r = r*r-r  + b*r
                  = r*(r-1 + b)

    Conveniently, we can simplify (r-1+b) in the numerator against (r+b-1) in the denominator, leaving r/(r+b). cqfd

     

    Just a little bit late...

    I guess in a test, half an hour would be allocated for this question. I get depressed when I realize the time I needed.

  6. The plot for all cases:

    Spoiler

     

    Round 1: M1W1 (M1W1) M2W2 (    ) M3W3 (    ) M4W4 (    )
    Round 2: M1W2 (M1w2) M2W3 (    ) M3W4 (    ) M4W5 (    )
    Round 3: M1W3 (M1w3) M2W4 (    ) M3W5 (    ) M4W1 (m4W1)
    Round 4: M1W4 (M1w4) M2W5 (    ) M3W1 (m3W1) M4W2 (****)
    Round 5: M1W5 (M1w5) M2W1 (m2W1) M3W2 (****) M4W3 (****)

    W1: protection in the 1st round (supposing it is M1 who is infected)
    W2: cannot escape
    W3: cannot escape
    W4: last round (was wrong in the previous post)
    W5: last round

    Round 1: M1W1 (    ) M2W2 (M2W2) M3W3 (    ) M4W4 (    )
    Round 2: M1W2 (m1W2) M2W3 (M2w3) M3W4 (    ) M4W5 (    )
    Round 3: M1W3 (****) M2W4 (M2w4) M3W5 (    ) M4W1 (    )
    Round 4: M1W4 (****) M2W5 (M2w5) M3W1 (    ) M4W2 (m4W2)
    Round 5: M1W5 (****) M2W1 (M2w1) M3W2 (m3W2) M4W3 (****)

    W1: last round
    W2: 1st round (supposing it is M2 who is infected)
    W3: cannot escape
    W4: cannot escape
    W5: cannot escape

    Round 1: M1W1 (    ) M2W2 (    ) M3W3 (M3W3) M4W4 (    )
    Round 2: M1W2 (    ) M2W3 (m2W3) M3W4 (M3w4) M4W5 (    )
    Round 3: M1W3 (m1W3) M2W4 (****) M3W5 (M3w5) M4W1 (    )
    Round 4: M1W4 (****) M2W5 (****) M3W1 (M3w1) M4W2 (    )
    Round 5: M1W5 (****) M2W1 (****) M3W2 (M3w2) M4W3 (m4W3)

    W1: cannot escape
    W2: last round
    W3: 1st round (supposing it is M3 who is infected)
    W4: cannot escape
    W5: cannot escape

    Round 1: M1W1 (    ) M2W2 (    ) M3W3 (    ) M4W4 (M4W4)
    Round 2: M1W2 (    ) M2W3 (    ) M3W4 (m3W4) M4W5 (M4w5)
    Round 3: M1W3 (    ) M2W4 (m2W4) M3W5 (****) M4W1 (M4w1)
    Round 4: M1W4 (m1W4) M2W5 (****) M3W1 (****) M4W2 (M4w2)
    Round 5: M1W5 (****) M2W1 (****) M3W2 (****) M4W3 (M4w3)

    W1: cannot escape
    W2: cannot escape
    W3: last round
    W4: cannot escape
    W5: cannot escape

    Round 1: M1W1 (    ) M2W2 (    ) M3W3 (    ) M4W4 (    )
    Round 2: M1W2 (    ) M2W3 (    ) M3W4 (    ) M4W5 (m4W5)
    Round 3: M1W3 (    ) M2W4 (    ) M3W5 (m3W5) M4W1 (M4W1)
    Round 4: M1W4 (    ) M2W5 (m2W5) M3W1 (****) M4W2 (M4w2)
    Round 5: M1W5 (m1W5) M2W1 (****) M3W2 (****) M4W3 (M4w3)

    W1: cannot escape
    W2: cannot escape
    W3: last round
    W4: escapes
    W5: infected by definition

     

    Strategy
     

    Spoiler

     

    The optimal strategy requires to wear the protection in the last round, quite evident.

    M1 infected, escape for: W4, W5    1/9 * 2/5 = 2 / 45
    W1 infected, escape for: W4, W5    1/9 * 2/5 = 2 / 45
    M2 infected, escape for: W1        1/9 * 1/5 = 1 / 45
    W2 infected, escape for: W1        1/9 * 1/5 = 1 / 45
    M3 infected, escape for: W2        1/9 * 1/5 = 1 / 45
    W3 infected, escape for: W2        1/9 * 1/5 = 1 / 45
    M4 infected, escape for: W3        1/9 * 1/5 = 1 / 45
    W4 infected, escape for: W3        1/9 * 1/5 = 1 / 45
    W5 infected, escape for: W3 + W4   1/9 * 2/5 = 2 / 45

    Total                                         12 / 45
    =====                                         =======

    Men have no chance, just one other woman will escape, if:
    - W5 is infected and
    - she is W4, giving:

    1/9  *  1/4  =  1/36  = 1/12

    => near 8 2/3 members of the group of nine get infected.

    e. o. e.

     

    I knew it would be hard, but not THAT hard.

  7. Spoiler

     

    Listing all the outcomes (after excluding cases when you take the place of the infected Wn), it comes out that you always get off if you use the protection in the last round - provided you are lucky to be on the right place. (Not very surprising, as the disease spreads, the chances to get infected rise.) That makes 1/5. (A little bit more if you happen to be W4, see below.)

    All the men get infected (which was clear from the beginning) and three women certainly.

    If W5 (the woman just looking in the first round) is that one that is infected, W4 (the woman preceding her) escapes. That makes 1/8. (To subtract the compound p that you are W4.)

    So finally, we will come very close to 8.75 infected members of the group of 9.

     

     

  8. So far, so good?
     

    Spoiler

     

    Case is M1 or W1 infected.

    In brackets:
    - empty: none infected on the end of the round
    - M1W1:  M1 infects W1 or inversely
    - m4W1:  m4 is infected by W1
    - ****:  both already infected

    Round 1: M1W1 (M1W1) M2W2 (    ) M3W3 (    ) M4W4 (    )
    Round 2: M1W2 (M1w2) M2W3 (    ) M3W4 (    ) M4W5 (    )
    Round 3: M1W3 (M1w3) M2W4 (    ) M3W5 (    ) M4W1 (m4W1)
    Round 4: M1W4 (M1w4) M2W5 (    ) M3W1 (m3W1) M4W2 (****)
    Round 5: M1W5 (M1w5) M2W1 (m2W1) M3W2 (****) M4W3 (****)

    W1: protection in the 1st round (supposing it is M1 who is infected)
    W2: cannot escape
    W3: cannot escape
    W4: 1st round
    W5: last round

    At least, did I understand the problem?

     

     

  9. 1 hour ago, ThunderCloud said:
      Hide contents

    As you say, 3 cards later, p(next card is red) = p(final card is red). So there is still no advantage to calling "Stop!" versus continuing to let the cards be dealt at that point, even though your probability of winning will have certainly changed from 3 cards ago. It is no different, statistically, than simply betting on the final card being red — that probability changes as cards are dealt out, but you cannot influence it.

    Spoiler

     

    So there is still no advantage - well, that's what I ask you to prove. It does not result from p1(R is next) = p1(last one is R) and p2(R is next) = p2(last one is R).

    It is no different, statistically, - the same. I can believe you or not. 

    In the https://en.wikipedia.org/wiki/Secretary_problem the p(next candidate is the best) = p(last candidate is the best) also is true all the time. Still, you do not choose the first candidate.

    I have about the same problem. If X has a strategy to predict R, then Y employing the mirror strategy can predict B. At any point, their chances sum 1. Just it is insufficient.

     

     

  10. I found a strategy, but far from sure it is optimal.
     

    Spoiler

     

    Divide the coins from left to right as 'pointer' and 'data' so that the 'pointer' is just large enough to access all 'data'. (Example with 17 coins: 4 coins are pointer, necessary to address 13 coins of data. With a pointer of 3 coins, we could not address the remaining 14 coins of data.)

    What if the rare coin is within the 'pointer'? We can solve it this way:
    Count the number of heads:
    - if it is even, the pointer solution apply
    - if it is odd, take the first head from left.

     

     

  11. On 2/27/2018 at 2:46 AM, ThunderCloud said:

    Therefore, at any given juncture, it is never more (nor less) advantageous to call "Stop!" than it is to allow all of the cards to be dealt out.

    True so far. But it does not imply that it is not advantageous to i.e. wait for the 3 next cards and call "Stop!" After the next 3 cards, the p(next card is R)=p(the last card is R) still holds - but with (most probably) a different p.

  12. 15 hours ago, bonanova said:

    In fact, one way to fail is to first assign rooms to the green men. That fails because it only serves only to create a bijection of { rooms } with { green men }. Every green man gets a room, true, but (gulp) also, every room houses a green man. Oy vey! The blue contingent got excluded.

     

    I do not think there is need to use the spoiler anymore.

    If the blue are excluded because every room houses a green man, the same way you cannot accept even a single new guest.

  13. Thanks Thalia...
     

    Spoiler

     

    For the case being extremely lucky, there is the case to be extremely unlucky - the first 26 cards are red.

    You can say he can be very lucky - 25 of the 26 cards are red. Outweighted when there 25 of 26 are red.

    ...

    Every situation where there remain more red cards in the deck has a counterpart with inverse situation.

    If you try with a small number like 4, 6, 8... you see the correspondence of cards being have dealt and the possibilities of what can get out (permutations of the stack).

     

     

  14. 20 hours ago, bonanova said:

    How's that?

    Brilliant, surprisingly interesting and leading to a major annoyance.

    Spoiler

    I did not expect much from this question, it is not a number, basta. I had the idea to number the rooms of the green men starting with 1, but had to find a different 1 from the 1 of the room number of the first green man.  And I did not do the jump. Seems so easy now. But...

    An infinity of rose women arrives. Each woman is married to one and only one blue or green man and each man is married to exactly one woman. Each woman asks for a separate room adjacent to her husband's room. The manager understands 'adjacent' his way and instead of moving people, he builds a 2nd floor. Each woman is therefore upstairs her husband. There is a relation 1 to 1 between integers and women, their rooms can be numbered the conventional way. Now a woman complains the wives of blue men have the same room number as their husbands while she does not. Telling her that blue numbers and rose numbers are different seems a little week.

    I think we can say that the blue men originally in rooms 2 and 4 are now neighbors, but maybe we can't even say that. It would be like asserting that (inf+2) - (inf+1) = 1, where the terms on the left are meaningless.

    Oh yes, we can say that. The blue man from the room 2 * n (original numbering) is now now in the room n_blue. Same for the green men. True for any n, if true for n then true for n + 1, why not for n -> inf? The equation does not bother me as long as we interpret it the same way:
    (2 miles down + 2) - (2 miles down + 1) = 1. (There might be a restriction: it is true in this problem, but it might be meaningless in other circumstances.)

    Another way to write it:
    (11_blue - 5_blue)=(71_green - 65_green). In both cases, there are 6 walls between them, too much to communicate via WiFi.

    Well, now back to the original problem. Everybody leaves, the hotel is empty. The green and blue men arrive all together and go to the room they occupied previously. Is this problem equivalent to the first one?

    Precision: By equivalent, I mean that the problems are announced in a slightly different way, but the answers remain the same. Something this way:

    Aunt: If I give you 5 bananas and take back 2 bananas, how many bananas have you?
    John: I do not know.
    Aunt: I met your teacher and she told me you make this kind of problems at school.
    John: Yes, but we do it with apples.

    Just do not tell me that the men know now the room numbers. Besides being clairvoyant, they can move in time. Forwards, backwards and sideways.

  15. Sorry for 'discard', I meant these numbers build a {set} from which elements can be removed. And yes, we remain in rationals.

    What if l only paint those between 0.5 and 0.6, even leaving .53745 unpainted? Did I not paint an infinite number of numbers?

    We turn in round here. You claim that if you can remove an infinite amount of elements from a set, the set will be empty - I claim there may remain some elements (and even more then removed, depending on circumstances). I suppose you apply a 'law' or a 'theorem'. Can you give me the (Wikipedia) reference?

  16. 1 hour ago, bonanova said:

    I would dispute your first point. I can't immediately think of a scenario that permits a discard which will not eventually happen given an infinite number of opportunities. Can you provide one?

    Maybe an idea. There is an infinite number of numbers between 0 and 1. I have the opportunity to discard an infinite number of numbers between 0 and 1.

    How much are you willing to bet that nothing remains between 0 and 1?

  17. There is a hotel with an infinite number of rooms, all rooms occupied by little green men (one man in a room). An infinity of little blue man arrive and each one asks for a room. No problem, the manager moves the blue man from the room n to the room 2*n, freeing the odd-numbered rooms for the green men. So far, loosely copied from https://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel.

    It turns out that the blue men sing between noon and midnight and sleep between midnight and noon while the green men sleep between noon and midnight and sing between midnight and noon. Complaints.

    The manager decides to group them. Conveniently, the rooms are in a straight line, numbered from left to right. While there is a green man left to a blue man, he makes them change the rooms.

    Eventually, all the blue men leave.

    - how many rooms are free?
    - how many rooms remain occupied?
    - what is the number of the first occupied room?

  18. 6 hours ago, bonanova said:

    The key question is this: can a coin that is kept at a certain event ever be discarded at a later event?

    If a coin can be discarded, it does not mean it will be discarded. I would reformulate it: The key question is this: will all coins that are kept at a certain event ever be discarded at a later event?

    BTW, we can establish a bijection between Al's and Bert's coins. The coins bear green numbers. After each step, Al renumbers them and assigns them blue numbers 1, 3, 5, ... His blue numbers will match the (green) numbers in Bert's box. For any number of steps. I think it is legal to assume it is true even for N-> inf.

    Another way to prove that Bert's box will not be empty: graphical presentation. The number of coins in his box is a straight line (at 45 degrees). How is that it suddenly drops to 0?

    And maybe a corollary: Bert never discards more coins that he receives. How is that when he has, let's say 8 coins, he can have less in a later stage?

    If we reason with {coins} and {events}, don't you see a 1-1 relation?

  19. 12 hours ago, bonanova said:

     

      Hide contents

    Al:
    On step 1 Al discards coin 1. On step 2 A discards coin 2. ... On step N Al discards coin N. As N -> inf, every coin is discarded.
    If there were a coin in Al's box at midnight it would have a number. What number would that be?

    Lets start with this one.

    If every coin is discarded, it comes to claim that inf - inf =0

    Remember the hotel with an infinite number of rooms all occupied? An infinity of guests arrive, you move the person from room 1 to room 2, from room 2 to room 4, from room 3 to room 6... getting an infinity of empty rooms.

    Now, an infinity of guests leave. Is the hotel empty? And why?

     

  20. After N steps, they will have received 2*N coins and withdrawn N coins. At that moment, there will be 2*N-N coins in the box.

    If the box is empty at midnight, this implies:

    limit(2*N-N)(for N->inf) = 0

    At least a little bit surprising.

    @ThunderCloud

    I have some troubles to refute your argument. If you remove an infinity of finite numbers from infinity of finite numbers, it does not imply no finite number remain. (Not sure I am convincing and clear enough.)

    Counterargument: Al removed all coins 1 - N, coins > N remain. If N -> inf, numbering looses it's sense, but he did not remove all coins.

    As for Charlie, I am ruminating, too. The first idea: every number will remain with p=1/2. Wrong, 1 will be more likely removed than 99.

    2nd idea:
    1st step, 2 coins: p(removing 1)=1/2
    2nd step, 3 coins: p(removing 1)=p(1 was not removed in the first step) * 1/3 = 1/2 * 1/3 = 1/6, p(1 remaining after 2nd step)=1 - 1/2 - 1/6 = 1/3
    3rd step, 4 coins:  p(removing 1)=p(1 not yet removed) * 1/4 = 1/3 * 1/4 = 1/12, p(1 remaining after 3rd step)=1 - 1/2 - 1/6 - 1/12 =

    I will not venture further, but this will not converge to 0. (Compare to 1 - 1/2 - 1/4 - 1/8...)

     

  21. On 1/5/2018 at 11:50 PM, CaptainEd said:

    Maybe this is clearer and more accurate than my previous try.

    Point one: 

     

      Hide contents

     

    The shortest distance is between one pair, A and B. They are a mutual pair, as the shortest distance from each goes to the other.

     

    Point two:

     

      Hide contents

     

    Consider the node whose smallest distance is greater than anyone else’s. Call that soldier A. A’s smallest distance is to a node, call it B.

    Which soldier is pointing at A? Call it Z. Because AB is A’s least distance, AB < Ax for all x in S - {A,B}

    Because ZA is Z’s least distance, ZA < Zx for all x in S - {A,Z}

    Because  A’s smallest distance is greater than anyone else’s, ZA < AB. But that contradicts the fact that AB < AZ. 

    However, it is possible that Z = B, as AB <= AZ and ZA <= AB. 

    Result: the node with the highest lowest distance is in a mutual pair OR A is not watched.

    What about the next highest least distance? Call it node C, its successor D and predecessor Y.

    CD < Cx for all x in S - {C,D}

    YC < Yx for all x in S - {C,Y}

    Because C’s smallest distance is greater than anyone other than A or B, YC < CD, but that contradicts that CD < YC.

    This can only happen if Y = D. So CD are a mutual pair OR C is not watched.

    The same argument proceeds one pair at a time, until an unwatched soldier is found, OR one soldier remains. That soldier is not watched.

     

     

     

    Cannot you shorten it?

    - if no one else watches A nor B, remove A and B and start over (this happens if A and B are very near and all other are far away enough)
    - if someone else watches A and/or B, at least one is not being watched (evident; if proof needed, start with 3 and continue with recursion)

×
×
  • Create New...