 # Practice Paper 3 Question 14

The Seesat language has the single-letter word $$A.$$ Longer words are built by applying a sequence of the following rules: Rule $$r_1$$ says that if $$x$$ is a word then $$Ax$$ is a word; Rule $$r_2$$ says that if $$x$$ and $$y$$ are words then $$Bxy$$ is a word. For example, the sequence $$r_1(r_2(A,A))$$ yields the word $$ABAA.$$

1. Give a valid sequence of rules that yields the word $$AAABBAAA.$$
2. Write $$N_A (x)$$ and $$N_B(x)$$ for the number of $$A$$ and $$B$$ letters in the word $$x$$ respectively. By expressing $$N_A(x)$$ and $$N_B(x)$$ in connection with the rules, prove mathematically that $$N_A(x) > N_B(x)$$ for any word $$x$$ in the language.

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

## Warm-up Questions

1. Prove, by mathematical induction, that $$\sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6}.$$

## Hints

• Hint 1
In simple terms, what do rule $$r_1$$ and $$r_2$$ do?
• Hint 2
How many times should you apply rule $$r_2$$ to get $$AAABBAAA?$$
• Hint 3
If $$x$$ is a word in the language, express $$N_A(r_1(x))$$ in terms of $$N_A(x).$$
• Hint 4
Similarly, find $$N_B(r_1(x)),$$ $$N_A(r_2(x,y))$$ and $$N_B(r_2(x,y)),$$ with $$y$$ being another word in the language.
• Hint 5
What assumption do you need to make in order to claim that $$N_A(r_1(x)) > N_B(r_1(x))$$ and $$N_A(r_2(x,y)) > N_B(r_2(x,y))?$$
• Hint 6
Is your assumption valid? Hint: Consider $$N_A(A)$$ and $$N_B(A).$$
• Hint 7
Try proving by induction.
• Hint 8
... more specifically, induction over each of the rules.

## Solution

Starting with a single-letter word $$A,$$ the rules allow us to create new words from existing ones. Rule $$r_1$$ lets us add an $$A$$ in front of a word, while rule $$r_2$$ combines two words and adds a $$B$$ in front. There are $$2$$ $$B$$s in $$AAABBAAA,$$ thus we must apply rule $$r_2$$ twice: first to have $$BAA,$$ then $$BBAAA.$$ Hence, the sequence of rule is $$r_1(r_1(r_1(r_2(r_2(A,A),A)))).$$

In order to prove that $$N_A(x) > N_B(x)$$ for any word $$x$$ in the language, we use induction over each of the rules. The base case is simple, $$N_A(A) = 1 > 0 = N_B(A).$$ For the inductive step, our assumption is that $$N_A(x) > N_B(x)$$ and $$N_A(y) > N_B(y),$$ for some words $$x$$ and $$y$$ in the language. We have to show that $$N_A(r_1(x)) > N_B(r_1(x))$$ and $$N_A(r_2(x,y)) > N_B(r_2(x,y)):$$

• $$r_1:$$ $$N_A(r_1(x)) = 1 + N_A(x) > N_B(x) = N_B(r_1(x))$$

• $$r_2:$$ $$N_A(r_2(x,y)) = N_A(x) + N_A(y) > 1 + N_B(x) + N_B(y) = N_B(r_2(x,y)).$$

Hence, $$N_A(x) > N_B(x)$$ for all words $$x$$ in the language.

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.tasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.