dougbell's Profile
Genius
487
points

Questions
1

Answers
36

dougbell loves solving puzzles at PuzzleFry.com. I am proud PuzzleFry member and like my time invested in solving brain teasers.
  • Somewhat more simply stated: pick an ant.  Each of the other two ants must decide to go the same direction which is 0.5 * 0.5 = 0.25.

    • 48548 views
    • 3 answers
    • 1 votes
  • Genius Asked on 21st October 2015 in Microsoft Interview Puzzles.

    The problem does not state whether the random number is inclusive, exclusive or some combination, of the bounds 0 and 1.  My answer assumes the typical random number generator, which is inclusive of 0 and exclusive of 1.  It takes exactly two calls to the random number generator.

    radius = random / 2
    degrees = random * 360

    x = radius * sin(degrees)
    y = radius * cos(degrees)

    Now the problem with this solution is that it lacks uniform distribution.  Half the points will have radius < 0.25 and half 0.25 to 0.5, but the area in the circle with radius < 0.25 is only 25% of the total area of the circle.  So we need to distribute the points along the radius using the inverse square of the random value so that the probability of a point having radius r is proportional to the area of a circle with radius r (i.e. a radius that gives a circle with area a is half as likely as a radius that gives a circle with area 2a).

    radius = sqrt(random) / 2
    degrees = random * 360

    x = radius * sin(degrees)
    y = radius * cos(degrees)

    • 3895 views
    • 1 answers
    • 0 votes
  • Only the lights connected to switches with a number that has an odd number of factors are left on.  These are the square numbers.  The largest square square number less than 1000 is 31^2 = 961, so there are 31 lights on connected to the switches 1^2, 2^2, … 31^2.

    • 3816 views
    • 2 answers
    • 1 votes
  • 1897

    There must be 7 years without a leap year between when he was born and his seventh birthday.  1900 is not a leap year.  He was born Jan. 3, 1897 and his seventh birthday was in 1904 before the leap day that year.

    • 3617 views
    • 2 answers
    • 2 votes
  • This is an interesting problem.

    We know that if the fifth son gets x5 then the fourth son gets x4 = 5*(x5 + 1)/4 – 1 = x5 + (x5+1)/4 and third son gets x3 = 5*(x4 + 1)/4 – 1 = x4 + (x4+1)/4 and so on.  Representing what each son gets in terms of what the fifth son gets gives:

    x3 = x5 + (x5+1)/4 + ((x5+(x5+1)/4))/4
    = x5 + (x5+1)/4 + 5(x5+1)/16
    x2 = x5 + (x5+1)/4 + 5(x5+1)/16 + 25(x5+1)/64
    x1 = x5 + (x5+1)/4 + 5(x5+1)/16 + 25(x5+1)/64 + 125(x5+1)/256

    From this we know that the fifth son (x5) must get a number of coins that can be expressed in the form x5 = 256y – 1.

    The other requirement is that x5 must be a multiple of 5, because each daughter gets 4/5 of what the 5th son gets.  That means that the final digit of y must be either 1 or 6 so that the final digit of 256y is 6.  The smallest such value for y is 1, making x5 = 255.

    Plugging in 255 for x5 gives

    x1 = 624
    x2 = 499
    x3 = 399
    x4 = 319
    x5 = 255
    with each daughter getting 4/5 * 255 = 204 and the manager getting 5 gold coins

    204 * 5 + 255 + 319 + 399 + 499 + 624 + 5 = 3121 = 624 * 5 + 1.  The minimum number of coins is 3121.

    The second smallest number of coins possible is 18,746, which results from setting y = 6.

    • 9581 views
    • 1 answers
    • 1 votes
  • After removing mirror images, there are six unique positions on the board: (1,1), (1,2), (1,3), (2,2), (2,3), (3,3).  The knight starts at (3,3).

    From each position, there is a fixed probability of moving to each of the other five positions.  The probability of moving off the board is 1 minus the sum of the probabilities of moving to other board positions.

     .      -------- starting position --------
     .      (1,1) (1,2) (1,3) (2,2) (2,3) (3,3)
     (1,1)                          .250
     (1,2)              .250  .250        1.000
     (1,3)        .125              .250
     (2,2)        .125              .250
     (2,3)  .250        .250  .250
     (3,3)        .125
     

    A quick examination reveals that positions (1,3) and (2,2) are equivalent–they each have the same probability for the following square.  So we can collapse them into a single state we’ll label as (*,*), giving the following five position table.

     .      ----- starting position -----
     .      (1,1) (1,2) (*,*) (2,3) (3,3)
     (1,1)                    .250
     (1,2)              .250        1.000
     (*.*)        .250        .500
     (2,3)  .250        .250
     (3,3)        .125
     

    The probability for the knight to be in each of the five positions at the end of k moves is the sum of the product of probability of the knight moving to that position from another position and the probability of having been in that position at the end of k-1 moves.  At zero moves, the probability of being in position (3,3) is 1 and the probability of being elsewhere on the board is 0.  After each move, the probability of the knight having moved off the board is 1 minus the sum of the probabilities of it being in each position.

     k  (1,1)  (1,2)  (*,*)  (2,3)  (3,3)   Off board
     0                              1.00000
     1         1.00000
     2                0.25000       0.12500  0.62500
     3         0.18750       0.06250         0.75000
     4  0.01563       0.07813       0.02344  0.88281
     5         0.04297       0.02344         0.93359
     6  0.00586       0.02246       0.00537  0.96631
     7         0.01099       0.00708         0.98193
     8  0.00177       0.00629       0.00137  0.99057
     9         0.00294       0.00201         0.99504
     10 0.00050       0.00174       0.00037  0.99739
     
    • 7323 views
    • 2 answers
    • 1 votes