Grid or tree?
Tonight's idea
Let \(a\) mean "one step east" and \(b\) mean "one step north". A route is a word: \(aab\) is east, east, north. Since \(ab\) and \(ba\) end at the same corner, you may use the rule \(ba \to ab\): wherever a \(b\) stands just before an \(a\), swap them. Keep going and every word reaches its standard form, all the \(a\)s and then all the \(b\)s.
With the rule \(ab = ba\), two words end at the same position exactly when they have the same standard form.
So a question about routes is settled by mechanical rewriting, a job a computer does well.
Now allow the reverse moves \(A\) (undo \(a\)) and \(B\) (undo \(b\)). With \(ab = ba\) the positions are the corners of a grid. Next imagine two other moves, still called \(a\) and \(b\), that obey no rule at all except that a move and its reverse cancel. Then \(ab\) and \(ba\) are different positions, the only way back to an earlier position is to retrace your steps, and the map is a branching tree.
Watch one: sorting babba
Use the rule \(ba \to ab\) on the leftmost place it fits, and repeat until it fits nowhere.
\[ \underline{ba}bba \;\to\; abb\underline{ba} \;\to\; ab\underline{ba}b \;\to\; a\underline{ba}bb \;\to\; aabbb \]
Four steps, and the word is in standard form: \(aabbb\), two steps east and three north. The rule only swaps letters, so the count of each letter never changes: two \(a\)s and three \(b\)s throughout. Often the rule fits in several places at once. Exercise 2 shows that the choice does not matter.
Your turn
- Rewrite each word into standard form with the rule \(ba \to ab\), showing every step. (a) \(bab\) (b) \(abab\) (c) \(bbaa\) (d) Which two of these words end at the same position?
- For any word, let \(T\) be the number of pairs made of a \(b\) and an \(a\) that comes later in the word. The two letters need not be neighbours. For \(babba\), \(T = 4\). (a) Find \(T\) for \(abab\) and for \(bbaa\), and compare with your step counts in exercise 1. (b) Explain why one use of the rule lowers \(T\) by exactly 1. Why must the rewriting stop, and why is the word then in standard form? (c) Which four-letter word needs the most steps?
- Forward moves only, four letters. (a) How many words are there? (b) With the rule \(ab = ba\), list the standard forms. How many different positions is that? (c) How many of the words end at \(aabb\)? (d) Answer (a) and (b) again for words of \(n\) letters, then put \(n = 10\).
- Now the reverse moves \(A\) and \(B\) are allowed too. A position is two steps away when its shortest route from the start has two moves. (a) There are 16 two-letter words in \(a\), \(b\), \(A\), \(B\). Four of them cancel back to the start. Which? List the other 12. (b) On the tree those 12 are 12 different positions. On the grid, which of them meet? How many grid positions are two steps away? Check your totals against the picture. (c) Go one step further. How many positions are exactly three steps away on the grid, and on the tree? How many are within three steps?
Stretch: how fast do the maps grow?
Show that the number of positions within \(n\) steps of the start is \(2n^2 + 2n + 1\) on the grid and \(2 \times 3^n - 1\) on the tree. Then compare the two at \(n = 10\). Hints: first count the positions exactly \(k\) steps away, for \(k \ge 1\). Then use \(1 + 2 + \cdots + n = \tfrac{n(n+1)}{2}\) and \(1 + 3 + 9 + \cdots + 3^{n-1} = \tfrac{3^n - 1}{2}\).
Answers
- (a) \(bab \to abb\), one step. (b) \(abab \to aabb\), one step. (c) Four steps: \(bbaa \to baba \to abba \to abab \to aabb\). Other choices give other middle words, but always four steps. (d) Words (b) and (c): both have standard form \(aabb\).
- (a) In \(abab\) only the first \(b\) has an \(a\) after it, so \(T = 1\). In \(bbaa\) each of the two \(b\)s is before both \(a\)s, so \(T = 4\). These match the step counts. (b) The \(b\) and \(a\) that swap were a counted pair and now are not. They were neighbours, so neither of them passed any third letter, and every other pair of letters is in the same order as before. So \(T\) falls by exactly 1. \(T\) is a whole number and cannot go below 0, so after as many steps as the starting \(T\) the rule fits nowhere, whatever choices you made. If no \(b\) stands just before an \(a\), then every letter after the first \(b\) is a \(b\), which is the standard form. (c) \(bbaa\), with \(T = 4\). A word with only one \(a\) or only one \(b\) has \(T\) at most 3.
- (a) Two choices for each letter: \(2^4 = 16\). (b) \(aaaa\), \(aaab\), \(aabb\), \(abbb\), \(bbbb\): 5 positions. (c) Six of them: \(aabb\), \(abab\), \(abba\), \(baab\), \(baba\), \(bbaa\). In the same way 1, 4, 6, 4 and 1 words end at the five positions, and \(1 + 4 + 6 + 4 + 1 = 16\). (d) There are \(2^n\) words. A standard form is fixed by how many times \(a\) appears, which can be \(0, 1, \ldots, n\), so there are \(n + 1\) positions. For \(n = 10\) that is 1024 words but only 11 positions. With no rule at all, the 1024 words would be 1024 different positions.
- (a) \(aA\), \(Aa\), \(bB\) and \(Bb\) cancel. The other 12 are \(aa\), \(ab\), \(aB\), \(bb\), \(ba\), \(bA\), \(AA\), \(Ab\), \(AB\), \(BB\), \(Ba\), \(BA\). (b) On the grid \(ab = ba\), \(aB = Ba\), \(Ab = bA\) and \(AB = BA\). Four pairs merge, so \(12 - 4 = 8\) positions are two steps away. Within two steps: \(1 + 4 + 8 = 13\) on the grid and \(1 + 4 + 12 = 17\) on the tree, as in the picture. (c) Tree: from each of the 12 positions you can go on with any move except the reverse of the last one, so \(12 \times 3 = 36\). Grid: the positions three steps away are 3 one way, or 2 one way and 1 the other. That is \(4 + 8 = 12\). Within three steps: \(13 + 12 = 25\) on the grid and \(17 + 36 = 53\) on the tree.
Stretch. Grid: after sorting and cancelling, a position is some number of steps east or west and some number north or south, and its shortest route has that many moves in total. Exactly \(k\) away, count the positions with at least 1 step east and none south: east \(1, 2, \ldots, k\) and the rest north, which is \(k\) positions. Quarter turns give three more groups of \(k\), so \(4k\) in all. The total is \(1 + 4(1 + 2 + \cdots + n) = 1 + 2n(n+1) = 2n^2 + 2n + 1\). Tree: a position \(k\) steps away is a word of \(k\) letters with nothing to cancel. There are 4 choices for the first letter and 3 for each one after, so \(4 \times 3^{k-1}\). The total is \(1 + 4 \times \tfrac{3^n - 1}{2} = 2 \times 3^n - 1\). Both formulas also give 1 when \(n = 0\). At \(n = 10\) the grid has \(200 + 20 + 1 = 221\) positions and the tree has \(2 \times 59049 - 1 = 118{,}097\), over 500 times as many. Mathematicians study a set of rules by the shape of its map in just this way. Sorting worked tonight because the rule was simple. For some sets of rules it has been proved that no mechanical method can decide every case.