Happy new year!

How many strings of length 11 consisting only of the letters A A and B B are there that meet the following conditions?

  • They don't have exactly 8 consecutive same letters, either A A or B B .
  • They don't have exactly 9 consecutive A A 's.


The answer is 2019.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Henry U
Dec 31, 2018

There are a total of 2 11 = 2048 2^{11} = \boxed{2048} strings of length 11. We now have to subtract the strings that don't meet the conditions. In the following, I will refer to the repeated letters as the row .

There are 4 different places where exactly 8 consecutive same letters can occur; from position 1–8, 2–8, 3–10 or 4–11, and 2 choices for the letter in the row. For 1–8 and 4–11, the letter next to the row has to be different and for the two remaining letters, there are 2 2 = 4 2^2 = 4 choices, so for 1–8 and 4–11 there are 2 2 2 + 2 2 2 = 16 2 \cdot 2^2 + 2 \cdot 2^2 = \boxed{16} strings. For 2–9 and 3–10, the letter before and after the row have are fixed (so that the row ends there), but the remaining letter has 2 options, so there are a total of 2 + 2 = 4 2 + 2 = \boxed{4} sequences with the row at 2–9 or 3–10.

We now do the same for a row of exactly 9 A A 's. The row can be at 1–9, 2–10 or 3–11 and there are 2, 1 and 2 such sequences respectively, so a total of 2 + 1 + 2 = 5 2+1+2=\boxed{5} .

Therefore, and since both conditions can't happen at the same time, the overall number of strings that meet both conditions is

2048 16 4 5 = 2019 2048 - 16 - 4 - 5 = \boxed{\boxed{\huge 2019}}

H appy new Y ear!! \huge\mathbb{H}\text{appy new }\mathbb{Y}\text{ear!!}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...