Problem of the Month
Hint for Problem 2: Manuals for Robots

1. Put your finger on the starting place (the square) and pretend you are the robot, following the arrows as they appear in each string. If you end at a finishing place (a shaded shape), the string is in the manual. If you don’t end at a finishing place, the string is not in the manual.

2. 1. Decide whether or not the following strings are in the manual: $$bbb,bbabb,bbabba,bbbbbabbbbb,bbbbbabbbabb.$$ What do you notice?

   2. Think about what it takes to move from the top row of places to the bottom row of places, and from the bottom row to the top row. Think about what it takes to move from the left column to the right column, and what it takes to move from the right column to the left column.

3. 1. First draw in the arrows and places corresponding to the desired finite set of words. Create another place that acts as a disposal site for the rest of the words. Make sure that once the robot is in that place, it can never get out!

   2. Think carefully about Course 1 from the first page of the problem, except pretend that the square is shaded instead of the circle.

4. 1. Suppose a string has length $3$. As the robot is travelling according to the instructions from the string, how many different places can the robot visit? What about if the string has length $1$? What if the string has length $k$?

   2. If a substring of a string returns the robot to a place it has already visited, what happens if you repeat that substring again?

   3. Use Part (b), and pay close attention to the lengths of the words $x{y}^{n}z$.

   4. Suppose there are $k$ places in a course, and $w$ is a string in the manual of length at most $k$. By Part (b), $w=xyz$. Can you put any restrictions on the length of $x$? If you can, see if you can cleverly select a palindrome $w$ so that when you write $w=xyz$ as in Part (b), $x{y}^{2}z$ is not a palindrome.