ITPEC FE Morning October 2018 Question 2

Inclusion-Exclusion on Bit Strings — counting bit strings satisfying at least one of two conditions using the inclusion-exclusion principle.

All bit strings of length 4: total = 2⁴ = 16.

• •A (start with 1): first bit fixed as 1, remaining 3 bits free → 2³ = 8
• •B (end with 00): last two bits fixed as 00, first 2 bits free → 2² = 4
• •A ∩ B (start with 1 AND end with 00): pattern 1_00, 1 free bit → 2¹ = 2

Apply inclusion-exclusion:

|A ∪ B| = |A| + |B| − |A ∩ B| = 8 + 4 − 2 = 10

Why not others:
- (a) 4 — this is only the count of strings ending with 00, ignoring those starting with 1
- (b) 8 — this is only the count of strings starting with 1, ignoring those ending with 00
- (d) 12 — this is 8 + 4 without subtracting the overlap (double-counting error)

Key rule: When counting "A or B," always subtract the overlap: |A ∪ B| = |A| + |B| − |A ∩ B|.

AI-generated — may contain errors