Computer Science 1 Solutions

MAT 2007 Q7

(i) The first letter must match, so the first tile must be $\left[\begin{array}{c}\mathsf{UU} \\ \hline\mathsf{U}\end{array}\right]$ (that's the only tile where the first letter matches above and below).

(ii) The last tile must be $\left[\begin{array}{c}\mathsf{E} \\ \hline\mathsf{ZE}\end{array}\right]$ because the last letter must match (the $\left[\begin{array}{c}\mathsf{UU} \\ \hline\mathsf{U}\end{array}\right]$ tile is no good, because we would end up with too many letters on the top). Before that last tile, we need something with $\mathsf{Z}$ upstairs, and there are two possibilities; $\left[\begin{array}{c}\mathsf{Z} \\ \hline\mathsf{X}\end{array}\right]$ and $\left[\begin{array}{c}\mathsf{Z} \\ \hline\mathsf{Y}\end{array}\right]$. Before that, completing our set of four tiles, we need something with a $\mathsf{U}$ downstairs (to balance out the extra $\mathsf{U}$ from the first tile) and either an $\mathsf{X}$ or a $\mathsf{Y}$ downstairs to balance out the third tile. Both of those exist, so we conclude that our possible lists are
\begin{equation*}
\left[\begin{array}{c}\mathsf{UU} \\ \hline\mathsf{U}\end{array}\right]
\left[\begin{array}{c}\mathsf{X} \\ \hline\mathsf{U}\end{array}\right]
\left[\begin{array}{c}\mathsf{Z} \\ \hline\mathsf{X}\end{array}\right]
\left[\begin{array}{c}\mathsf{E} \\ \hline\mathsf{ZE}\end{array}\right]
\quad\text{and}\quad
\left[\begin{array}{c}\mathsf{UU} \\ \hline\mathsf{U}\end{array}\right]
\left[\begin{array}{c}\mathsf{Y} \\ \hline\mathsf{U}\end{array}\right]
\left[\begin{array}{c}\mathsf{Z} \\ \hline\mathsf{Y}\end{array}\right]
\left[\begin{array}{c}\mathsf{E} \\ \hline\mathsf{ZE}\end{array}\right].
\end{equation*}

(iii) We've got to balance out those three $\mathsf{Z}$, so we'll need three of those tiles with a $\mathsf{Z}$ upstairs. Each of those introduces a single letter downstairs, which we'll have to balance out with one of the $\left[\begin{array}{c}\mathsf{X} \\ \hline\mathsf{U}\end{array}\right]$ or $\left[\begin{array}{c}\mathsf{Y} \\ \hline\mathsf{U}\end{array}\right]$ tiles as appropriate. Then we'll have an extraneous three $\mathsf{U}$s downstairs, which we can most quickly balance out with three of the $\left[\begin{array}{c}\mathsf{UU} \\ \hline\mathsf{U}\end{array}\right]$ tiles. That's a total of ten tiles.

There are 8 ways that we might deal with the three $\mathsf{Z}$s, and each of those has a precise sequence of $\left[\begin{array}{c}\mathsf{X} \\ \hline\mathsf{U}\end{array}\right]$ or $\left[\begin{array}{c}\mathsf{Y} \\ \hline\mathsf{U}\end{array}\right]$ tiles that balances out the resulting letters below the line. So there are exactly eight different matches using 10 tiles.

(iv) Suppose we have $a$ copies of the first tile and $b$ copies of the second tile. We'll end up with a lot of $\mathsf{X}$s upstairs and downstairs; to be precise, we'll have $7a+b$ upstairs and $a+10b$ below. We want these to be equal, so $6a=9b$, so $2a=3b$. So $a$ is a multiple of $3$. Let's write $a=3k$ where $k$ is a whole number. Then $b=2k$. The total number of tiles is $a+b=3k+2k=5k$. So the total number of tiles must be a multiple of 5.

If $n$ is a multiple of 5, then write $n=5k$ and use that value of $k$ to decide how many of each tile to use; $3k$ of the first and $2k$ of the second. Those match together in any order.

MAT 2008 Q7

(i) Zero is even, and then other Ox-words are made from shorter Ox-words. It's either an Ox-word with two extra letters, or it's two Ox-words, one after the other. Either way, even plus even is even, so the number of letters in the new Ox-word is even.

(ii) First make all 2-letter words. That's just $ab$. Then to make a word of length four, we can add use rule II again to make $aabb$, or we could use rule III on $ab$ and another $ab$ to make $abab$.

To make a word of length 6 from either a word of length 4 with rule II, or from a word of length 4 and a word of length 2 in some order, combined with length 6. So the words are $aaabbb$ and $aababb$ and $(aabb)ab$ and $(abab)ab$ and $ab(aabb)$.

(iii) Yes. The sequence with no letters has equal numbers of $a$s and $b$s. Then other Ox-words are made from shorter Ox-words using rules II and III>

For rule II, one $a$ is added and one $b$ is added, so if $W$ had equal numbers of $a$s and $b$s, then so does $aWb$.

For rule III, if $U$ and $V$ each have an equal number of $a$s and $b$s then so does $UV$.

(iv) $W$ and $W'$ could be anything with total length $2n$, and with each being even in length. So $C_{n+1}=C_0 C_{n}+C_1C_{n-1}+\dots +C_{n-1}C_1+C_{n}C_0$.

Extension

That's true for the empty word (I've never written any $b$s at all!). If an Ox-word is made from two Ox-words $U$ and $V$, then the $b$s are never ahead while you write out $U$, and once you've written out $U$ that's got the same number of $a$s and $b$s in it, so from now on the $b$s can only get ahead if they're ahead while you write out $V$, and they're not. If an Ox-word is made from $aWb$ then the $b$s really don't stand a chance; the $a$s take an early lead, then the $b$s can't overtake during the Ox-word $W$, then finally there's one $b$ to balance things out at the end.

For a sequence where the $b$s are never ahead of the $a$s, identify whether there are any times while you're writing out the word when there are equal numbers of $a$s and $b$s. If so, this is of the form $UV$ where $U$ and $V$ are smaller sequences, in each of which the $b$s don't get ahead, so those are shorter Ox-words. If that never happens, then there's always at least one more $a$ than $b$ until the very end, so this is $aWb$ for some shorter sequence $W$ with the same property, so $W$ is an Ox-word.

Identify the first time where the number of $a$s is equal to the number of $b$s (this might be right at the end of the Ox-word). The sequence up to that point is $aWb$ for some Ox-word $W$, and the sequence after that point is $W'$ for some Ox-word, because of the way the $b$s never catch up with the $a$s discussed above.

MAT 2009 Q7

(i) There are at most nine, because there are three choices of letter. Valid sequences are MM WW XX MX XM WX XW XX (MW and WM are the only ones not valid).

(ii) $m(n)=w(n)$ because for each sequence starting with an M, we can switch all the Ms and Ws to get a sequence starting with W (and vice versa).

For $n>1$, $m(n)$ is the number of valid sequences starting with M. The next letter in the sequence is either M or X (not W), and the sequence after the first letter must itself be valid. Those cases are mutually exclusive, so we should add the number of valid sequences in each case for $m(n)$. So $m(n)=m(n-1)+x(n-1)$.

Similarly, if a sequence starts with X then the next letter could be X or M or W. So $x(n)=x(n-1)+m(n-1)+w(n-1)$. Remember that $m(n-1)=w(n-1)$ because of what we said above (and because $n>1$ here), so the right-hand side here is the same thing as $2m(n-1)+x(n-1)$.

The number $g(n)$ is the total, and sequences either start with M or X or W, so $g(n)=m(n)+x(n)+w(n)$. Remember that $m(n)=w(n)$, so $g(n)=2m(n)+x(n)$.

$g(3)=2m(3)+x(3)$ and we have $m(3)=m(2)+x(2)$ and $x(3)=2m(2)+x(2)$.

Then $m(2)=2$ and $x(2)=3$ from part (i) where we explicitly listed them. So $m(3)=5$ and $x(3)=7$ so $g(3)=17$.

We also have $g(4)=2m(4)+x(4)$ and $m(4)=m(3)+x(3)$ and $x(4)=2m(3)+x(3)$. So $m(4)=12$ and $x(4)=17$ and $g(4)=41$.

(iii) The middle letter of an odd sequence doesn't get changed by the reversal, and then a change from M to W or vice versa would change it. So for this sequence to be reflexive, the "middle" letter must be X.

So if $n$ is odd then the sequence to the right of the middle letter has $\frac{n-1}{2}$ letters and must be valid (there are $x\left(\frac{n-1}{2}\right)$ such sequences). The sequence to the left must be the reverse of the string on the right, but with M and W switched.

If $n$ is even then my first guess is that any sequence for the right half gives a reflexive sequence (if we choose the left half to match), but then I realise that if my sequence-on-the-right starts with M or W then when I reflect and switch, I'll end up with M and W next to each other in the middle. So I want the sequence-on-the-right to be valid and to start with X. There are $x(n/2)$ such sequences.

Extension

For $n=2$, $3$, $4$, I get $(x,m)$ equal to $(3,2)$ and $(7,5)$ and $(17,12)$. I've seen $(3,2)$ and $(17,12)$ before in MAT 2008 Q2 on the Sequences worksheet.
I have $$g(n)=\frac{1}{2}\left(\left(1+\sqrt{2}\right)^{n+1}+\left(1-\sqrt{2}\right)^{n+1}\right).$$

MAT 2013 Q7

(i) I want three As, so I'm going to apply rule (1) three times starting with the empty word, to get AAABBB. Then I'll remove the final B twice, using rule (2).

(ii) The As always go on the front, and the Bs always go on the end, so I'm always going to make something of the form A$^i$B$^j$. When I do the A$x$B rule I add one A and one B, and there's a separate rule that removes a B. So I can only ever have as many Bs as I have As. I can therefore only make things of the form A$^i$B$^j$ with $j\leq i$. I should check that I can make all of these; just like in part (i) I'll apply the A$x$B rule $i$ times and then the remove-the-final-B rule $i-j$ times (which might be zero times, but is definitely not negative because $j\leq i$).

(iii) If I apply this new rule I still get something of the form A$^i$B$^j$ (the Bs move to the front when I reverse, but then all the Bs are replaced by As!). Previously I could make anything of the form A$^i$B$^j$ with $j\leq i$. If I simply apply the new rule to this, I can make A$^i$B$^j$ for any $i$ and $j$ with $j\geq i$ ("more As at the start" becomes "more Bs at the end"). So with this addition I can now make any word of the form A$^i$B$^j$ with no restriction on $i$ and $j$; if $j\leq i$ then make it like in (ii) and otherwise make $A$^j$B$^i$ then apply the new rule.

(iv) Following the hint, I'll aim to make A$w$ and B$w$. The first is relatively straightforward; I can do that just with rules (1) and (2), first using rule (1) to add an A to the front and a B to the end, and then using rule (2) to immediately remove that B that I didn't really want from the end.

To make B$w$ I'll need to do some reversing. I think that I'd like to transform $w$ somehow, then add an A to the front, then transform again to turn that B into an A. That last transformation sounds like reverse-and-switch to me. So my plan is something like reverse-and-switch $w$, then put an A on the front, then reverse-and-switch. But that would give me $w$B, and even if I reverse that I get B followed by the reverse of $w$ which is not quite what I wanted. So I'll start by reversing $w$ so that when it comes out the end it's been reversed four times (not three) and is back to normal.

My answer then, is to apply

rule (4) to give the reverse of $w$ then rule (3) to give $w$ forwards, with As and Bs switched
rule (1) then rule (2) to give A$x$ where $x$ is $w$ with the As and Bs switched
rule (3) then rule (4) to give B$w$.

So to make any word with $n$ letters, look at the $n-1$ letters after the first, make that word, then follow the steps above to add an initial A or B as appropriate. This lets us build up from short words to long words.