Computer Science 1
Part of the Oxford MAT Livestream.
MAT questions
MAT 2007 Q7
Suppose we have a collection of tiles, each containing two strings of letters, one above the other. A match is a list of tiles from the given collection (tiles may be used repeatedly) such that the string of letters along the top is the same as the string of letters along the bottom. For example, given the collection
\begin{equation*}
\left\{ \,\left[
\begin{array}{c}
\mathsf{AA} \\ \hline
\mathsf{A}
\end{array}
\right] ,\,\left[
\begin{array}{c}
\mathsf{B} \\ \hline
\mathsf{ABA}
\end{array}
\right] ,\,\left[
\begin{array}{c}
\mathsf{CCA} \\ \hline
\mathsf{CA}
\end{array}
\right] \,\right\} \,,
\end{equation*}
the list
\begin{equation*}
\left[
\begin{array}{c}
\mathsf{AA} \\ \hline
\mathsf{A}
\end{array}
\right] \,\left[
\begin{array}{c}
\mathsf{B} \\ \hline
\mathsf{ABA}
\end{array}
\right] \,\left[
\begin{array}{c}
\mathsf{AA} \\ \hline
\mathsf{A}
\end{array}
\right]
\end{equation*}
is a match since the string $\mathsf{AABAA}$ occurs both on the top and bottom.
Consider the following set of tiles:
\begin{equation*}
\left\{ \,\left[
\begin{array}{c}
\mathsf{X} \\ \hline
\mathsf{U}
\end{array}
\right] ,\,\left[
\begin{array}{c}
\mathsf{UU} \\ \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] ,\,\left[
\begin{array}{c}
\mathsf{Y} \\ \hline
\mathsf{U}
\end{array}
\right] ,\,\left[
\begin{array}{c}
\mathsf{Z} \\ \hline
\mathsf{Y}
\end{array}
\right] \,\right\} \,.
\end{equation*}
(i) What tile must a match begin with?
(ii) Write down all the matches which use four tiles (counting any repetitions).
(iii) Suppose we replace the tile $\left[
\begin{array}{c}
\mathsf{E} \\ \hline
\mathsf{ZE}
\end{array}
\right] $ with $\left[
\begin{array}{c}
\mathsf{E} \\ \hline
\mathsf{ZZZE}
\end{array}
\right] $.
What is the least number of tiles that can be used in a
match?
How many different matches are there using this smallest numbers of tiles?
[Hint: you may find it easiest to construct your matches backwards from right to left.]
Consider a new set of tiles $\left\{ \,\left[
\begin{array}{c}
\mathsf{XXXXXXX} \\ \hline
\mathsf{X}
\end{array}
\right] ,\,\left[
\begin{array}{c}
\mathsf{X} \\ \hline
\mathsf{XXXXXXXXXX}
\end{array}
\right] \,\right\} $. (The first tile has seven $\mathsf{X}$s on top, and the second tile has ten $\mathsf{X}$s on the bottom.)
(iv) For which numbers $n$ do there exist matches using $n$ tiles? Briefly justify your answer.
Hints
(i) How would the string of letters above and below the line start?
(ii) How does the sequence of tiles end? What comes before that?
(iii) Work backwards; how are you going to balance out the $\mathsf{ZZZ}$? At first, you should aim to find one example of a matching set of tiles, but try to keep track of your choices along the way.
Note that $\mathsf{X}$ and $\mathsf{Y}$ are neatly interchangeable in the tiles; you can change all the tiles with $\mathsf{X}$ for tiles with $\mathsf{Y}$ tiles in your sequence and nothing goes wrong.
(iv) What would the string of letters above and below the line look like? Now add more precision; how many letters would there be?
Giving names to things or numbers is a good way to start to turn words into maths. You're aiming for a relationship between the number of each sort of tile in your sequence of tiles.
MAT 2008 Q7
Ox-words are sequences of letters $a$ and $b$ that are constructed according to the following rules:
I. The sequence consisting of no letters is an Ox-word.
II. If the sequence $W$ is an Ox-word, then the sequence that begins with $a$, followed by $W$ and ending in $b$, written $aWb$, is an Ox-word.
III. If the sequences $U$ and $V$ are Ox-words, then the sequence $U$ followed by $V$, written $UV$, is an Ox-word.
All Ox-words are constructed using these rules. The length of an Ox-word is the number of letters that occur in it. For example $aabb$ and $abab$ are Ox-words of length 4.
(i) Show that every Ox-word has an even length.
(ii) List all Ox-words of length 6.
(iii) Let $W$ be an Ox-word. Is the number of occurrences of $a$ in $W$ necessarily equal to the number of occurrences of $b$ in $W$? Justify your answer.
You may now assume that every Ox-word (of positive length) can be written uniquely in the form $aWbW^{\prime }$ where $W$ and $W^{\prime }$ are Ox-words.
(iv) For $n\geqslant 0$, let $C_{n}$ be the number of Ox-words of length $2n$. Find an expression for $C_{n+1}$ in terms of $C_{0},C_{1},\cdots ,C_{n}$. Explain your reasoning.
Hints
(i) Where do Ox-words come from? Try to make an Ox-word with 3 letters. Why is that impossible?
(ii) Start by making Ox-words of length 2 and then of length 4. Try to work systematically as you apply rules.
(iii) It's true for all the Ox-words you've found so far!
(iv) $C_{n+1}$ refers to Ox-words of length $2n+2$. If that's of the form $aWbW'$, how long are the Ox-words $W$ and $W'$? They don't have to be the same length, so there are several possibilities.
Your expression might involve $+\dots$ (plus dot dot dot) or some sort of a sum. It's OK to leave it in either form if it's clear what the terms that you're adding are.
Extension
[Just for fun, not part of the MAT question]
- Explain why, if you write out an Ox-word from left to right, at no point have you written more $b$s than $a$s.
Explain why any such sequence of $a$s and $b$s is an Ox-word.
Prove that every Ox-word of positive length can be written uniquely in the form $aWbW'$ where $W$ and $W'$ are Ox-words.
MAT 2009 Q7
Consider sequences of the letters M, X and W. Valid sequences are made up according to the rule that an M and a W can never be adjacent in the sequence. So M, XMXW, and XMMXW are examples of valid sequences, whereas the sequences MW and XWMX are not valid.
(i) Clearly, there are 3 valid sequences of length 1. List all valid sequences of length 2.
(ii) Let $g(n)$ denote the number of valid sequences of length $n.$ Further, let $m(n)$, $x(n)$, $w(n)$ denote the number of valid sequences of length $n$ that start with an M, an X, a W respectively.
Explain why
\begin{eqnarray*}
m\left( n\right) &=&w\left( n\right) , \\
m\left( n\right) &=&m\left( n-1\right) +x\left( n-1\right) \quad \text{for }
n>1, \\
x\left( n\right) &=&2m\left( n-1\right) +x\left( n-1\right) \quad \text{for }
n>1,
\end{eqnarray*}
and write down a formula for $g\left( n\right) $ in terms of $m\left(n\right) $ and $x\left( n\right) .$
Hence compute $g(3)$, and verify that $g(4)=41$.
(iii) Given a sequence using these letters then we say that it is reflexive if the following operation on the sequence does not change it: reverse the letters in the sequence, and then replace each occurrence of M by W and vice versa. So MXW, WXXM and XWXMX are reflexive strings, but MXM and XMXX are not. Let $r(n)$ be the number of valid, reflexive sequences of length $n$.
If a sequence is reflexive and has odd length, what must the middle letter be? Explain your answer.
Hence, show that
\begin{equation*}
r\left( n\right) =\left\{
\begin{array}{cc}
\displaystyle x\left( \frac{n+1}{2}\right) & \text{if }n\text{ is odd,} \\
\displaystyle x\left( \frac{n}{2}\right) & \text{if }n\text{ is even.}
\end{array}
\right.
\end{equation*}
Hints
(i) Don't take their word for it; list all three one-letter valid sequences.
Without the rule about M and W not being adjacent, how many two-letter sequences would there be? That's not that many. List all of them systematically, then cross out the ones that don't work.
(ii) The first equality says that there are the same number starting with M as there are starting with W. A good way to prove that two sets are equal in size is to describe a one-to-one correspondence between the elements of the sets.
If a valid sequence starts with an M, what's the next letter? There are two possibilities.
If a valid sequence starts with an X, what's the next letter? Don't worry if your equality doesn't immediately match the equality in the question; focus on writing down a true fact, and then try to work out how to manipulate it into the form of the equality in the question.
Remember that $g(n)$ is the total number of valid sequences.
To compute $g(3)$, you'll need the values of $m(3)$ and $x(3)$, and to find those you'll need $m(2)$ and $x(2)$. Remember that you did some work in part (i).
(iii) What happens to the middle letter of an odd sequence when you reverse the sequence? What happens to that letter if you replace each M with W and vice versa (it depends on the letter)? Could this end up being the same sequence?
If a sequence is reflexive, then you can work out the second half of the sequence from the first half (more or less; I'm being a bit flexible with the word "half"). Can you see how? Note that if the sequence is valid then the first half of the sequence is valid.
Extension
[Just for fun, not part of the MAT question]
- List the values of $(x(n),m(n))$ for small values of $n$.
Have you seen any of these pairs of numbers before? - Suppose that
$$m(n)=\frac{\sqrt{2}}{4}\left(\left(1+\sqrt{2}\right)^n-\left(1-\sqrt{2}\right)^n\right)\quad\text{and }\quad x(n)=\frac{1}{2}\left(\left(1+\sqrt{2}\right)^n+\left(1-\sqrt{2}\right)^n\right).$$
Check that this is consistent with the values you found in part (i) and the relationships you found in part (ii).
Deduce a closed-form expression for $g(n)$ in terms of $n$.
MAT 2013 Q7
AB-words are "words" formed from the letters A and B according to certain rules. The rules are applied starting with the empty word, containing no letters. The basic rules are:
(1) If the current word is $x$, then it can be replaced with the word that starts with A, followed by $x$ and ending with B, written AxB.
(2) If the current word ends with B, the final B can be removed.
(i) Show how the word AAAB can be produced.
(ii) Describe precisely all the words that can be produced with these two rules. Justify your answer. You might like to write A$^i$ for the word containing just $i$ consecutive copies of A, and similarly for B; for example A$^3B$^2$=AAABB.
We now add a third rule:
(3) Reverse the word, and replace every A by B, and every B by A.
For example, applying this rule to AAAB would give ABBB.
(iii) Describe precisely all the words that can be produced with these three rules. Justify your answer.
Finally, we add a fourth rule:
(4) Reverse the word.
(iv) Show that every word consisting of As and Bs can be formed using these four rules. Hint: show how, if we have produced the word $w$, we can produce (a) the word Aw, and (b) the word Bw; hence deduce the result.
Hints
(i) We have to start with the empty word, and we can't remove B from that, so our first move is going to have to be to write A$x$B with $x$ the empty word, giving us AB.
(ii) Can you adapt what you did in the previous part? How many times would you apply rule (1)? How many times would you apply rule (2)? Can you make any number of As and also any number of Bs?
(iii) What happens if you apply the new rule to words that you made before? Can you now make any word? (probably not, since the next part introduces a new rule and asks you to show that every word can be formed with those four rules)
(iv) There's a hint in the question that says we should think about making A$w$ and B$w$. How do we make A$w$ with rules (1) and (2)?
To make B$w$, some sort of switching needs to happen (with rule (3), probably).
What happens if we apply rule (3) and then rule (4)?