조합[비둘기집의 원리1] 2-1

비둘기집의 원리에 대해 알아보자. 비둘기집의 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리이다. 보다시피 이 원리를 도대체 어떻게 문제에 적용할지를 궁금해할 것 같다. 이제부터 비둘기집의 원리에 대한 문제들을 살펴보도록 하자.

 

#1.n명의 사람이 모임을 가지고 있다. 모든 사람은 다른 사람과 악수를 한다. 모임 동안에 같은 수만큼 악수한 사람 두 명이 항상 존재함을 증명하여라.

사람당 가질 수 있는 악수의 숫자는 1~n-1인데 사람은 총 n명이니 모임 동안 같은 수만큼 악수한 사람이 존재한다.

이 #1은 비둘기집의 원리의 기초라고 볼 수 있을 정도로 쉬운 축에 속한다.

 

#2.공간상에 어느 세 점도 일직선상에 있지 않은 9개의 격자점 P₁...,P₉이 있다. 어떤 선분 PiPk,i≠k 위에 한 격자점 L이 있음을 증명하여라.

Pi=(xi,yi,zi) 최대 8가지가 mod 2에 대한 서로 다른 쌍이다.

비둘기집의 원리에 의해 (xi,yi,zi)가 가질 수 있는 mod 2 종류는 8가지인데 점은 9개라 따라서 문제에서 증명하라는 것이 충분히 증명되었다.

 

#3.2나 5에 의해 나누어지지 않는 양의 정수 n이 있다. 전부 1로 구성된 n의 배수가 존재함을 증명하여라.

집합 S를 먼저 잡는다.

S={1,11,111,.....,111....1} (마지막은 1이 n개 있는 수)

S의 집합에 속하는 모든 원소가 n으로 나누어떨어지지 않으면 S의 두 원소 차이는 10의 배수×111....111꼴이기 때문에 mod n에 대해 같은 두 원소가 없다. 따라서 S에 속하는 n개의 원소 중에는 mod n에 대해 0과 합동인 수가 존재한다.

(만약 집합에 속하는 모든 원소가 n으로 나누어 떨어지지 않지 않으면 바로 mod n에 대해 0과 합동인 수가 존재함)

이 방법은 굉장히 여러군데에서 사용되는 방식이라고 볼 수 있다. 꼭 이런 형식으로 집합을 잡는 것을 기억하자.

 

이 문제를 활용하는 예시 문제를 아래에 첨부한다.

#3*.S는 n개의 양의 정수 집합이다. S의 원소 중 어느 것도 n에 의해 나누어지지 않는다. S의 부분 집합 중에는 합이 n으로 나누어지는 것이 있음을 증명하여라.

 

#3**.{1,2,...,2n}에서 택한 n+1개의 정수들 중에는 서로소인 두 정수가 존재함을 보여라.

 

#4.서로 다른 10개의 두자리 자연수중에서, 교집합이 공집합이면서 각 집합의 원소의 합이  같아지도록 두 개의 집합을 항상 택할 수 있음을 보여라.

S는 서로 다른 10개의 두자리 자연수들의 집합으로 두자. S={a1,a2,...,a10}

공집합이 아닌 S의 부분집합의 개수는 2¹⁰-1개이다.

그런데 임의의 집합 A⊂S를 살펴보면 1≤A의 원소합≤S의 원소합≤90+91+...+99<2¹⁰-1이라서 비둘기집의 원리에 의해 원소합이 같고 다른 두 집합 A,B가 존재한다. 만약 A∩B≠∮이면 B-A,A-B가 원소의 합이 같고 교집합이 공집합인 두 개의 집합이 되는 것이고, A∩B=∮이면 A,B가 원소의 합이 같고 교집합이 공집합인 두 개의 집합이 된다.

이 문제는 매우 중요한 테크닉을 가지고 있다. 꼭 외우도록 하자.

 

외웠다면 아래의 문제를 풀어보자.

#4*.a1,a2,...,an(n≥5) 는 양의 정수의 수열이다. 이 수열의 부분 수열 중에는 각 원소를 더하거나 빼서 그 합이 n²의 배수가 되는 것이 있음을 증명하여라.