Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Jul 3, 2014

Mad Robot Puzzle

Source: http://nrich.maths.org/

Problem:




A mad robot sets off towards the North East on a journey from the point (0,0) in a coordinate system. It travels in stages by moving forward and then rotating on the spot. It follows these pseudo-code instructions:

SUB JOURNEY
    DISTANCE = 1000
    WHILE (DISTANCE > 0.001)
        MOVE DISTANCE
        STOP
        ROTATE(90, DEGREES, CLOCKWISE)
        DISTANCE = DISTANCE / 2
    END WHILE
    EXPLODE
END SUB

Where does the robot explode?

Update (23 Oct 2014):
Solution: Posted by me (Pratik Poddar) in comments!


9 comments:

  1. (x,y) = (1/3√2, -19/15√2) = (0.2357,-0.8957)
    Since length is 1000, coordinates become (235.7,-895.7)

    For calculation, I have used GP for infinite numbers (not stopping at distance =0.001)

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Thinking of the grid as a a complex plane, the initial step the robot takes is to 1000*(1+i)/(sqrt 2): call this position z.
    Her total journey is then to

    Final position = z + z(i/2) + z(i/2)^2 + . . . + z(i/2)^n = z*( 1 - (i/2)^(n+1) )/(1-i/2)

    where n is the largest integer for which 1000/(2^n) >= 0.001, namely, 19, so

    Final position = z*( 1 - (i/2)^20 )/(1-i/2) ~ 200(sqrt 2) + 600(sqrt 2) i

    This is an approximation, ignoring the 1 - (i/2)^20 factor (if the robot never stops walking, this is the point she approaches). Thus her final coordinates are about (282.8, 848.5).

    ReplyDelete
  4. To calculate the number of moves the mad robot takes before it explodes, we have 1000/2^n < 0.001 i.e n > 19.93. So the robot does 20 moves, including the first step (n=0) of length 1000, before it explodes. The x-coordinate of the final position is given by summation 1000/sqrt2 * (1 + 1/2 - 1/4 - 1/8 + .... - 1/2^19) and the y-coordinate is 1000/sqrt2 * (1 - 1/2 - 1/4 + 1/8 + .... + 1/2^19). Take out (1 + 1/2) and (1 - 1/2) from the first and the second summations you'll end up with a Geometric Progression with multiplication factor of (-1/4) with 10 terms. Summation of this gives the x and y coordinates as (1200/sqrt2, 400/sqrt2).

    ReplyDelete
  5. I think a simpler solution would be just simply rotate the coordinate axis by 45 degrees and then rotate back after solving the problem. The answer should be (600sqrt2, 400sqrt2)

    ReplyDelete
  6. All the answers are wrong. Correct solution: http://plus.maths.org/content/mad-robot-solution

    Total Distance travelled = 5*1000 (1 + 1/2^4 + 1/2^8 + 1/2^12 + 1/2^16) = TDT

    (x,y) = (9*sqrt(2)*TDT/80, 3*sqrt(2)*TDT/80)

    ReplyDelete
    Replies
    1. Ain't total distance travelled should be 1000*(1+1/2^4+1/2^8+2^12+2^16)*(1+1/2+1/4+1/8)?

      Delete