Maths Olympiad Prep

Library / /13 of 15

Combinatorics Difficulty 6.8 National Olympiad Prove it Philippines

Problem:
A Vitas word is a string of letters that satisfies the following conditions:
- It consists of only the letters BB, LL, RR.
- It begins with a BB and ends in an LL.
- No two consecutive letters are the same.
How many Vitas words are there with 1111 letters?

Solution

Solution:
Let ana_n be the number of nn-letter Vitas words that start with BB and end with LL.

Let us generalize and define:
- ana_n: number of nn-letter words starting with BB and ending with LL.
- bnb_n: number of nn-letter words starting with BB and ending with RR.

We do not consider words ending with BB since the last letter cannot be BB (as the word must end with LL).

For n=2n = 2:
- The word must be BLBL (since it starts with BB and ends with LL), so a2=1a_2 = 1.
- The word BRBR is also possible, so b2=1b_2 = 1.

For n>2n > 2:
To form an nn-letter word ending with LL, the (n1)(n-1)-th letter must be RR (since no two consecutive letters are the same), so we append LL to any (n1)(n-1)-letter word ending with RR.
Thus,
an=bn1 a_n = b_{n-1}

Similarly, to form an nn-letter word ending with RR, the (n1)(n-1)-th letter must be LL, so
bn=an1 b_n = a_{n-1}

But, at each step, the letter can be LL or RR (but not the same as the previous letter), so we must also consider that after the first BB, the rest of the letters alternate between LL and RR.

But, since the alphabet is only BB, LL, RR, and the first letter is BB, the rest of the letters (positions 22 to nn) are LL or RR, with no two consecutive letters the same.

Let us define ana_n as above, and bnb_n as above.

From above:
an=bn1 a_n = b_{n-1}
bn=an1 b_n = a_{n-1}

With initial conditions:
a2=1a_2 = 1 (word BLBL), b2=1b_2 = 1 (word BRBR).

So,
a3=b2=1a_3 = b_2 = 1
b3=a2=1b_3 = a_2 = 1

a4=b3=1a_4 = b_3 = 1
b4=a3=1b_4 = a_3 = 1

So, for all n2n \geq 2, an=1a_n = 1, bn=1b_n = 1? But this cannot be, since the number should grow with nn.

Wait: Let's reconsider.

Let us define AnA_n as the number of nn-letter words starting with BB and ending with LL.
Let BnB_n as the number of nn-letter words starting with BB and ending with RR.

For n=2n = 2:
Possible words: BLBL, BRBR.
So A2=1A_2 = 1, B2=1B_2 = 1.

For n=3n = 3:
Words: BLRBLR, BRLBRL.
So A3=1A_3 = 1 (BRLBRL), B3=1B_3 = 1 (BLRBLR).

For n=4n = 4:
Words: BLRLBLRL, BRLRBRLR.
So A4=1A_4 = 1 (BLRLBLRL), B4=1B_4 = 1 (BRLRBRLR).

So, for each nn, An=1A_n = 1, Bn=1B_n = 1.

But for n=5n = 5:
Words: BLRLRBLRLR, BRLRLBRLRL.
So A5=1A_5 = 1 (BRLRLBRLRL), B5=1B_5 = 1 (BLRLRBLRLR).

So, for each nn, An=1A_n = 1.

But this cannot be, since the number should be larger for n=11n = 11.

Let us try to generalize differently.

Let us define f(n,x)f(n, x) as the number of nn-letter words starting with BB and ending with xx, where xx is LL or RR.

Let us consider the sequence of letters:
- The first letter is BB.
- The next n2n-2 letters are each LL or RR, with no two consecutive letters the same.
- The last letter is LL.

So, the word is Bx2x3xn1LB x_2 x_3 \ldots x_{n-1} L, where each xix_i is LL or RR, and xixi1x_i \neq x_{i-1} for i2i \geq 2.

Let us define g(k,y)g(k, y) as the number of sequences of length kk (positions 22 to n1n-1), starting with yy (LL or RR), with no two consecutive letters the same.

But perhaps it's easier to let SkS_k be the number of sequences of length kk (positions 22 to nn), with letters LL or RR, no two consecutive letters the same, and ending with LL.

Let aka_k be the number of such sequences of length kk ending with LL.
Let bkb_k be the number of such sequences of length kk ending with RR.

We want an1a_{n-1}, since the first letter is BB, and the rest is a sequence of n1n-1 letters, with the last letter LL, and no two consecutive letters the same.

The recurrence is:
- To get a sequence of length kk ending with LL, the previous letter must be RR, so ak=bk1a_k = b_{k-1}.
- To get a sequence of length kk ending with RR, the previous letter must be LL, so bk=ak1b_k = a_{k-1}.

With initial conditions:
For k=1k = 1:
- The sequence is just one letter, which can be LL or RR.
So a1=1a_1 = 1 (sequence LL), b1=1b_1 = 1 (sequence RR).

Then:
a2=b1=1a_2 = b_1 = 1
b_2 = a_1 = 1
a3=b2=1a_3 = b_2 = 1
b_3 = a_2 = 1

So, for all kk, ak=1a_k = 1, bk=1b_k = 1.

But this cannot be, since the number should grow with nn.

Wait, perhaps the error is in the initial conditions.

Let us try to write out all possible sequences for small nn.

For n=2n = 2:
- BLBL

For n=3n = 3:
- BLRBLR
- BRLBRL

For n=4n = 4:
- BLRLBLRL
- BRLRBRLR

For n=5n = 5:
- BLRLRBLRLR
- BRLRLBRLRL

So, for n=2n = 2, 11 word.
For n=3n = 3, 22 words.
For n=4n = 4, 22 words.
For n=5n = 5, 22 words.

Wait, but for n=6n = 6:
- BLRLRLBLRLRL
- BRLRLRBRLRLR

So, always 22 words for n3n \geq 3.

But for n=11n = 11:
- BLRLRLRLRLRBLRLRLRLRLR
- BRLRLRLRLRLBRLRLRLRLRL

So, the answer is 22.

Therefore, the number of Vitas words with 1111 letters is 22.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.