GATE 2025 CS1 Q.30: solution and answer

GATE 2025 · CS1Q.30 · 1 mark · NAT

Let $S$ be the set of all ternary strings defined over the alphabet ${a, b, c}$ . Consider all strings in $S$ that contain at least one occurrence of two consecutive symbols, that is, "aa", "bb" or "cc". The number of such strings of length 5 that are possible is ______. (Answer in integer)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The number of such strings is 195.

Official answer: 195Source: Official answer key, GATE 2025 CS1 (IIT Roorkee)

Count the complement: strings of length 5 over ${a, b, c}$ in which no two adjacent symbols are equal. Then answer $=$ total $-$ complement.
Total strings of length 5 over 3 symbols: $3^{5} = 243$ .
A string has none of "aa", "bb", "cc" exactly when every symbol differs from the one before it. The first symbol has 3 choices. Each later symbol must differ from its predecessor, so it has 2 choices.
Complement count $= 3 \times 2^{4} = 3 \times 16 = 48$ . Check on length 2: the formula gives $3 \times 2 = 6$ strings with no repeat (ab, ac, ba, bc, ca, cb), and $9 - 6 = 3$ strings (aa, bb, cc) do contain a repeat, which is correct.
Strings with at least one of "aa", "bb" or "cc" $= 243 - 48 = 195$ .

KEY IDEA

Count the complement. Strings with no two equal adjacent symbols number $3 \cdot 2^{n - 1}$ , because each new symbol has exactly 2 choices that differ from the previous one. Subtract this from $3^{n}$ .

WATCH OUT FOR

Counting strings containing "aa", "bb" or "cc" directly and adding the three counts. This double-counts strings that contain more than one repeat, such as "aabbc". Another slip is to allow 3 choices for every position of the complement instead of 2 for positions after the first.

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 6 Counting questions, with notes

GATE 2025 CS1 Q.30: solution and answer

Answer and solution

More Counting questions