A word is a string of arbitrary length consisting of the letters

MATHEMATICS · Multi-part · AoPS · Mathematics · Follow the Rules · Follow the Rules

Problem

A word

w

is a string of arbitrary length consisting of the letters

a, b, c

. If

w

and

v

are words, then we write

wv

for their concatenation. For example, if

w = aba

and

v = caa

then

wv = abacaa

. We create a set

\mathcal{L}

of allowable words (we write

w \in \mathcal{L}

to mean that

w

is a word in our language) via just the following rules: - (a)

a, b \in \mathcal{L}

; - (b) if

w \in \mathcal{L}

then so is

cw

; - (c) if

w

and

v

are words such that

wv \in \mathcal{L}

and

w

has length at least 1, then

vwv \in \mathcal{L}

; - (d) if

aw \in \mathcal{L}

then

wb \in \mathcal{L}

. For example,

a, cca, acca, ccab

are all in

\mathcal{L}

by the rules. We call a word

w

a palindrome if the word looks the same forwards or backwards, including single-letter words. So for example,

a, aba, acbbca

are all palindromes, but

cb, abc, abbbac

are not. (1) What is the number of palindromes in

\mathcal{L}

that contain both

a

and

b

with length 10? (2) What are some observations you made about the words in

\mathcal{L}

? (3) Can you prove your observations?