ITPEC FE Morning October 2018 Question 2

10 — count the two sets separately, then subtract the strings counted twice.

• •Start with 1: the first bit is fixed and 3 bits are free, 2³ = 8 strings
• •End with 00: two bits are fixed and 2 are free, 2² = 4 strings
• •Both, pattern 1?00: one free bit, 2¹ = 2 strings (1000 and 1100)
• •Either: 8 + 4 − 2 = 10

Answer (c)

Why not others:

• •(a) 4 — counts only the strings that end with 00
• •(b) 8 — counts only the strings that start with 1
• •(d) 12 — adds 8 + 4 without subtracting 1000 and 1100, which belong to both sets

Key rule: For "A or B", use inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|.

Basic Theory · AI-written, may contain errors