A particular robot has three commands:

  • \(\mathbf{F}\): Move forward a unit distance;
  • \(\mathbf{L}\): Turn left \(90^{\circ}\);
  • \(\mathbf{R}\): Turn right \(90^{\circ}\).

A program is a sequence of commands. We consider particular programs \(P_n\) (for \(n \ge 0\)) in this question. The basic program \(P_0\) just instructs the robot to move forward: \[P_0 = \mathbf{F}.\]

The program \(P_{n+1}\) (for \(n \ge 0\)) involves performing \(P_n\), turning left, performing \(P_n\) again, then turning right: \[P_{n+1}= P_n\, \mathbf{L}\, P_n\, \mathbf{R}.\]

So, for example, \(P_{1} = \mathbf{F\, L\, F\, R}\).

  1. Write down the program \(P_2\).
By the (recursive) definition of \(P_n\), \[\begin{align*} P_2 = P_1\,\mathbf{L}\,P_1\,\mathbf{R}&=\mathbf{(F\,L\,F\,R)\,L\,(F\,L\,F\,R)\,R}\\ &=\mathbf{F\,L\,F\,R\,L\,F\,L\,F\,R\,R}. \end{align*}\]
  1. How far does the robot travel during the program \(P_n\)? In other words, how many \(\mathbf{F}\) commands does it perform?

Let the number of \(\mathbf{F}\) commands in \(P_n\) be \(f_n\). Then since \(P_{n+1} = P_n\,\mathbf{L}\,P_n\,\mathbf{R}\), we have \(f_{n+1} = 2f_n\). As \(f_0 = 1\), this gives \(f_n = 2^n\).

  1. Let \(l_n\) be the total number of commands in \(P_n\); so, for example, \(l_0 = 1\) and \(l_1 = 4\). Write down an equation relating \(l_{n+1}\) to \(l_n\). …

If \(l_n\) is the total number of commands in \(P_n\), then since \(P_{n+1} = P_n\,\mathbf{L}\,P_n\,\mathbf{R}\), we have \[l_{n+1} = l_n + 1 + l_n + 1 = 2l_n + 2.\]

… Hence write down a formula for \(l_n\) in terms of \(n\). No proof is required. Hint: consider \(l_n + 2\).

Let \(L_n = l_n+2\), following the suggestion. Using our formula for \(l_n\), we find \[L_{n+1} = l_{n+1}+2=2l_n+2+2=2L_n,\] and therefore, \[L_n = 2^n L_0.\]

We are given \(l_0 = 1\), so \(L_0 = 3\), so \[L_n = 3 \times 2^n.\]

Then as \(l_n=L_n-2\), we get \[l_n = 3 \times 2^n - 2.\]

Check: for \(n=2\), this gives \(l_2=3\times4-2=10\), which tallies.

  1. The robot starts at the origin, facing along the positive \(x\)-axis. What direction is the robot facing after performing the program \(P_n\)?

Since \(P_0\) contains only an \(\mathbf{F}\), we see that each program \(P_n\) contains an equal number of \(\mathbf{L}\) and \(\mathbf{R}\) commands.

Therefore the robot will still face along the positive \(x\)-axis after completing \(P_n\).

  1. The first diagram below shows the path the robot takes when it performs the program \(P_1\). On the second (blank) diagram, draw the path it takes when it performs the program \(P_4\).

It helps to work out the paths for \(P_2\) and \(P_3\).

the paths for P 2 and P 3

To find \(P_3\), we do \(P_2\), then turn to north and repeat \(P_2\).

To find \(P_4\), we do \(P_3\), then turn to north and repeat \(P_3\). This gives us

Path given by P4, which ends at (-4,0)

Four copies of \(P_2\) are clearly visible, as are 8 copies of \(P_1\).

  1. Let \((x_n, y_n)\) be the position of the robot after performing the program \(P_n\), so \((x_0, y_0) = (1,0)\) and \((x_1, y_1) = (1,1)\). Give an equation relating \((x_{n+1}, y_{n+1})\) to \((x_n, y_n)\).

We have the relationship \[P_{n+1} = P_n\,\mathbf{L}\,P_n\,\mathbf{R}.\]

Originally the robot is at the origin facing east. Performing \(P_n\) takes the robot to \((x_n,y_n)\) still facing east.

The move \(\mathbf{L}\) turns the robot left \(90^\circ\), so it then faces north.

Now imagine the robot is at the origin but facing north. Performing \(P_n\) moves the robot to position \((-y_n, x_n)\).

So facing north and performing \(P_n\) will translate the robot by the vector \(\dbinom{-y_n}{x_n}\).

So starting at the origin and facing east, after performing \(P_n\,\mathbf{L}\,P_n\), the robot will be at position \((x_n - y_n, y_n + x_n)\).

This position is obviously unchanged by performing the final \(\mathbf{R}\).

Therefore \[(x_{n+1},y_{n+1}) = (x_n - y_n, x_n + y_n).\]

What is \((x_8, y_8)\)? What is \((x_{8k}, y_{8k})\)?

By using the relationship we have just established, we find that \[\begin{align*} (x_{n+2},y_{n+2}) &{}= (x_{n+1} - y_{n+1}, x_{n+1} + y_{n+1}) \\ &{}= (x_n - y_n - x_n -y_n, x_n -y_n +x_n + y_n) \\ &{}= (-2y_n, 2x_n). \end{align*}\] Therefore, \[\begin{align*} (x_{n+4},y_{n+4}) &{}= (-2y_{n+2}, 2x_{n+2})\\ &{}= (-4x_n, -4y_n) \end{align*}\] and so \[\begin{align*} (x_{n+8},y_{n+8}) &{}= (-4x_{n+4}, -4y_{n+4})\\ &{}= (16x_n, 16y_n). \end{align*}\]

Setting \(n=0\) in the final expression gives \[(x_8, y_8) = (16x_0, 16y_0) = (16,0),\] and we can also see from the final expression that \[(x_{8k}, y_{8k}) = (16^k,0).\]

The program Logo is perfect for trying out programs involving F, L and R. Search on the internet to find a free download.