GATE2025_CS1_Q30

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)

✅ Final Answer:

The correct answer is 195.

🔹 Short Answer:

This problem is best solved using the complement rule. First, find the total number of ternary strings of length 5, which is 3⁵ = 243. Then, find the number of strings with *no* consecutive identical characters. The first character has 3 choices, and each subsequent character has 2 choices (it can't be the same as the previous one). This gives 3 × 2⁴ = 48 strings. The final answer is the total minus the complement: 243 - 48 = 195.

🔸 Long Answer:

Finding the number of strings that have "at least one" of a certain property can be complex using direct counting (e.g., with the Principle of Inclusion-Exclusion). A much simpler approach is to count the opposite (the complement) and subtract it from the total number of possibilities.

Step 1: Calculate the Total Number of Possible Strings

We are creating strings of length 5 from an alphabet of 3 characters {a, b, c}. For each of the 5 positions in the string, we have 3 independent choices.

Total strings = 3 × 3 × 3 × 3 × 3 = 3⁵ = 243

Step 2: Calculate the Complement

The complement to the condition "at least one occurrence of 'aa', 'bb', or 'cc'" is "no occurrences of 'aa', 'bb', or 'cc'". This means no two adjacent characters can be the same.

Let's count the number of such strings by filling the positions one by one:

• Position 1: Can be 'a', 'b', or 'c'. There are 3 choices.
• Position 2: Can be any character except the one at Position 1. There are 2 choices.
• Position 3: Can be any character except the one at Position 2. There are 2 choices.
• Position 4: Can be any character except the one at Position 3. There are 2 choices.
• Position 5: Can be any character except the one at Position 4. There are 2 choices.

The total number of strings in the complement set is:

Number of complement strings = 3 × 2 × 2 × 2 × 2 = 3 × 2⁴ = 3 × 16 = 48

Step 3: Calculate the Final Answer

The number of strings with at least one consecutive pair is the total number of strings minus the number of strings in the complement.

Required Strings = Total Strings - Complement Strings
Required Strings = 243 - 48 = 195

Therefore, there are 195 possible strings of length 5 that contain at least one occurrence of "aa", "bb", or "cc".

Bibliography:
- Rosen, K. H. (2018). Discrete Mathematics and Its Applications. McGraw-Hill Education. (Chapter 6.1: The Basics of Counting).
- Tucker, A. (2012). Applied Combinatorics. Wiley. (Chapter 5: General Counting Methods for Arrangements and Selections).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.