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.

The Computer Laboratory

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 oi.foo[email protected]. Please do not write to this address regarding general admissions or course queries.