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

비둘기집의 원리1에 이어서 비둘기집의 원리2를 적게 되었습니다. 비둘기집의 원리를 파트를 나눠서 진행하는 이유는 없고 단지 양이 많기 때문입니다. 비둘기집의 원리1을 아직 보지 못했다면 여기로 들어가서 보고 와주세요.

 

#5.a1<a2<...<ak≤n이고, k>(n+1)/2 인 k개의 양의 정수가 있다. 그러면 ai+a1=ar인 ai,ar이 적어도 한 쌍 존재함을 보여라.

원소가 k-1개인 집합 S={a2-a1,....ak-a1}와 원소가 k개인 T={a1,a2...,ak}를 잡자.

S,T의 각 원소들은 서로 다르고 S∩T≠∮이라면 S와 T의 원소개수 합이 문제조건에 의해 2k-1>n 즉, n을 넘게 되어 모순이 생긴다. 따라서 S의 원소 중에 하나와 T의 원소 중 하나가 같은 경우가 생겨야 한다.

ai-a1=ar이 되어 ai+a1=ar

계속 뭐든지 중요하다고 하는 것 같은데 이 문제도 굉장히 중요하다. 이 테크닉을 여러 문제에 적용할 수 있으니 말이다.

 

#6.임의의 볼록2n각형에는 임의의 변과 평행하지 않은 대각선이 존재함을 보여라.

문제를 풀기 전에 생각을 해보자. 대각선은 임의의 변과 평행한 대각선과 그렇지 않은 것으로 나뉜다.

만약 평행한 대각선 개수<전체 대각선 개수라면 평행하지 않은 대각선이 존재하지 않겠는가?

각 변 e에 대해 e와 평행한 대각선 개수≤n-2

각 변과 평행한 대각선 개수의 총합≤2n(n-2)

볼록2n각형의 대각선 개수≤2nC2=n(2n-3)

2n(n-2)≤n(2n-3)이라서 임의의 변과 평행하지 않은 대각선이 존재한다.

 

#7.정 7각형의 각 꼭지점은 흰색이나 검은색으로 칠해져 있다. 이등변삼각형을 만들 수 있는 색이 같은 꼭지점이 존재함을 증명하여라. 정 8각형에 대해서는 어떠한가?

비둘기집의 원리에 의해 정 7각형의 경우 어떤 연속한 두 꼭짓점은 같은 색(WLOG:검은색)이다.

그 같은 두 꼭짓점을 P1,P2라 하면 P7,P3은 흰색이 된다. P5가 검은색이 되면 P1P2P5가, 흰색이 되면 P3P5P7이 이등변삼각형이 된다.

정 8각형의 경우 정 7각형처럼 이등변삼각형이 존재하지 않는다. 반례를 들어 증명하면 된다.

(흰색을 w로, 검은색을 b로 표현하면 P1부터 P8까지 wwbbwwbb 이런 형식으로 색칠된 경우가 반례)

 

다음 글은 램지의 정리이다.