포함과 배제에 관련 5문제

포함-배제 원리를 이용한 조합 문제 5가지와 풀이

**포함-배제 원리 (Principle of Inclusion-Exclusion)**는 여러 조건 중 적어도 하나를 만족하는 원소의 개수를 구할 때 유용하게 사용되는 원리입니다. 두 집합 A와 B에 대해 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣가 성립하며, 세 집합 A,B,C에 대해서는 ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−(∣A∩B∣+∣A∩C∣+∣B∩C∣)+∣A∩B∩C∣가 성립합니다.

문제 1. 1부터 100까지의 자연수 중 2의 배수 또는 3의 배수의 개수를 구하시오.

풀이:

• A: 1부터 100까지의 자연수 중 2의 배수의 집합
• B: 1부터 100까지의 자연수 중 3의 배수의 집합

우리가 구해야 하는 것은 ∣A∪B∣입니다.

• ∣A∣=⌊100/2​⌋=50 (2의 배수의 개수)
• ∣B∣=⌊100/3​⌋=33 (3의 배수의 개수)
• ∣A∩B∣는 2의 배수이면서 3의 배수인 수의 집합, 즉 6의 배수의 집합입니다. ∣A∩B∣=⌊100/6​⌋=16 (6의 배수의 개수)

따라서 포함-배제 원리에 의해, ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣=50+33−16=67

답: 67개

---

문제 2. 50명의 학생 중 수학을 좋아하는 학생은 30명, 과학을 좋아하는 학생은 25명이다. 수학과 과학을 모두 좋아하는 학생은 10명일 때, 수학 또는 과학을 좋아하는 학생의 수를 구하시오.

풀이:

• M: 수학을 좋아하는 학생의 집합 (∣M∣=30)
• S: 과학을 좋아하는 학생의 집합 (∣S∣=25)
• M∩S: 수학과 과학을 모두 좋아하는 학생의 집합 (∣M∩S∣=10)

우리가 구해야 하는 것은 ∣M∪S∣입니다.

포함-배제 원리에 의해, ∣M∪S∣=∣M∣+∣S∣−∣M∩S∣=30+25−10=45

답: 45명

---

문제 3. 1부터 200까지의 자연수 중 3의 배수도 아니고 5의 배수도 아닌 수의 개수를 구하시오.

풀이:

• 전체 집합 U: 1부터 200까지의 자연수 (∣U∣=200)
• A: 1부터 200까지의 자연수 중 3의 배수의 집합
• B: 1부터 200까지의 자연수 중 5의 배수의 집합

우리가 구해야 하는 것은 3의 배수도 아니고 5의 배수도 아닌 수의 개수, 즉 ∣U∣−∣A∪B∣입니다.

• ∣A∣=⌊200/3​⌋=66
• ∣B∣=⌊200/5​⌋=40
• ∣A∩B∣는 15의 배수의 집합입니다. ∣A∩B∣=⌊200/15​⌋=13

먼저 ∣A∪B∣를 구합니다. ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣=66+40−13=93

따라서 3의 배수도 아니고 5의 배수도 아닌 수의 개수는 ∣U∣−∣A∪B∣=200−93=107

답: 107개

---

문제 4. 100명의 학생에게 세 가지 종류의 문제 A, B, C를 풀게 하였다. 문제 A를 푼 학생은 40명, 문제 B를 푼 학생은 35명, 문제 C를 푼 학생은 30명이었다. 문제 A와 B를 모두 푼 학생은 15명, 문제 B와 C를 모두 푼 학생은 10명, 문제 A와 C를 모두 푼 학생은 12명이었다. 세 문제 모두 푼 학생은 5명일 때, 적어도 한 문제를 푼 학생의 수를 구하시오.

풀이:

• A: 문제 A를 푼 학생의 집합 (∣A∣=40)
• B: 문제 B를 푼 학생의 집합 (∣B∣=35)
• C: 문제 C를 푼 학생의 집합 (∣C∣=30)
• ∣A∩B∣=15
• ∣B∩C∣=10
• ∣A∩C∣=12
• ∣A∩B∩C∣=5

우리가 구해야 하는 것은 ∣A∪B∪C∣입니다.

포함-배제 원리에 의해, ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−(∣A∩B∣+∣A∩C∣+∣B∩C∣)+∣A∩B∩C∣ ∣A∪B∪C∣=40+35+30−(15+12+10)+5 ∣A∪B∪C∣=105−37+5=68+5=73

답: 73명

---

문제 5. 7개의 서로 다른 색깔의 구슬이 있다. 이 중 빨간색 또는 파란색 구슬을 적어도 하나 포함하여 3개의 구슬을 선택하는 경우의 수를 구하시오.

풀이:

• 전체 경우의 수: 7개의 구슬 중 3개를 선택하는 경우의 수 = (7C3)=7×6×5​/ 3×2×1 =35
• R: 선택한 3개의 구슬 중 빨간색 구슬이 적어도 하나 포함된 경우의 집합
• B: 선택한 3개의 구슬 중 파란색 구슬이 적어도 하나 포함된 경우의 집합

우리가 구해야 하는 것은 ∣R∪B∣입니다. 이를 직접 구하는 대신 여집합을 이용하여 계산할 수 있습니다.

• Rc: 선택한 3개의 구슬 중 빨간색 구슬이 하나도 없는 경우의 집합. 빨간색을 제외한 6개의 구슬 중 3개를 선택하는 경우의 수 = (6C3​)=6×5×4/ 3×2×1 ​=20
• Bc: 선택한 3개의 구슬 중 파란색 구슬이 하나도 없는 경우의 집합. 파란색을 제외한 6개의 구슬 중 3개를 선택하는 경우의 수 = (6C3​)=20
• R^c∩B^c: 선택한 3개의 구슬 중 빨간색 구슬도 없고 파란색 구슬도 없는 경우의 집합. 빨간색과 파란색을 제외한 5개의 구슬 중 3개를 선택하는 경우의 수 = (5C3​)=5×4×3/ 3×2×1 ​=10

∣R^c∪B^c∣=∣R^c∣+∣B^c∣−∣R^c∩B^c∣=20+20−10=30

따라서 빨간색 또는 파란색 구슬을 적어도 하나 포함하는 경우의 수는 전체 경우의 수에서 빨간색도 파란색도 포함하지 않는 경우의 수를 뺀 것과 같습니다.

∣R∪B∣=전체 경우의 수−∣(R∪B)^c∣=전체 경우의 수−∣R^c∩B^c∣=35−10=25

다른 풀이 (직접 계산):

• 빨간색만 포함하는 경우: (11​)×(25​)=1×10=10 (빨간색 1개 선택, 빨간색/파란색 아닌 5개 중 2개 선택)
• 파란색만 포함하는 경우: (11​)×(25​)=1×10=10 (파란색 1개 선택, 빨간색/파란색 아닌 5개 중 2개 선택)
• 빨간색과 파란색 모두 포함하는 경우: (11​)×(11​)×(15​)=1×1×5=5 (빨간색 1개, 파란색 1개, 빨간색/파란색 아닌 5개 중 1개 선택)

따라서 적어도 하나 포함하는 경우의 수는 10+10+5=25

답: 25가지