조합[포함과 배제의 원리] 1-2

출처:123rf

포함과 배제의 원리, 조합에서 자주 사용되는 원리이다. 포함과 배제의 원리는 유한 집합의 합집합의 원소 개수를 세는 기법이라고 구글에 나와있는데 이렇게 들으면 뭔 소린지 도통 모르겠으므로 다음의 예시문제로 설명을 시작할까 한다.

 

#*.한 변의 길이가 2인 정사각형의 내부에 각각의 넓이가 1 이상인 일곱개의 다각형들이 주어져 있다. 이 때, 이 다각형들 중에서 어떤 두 개의 다각형은 공통 부분의 넓이가 1/7 이상임을 증명하여라.

위의 문제의 결론을 부정하는 문장은 '임의 두 개의 다각형의 공통 부분의 넓이가 1/7 미만'이라고 볼 수 있다. 우리가 이제부터 해야할 행동이 무엇인지 알겠는가? 바로 귀류법을 사용하여 최선을 다해도 모순이 나온다는 것을 보이는 것이다.

 

귀류법:임의 두 개의 다각형의 공통 부분의 넓이는 1/7 미만

정사각형의 넓이=다각형들의 넓이합-다각형 2개 공통부분의 넓이합+다각형 3개 공통부분의 넓이합≥다각형들의 넓이합-다각형 2개 공통부분의 넓이합>1×7-1/7×21=4

정사각형의 넓이는 4라 4>4 모순

따라서 귀류법의 부정이 참이다.

다음의 문제를 보고 어떤 생각이 드는가? 포함과 배제의 원리는 어떤 것을 세는 여러가지 방법 중 하나이다.

 

#L.다음을 만족하는 기약분수 D의 개수를 구하시오.

D의 분자는 2015이다.

1/2016<D<1/2015

D=2015/a일때 1/2016<2015/a<1/2015이므로

2015²<a<2015×2016

a=2015²+u라 두면, (2015,a)=(2015,u)=1이므로 D개수=a개수=u개수=∮(2015)=1440