Mad robot: Solution

Submitted by mf344 on October 14, 2012
robot

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?

Solution

First we find the number of forward turns, noting that the WHILE(DISTANCE > 0.001) condition is evaluated after each halving.

The forward motion, if it occurs, following the $n$th turn will be of distance $1000\times 2^{-n}$. This will occur for each $n$ for which

  \[ 1000\times 2^{-n} > 0.001. \]    

Taking logs gives

  \[ \log {1000}-n\log {2}>\log {0.001} \]    

Rearranging gives

  \[ n<\frac{\log {1000}-\log {0.001}}{\log {2}} = \frac{\log {1000000}}{\log {2}} \approx 19.93. \]    

This first becomes invalid after 20 turns. Thus, the path of the robot is determined by 20 motions. The directions that the robot travels in these 20 motions are alternately NE, SE, SW, NW, .... Since there are 20 motions in total there are 5 motions in each of these directions.

Let $T$ be the total distance travelled NE. Then

  \[ T=1000\left(\frac{1}{2^0}+\frac{1}{2^4}+\frac{1}{2^8}+\frac{1}{2^{12}}+\frac{1}{2^{16}}\right). \]    

The NE motion contributes a component $d$ travelled in the $x$ direction and the same component $d$ travelled in the $y$ direction. By Pythagoras’ theorem we have

  \[ 2d^2=T^2, \]    

so

  \[ d=\frac{T}{\sqrt {2}}. \]    

Note that the distance SE will be half of T, since each motion is half the length of the preceding NE motion. Similarly, the total distance SW will be one quarter of $T$; total distance NW will be one eighth of $T$. Each of these motions contributes the same component in the $x$-direction as in the $y$-direction. The NE direction counts positively towards both $x$ and $y$ directions, the SE direction counts positively in the $x$ direction and negatively in the $y$ direction, SW counts negatively in both $x$ and $y$ directions and NW counts negatively in the $x$ and positively in the $y$ direction. The final coordinates are therefore

  \[ (x,y)=\left(\frac{T}{\sqrt {2}}\left(1+\frac{1}{2}-\frac{1}{4}-\frac{1}{8}\right),\frac{T}{\sqrt {2}}\left(1-\frac{1}{2}-\frac{1}{4}+\frac{1}{8}\right)\right)=\left(\frac{9T}{8\sqrt {2}},\frac{3T}{8\sqrt {2}}\right) \]    

This problem comes from our sister site NRICH, which is packed with challenges, activities and articles for maths learners and teachers.

Back to puzzle