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 \[\left\{ \left[ \frac{\mathsf{AA}}{\mathsf{A}} \right], \left[ \frac{\mathsf{B}}{\mathsf{ABA}} \right], \left[ \frac{\mathsf{CCA}}{\mathsf{CA}} \right] \right\},\] the list \[\left[ \frac{\mathsf{AA}}{\mathsf{A}} \right]\quad \left[ \frac{\mathsf{B}}{\mathsf{ABA}} \right]\quad \left[ \frac{\mathsf{AA}}{\mathsf{A}} \right]\] is a match since the string \(\mathsf{AABAA}\) occurs both on the top and bottom.
Consider the following set of tiles: \[\left\{ \left[ \frac{\mathsf{X}}{\mathsf{U}} \right], \left[ \frac{\mathsf{UU}}{\mathsf{U}} \right], \left[ \frac{\mathsf{Z}}{\mathsf{X}} \right], \left[ \frac{\mathsf{E}}{\mathsf{ZE}} \right], \left[ \frac{\mathsf{Y}}{\mathsf{U}}\right], \left[ \frac{\mathsf{Z}}{\mathsf{Y}} \right] \right\}.\]
What tile must a match begin with?
Write down all the matches which use four tiles (counting any repetitions).
Suppose we replace the tile \(\left[ \dfrac{\mathsf{E}}{\mathsf{ZE}} \right]\) with \(\left[ \dfrac{\mathsf{E}}{\mathsf{ZZZE}} \right]\).
What is the least number of tiles that can be used in a match?
How many different matches are there using this smallest number 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[ \dfrac{\mathsf{XXXXXXX}}{\mathsf{X}} \right], \left[ \dfrac{\mathsf{X}}{\mathsf{XXXXXXXXXX}} \right] \right\}\). (The first tile has seven \(\mathsf{X}\)s on top, and the second tile has ten \(\mathsf{X}\)s on the bottom.)
- For which numbers \(n\) do there exist matches using \(n\) tiles? Briefly justify your answer.
