The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field. # Practice Paper 4 Question 20

The Csatian language has the following two rules: (i) $$B$$ is a word, and (ii) if $$x$$ is a word then $$BBBxxx$$ is a word.

1. Give an expression for the number of $$B$$s in a valid word.

2. Suggest a third rule (iii) such that all multiples of 3 $$B$$s are valid words, and the only other valid word is a single $$B.$$

3. Replace rule (iii) with the following: (iii) if $$BBBBx$$ is a word then $$x$$ is a word. Find all pairs $$(p,q)$$ such that, for all integers $$n\ge0,$$ the expression $$pn+q$$ gives the lengths of all valid words.

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

## Warm-up Questions

1. Find a closed form solution to the recurrence defined by $$a_0=5, a_{n+1}=2a_n+1.$$
2. The Climb language has two rules: (i) it contains the word $$AAAAAAAA,$$ and (ii) if $$xx$$ is a word, then $$x$$ is a word. Write down all the words in the language.
3. Give the possible values of $$b$$ in $$3 \cdot 2^i \equiv b \mod 12$$ for $$i \in \{0,1,2,3, \ldots\}.$$

## Hints

• Hint 1
(Part (a)) Find and solve a recurrence relation for the length of possible words.
• Hint 2
(Part (b)) What is the characteristic of the valid words described by rule (ii)?
• Hint 3
(Part (b)) ... in terms of their divisibility?
• Hint 4
(Part (b)) Rules (i) and (ii) only cover the case of a single $$B$$ and some multiples of 3 $$B$$s. How could rule (iii) cover all multiples of 3 $$B$$s, given that some multiples of 3 $$B$$s are valid words?
• Hint 5
(Part (b)) Could you modify rule (iii) given in part (c) to do so? Note: Sometimes, reading the next part of the question helps.
• Hint 6
(Part (c)) From the expression in part (a), find a new expression for the length of the valid words described by the new rule (iii).
• Hint 7
(Part (c)) If you subtract $$4k$$ from the words described by rule (ii), do you get all the naturals?
• Hint 8
(Part (c)) You should notice that by subtracting $$4k$$ from the words described by rule (ii), you are not guaranteed to get all naturals (why?). Which of those naturals are not possible? Try expressing them in a more general form.
• Hint 9
(Part (c)) Prove that the new expression you get earlier could not be equal to those naturals. Hint: It is sufficient to show that the expression is not equal to the base case of the naturals (why?).

## Solution

1. We use the recurrence relation $$l_i=3+3l_{i-1},$$ which unwinds to give us:\begin{align} l_i&= 3+ 3(3+3l_{i-2}) \\ &=3+3^2+3^2 \cdot l_{i-2} \\ &=\sum_{k=1}^{i}3^k + 3^{i}\cdot l_0 \\ &=\frac{3(3^{i}-1)}{2}+3^{i} \\ &=\frac{5\cdot3^i-3}{2}. \end{align}

2. Factorising $$3$$ from $$l_i$$ gives $$\frac{5\cdot3^{i-1}-1}{2},$$ whose numerator is divisible by $$2,$$ which means $$l_i$$ is a multiple of $$3.$$ Thus, if we want to obtain all multiples of $$3$$ as valid words, we can add a rule which subtracts $$3$$ $$B$$s from any valid word: "if $$BBBx$$ is a word then $$x$$ is a word".

3. You can write $$l'_i=\frac{5\cdot3^i-3}{2}-4n,$$ where $$i,n$$ are the number of applications of rule (ii) and (iii) respectively. But the question asks you to simplify this. From (a), $$l_i$$ is a multiple of $$3,$$ but it does not give all multiples of $$3.$$ Hence by subtracting $$4n$$ from it, you are not guaranteed to get all naturals, so it is not obvious which of the $$4k,4k+1,$$$$4k+2,4k+3$$ forms you can generate. The proof is in showing that $$4k$$ and $$4k+3$$ are not possible. One approach could be:

• Show that there do not exist any positive integers $$i,n$$ such that $$\frac{5\cdot3^i-3}{2}-4n=4:$$

Rearranging the given equation yields $$5 \cdot 3^i - 8n = (2 \cdot 4) + 3 = 11,$$ i.e. we require that $$5 \cdot 3^i \equiv 11 \mod 8$$. But for $$i = 0,1,2,3,4$$ we get $$3^i \equiv 1, 3, 1, 3.$$ This pattern repeats because:$3^i \equiv 1 \mod 8 \implies 3^{i+1} \equiv 1 \cdot 3 \equiv3 \mod 8 \\ 3^i \equiv 3 \mod 8 \implies 3^{i+1} \equiv 9 \equiv 1\mod 8$

Hence, $$3^i \in \{1,3\}$$ when taken $$\text{mod }8$$. Following that, $$5 \cdot 3^i$$ can only be $$5 \cdot 1 \equiv 5$$ or $$5 \cdot 3 \equiv 15 \equiv 7$$. Hence the equation can never be satisfied.

• Show that there do not exist any positive integers $$i,n$$ such that $$\frac{5\cdot3^i-3}{2}-4n=3:$$

Rearranging similarly, the problem becomes $$5\cdot 3^i \equiv 9 \mod 8$$. Using a similar argument as above, we get $$5 \cdot 3^i$$ is either $$5$$ or $$7$$ in $$\text{mod }8,$$ so the equation can never be satisfied.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at . Please do not write to this address regarding general admissions or course queries.