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

바위비둘기, 출처:위키백과

어느덧 비둘기집의 원리 마지막을 다루게 되었다. 열심히 해보자. 비둘기집의 원리는 무엇이 비둘기이고, 비둘기집인지에 대해 잘 파악해야 한다.

 

#8.반지름 16인 원의 내부에 650개의 점이 있다. 그러면 내부 반지름이 2이고 외부 반지름이 3인 반지모양(링 C)으로 이 점들 중 10개를 덮을 수 있음을 증명하여라.

점 P가 중심이 Q인 링 C에 덮이는 것은 점Q가 중심이 P인 링 C에 덮이는 것과 같다.

650개의 각 점 P를 중심으로 내부반지름:2 외부반지름:3인 링을 그린다. 이 링중 어떤 10개가 어떤 점을 동시에 덮는다는 것을 보이자.

 

귀류법:평면상의 임의의 점은 최대 9개의 링이 덮는다.

S=링의 넓이의 합=5π×650=3250π

650개의 링은 반지름이 19인 원에 덮인다.

S는 최대 361π×9=3249π라 모순

따라서 평면상의 적어도 한 점은 10개의 점이 덮는다.

비둘기집의 원리를 넓이에 적용한 사례이다.

 

#2.변의 길이가 1인 정사각형 내부에 총길이가 10인 여러 개의 원이 있다, 이 원 중 적어도 4개를 지나는 직선이 존재함을 보여라.

이 문제는 정사영을 활용하여 풀어야 한다.

 

모든 원을 정사각형의 임의 선분 AB 위로 정사영시킨다.

n개의 원의 원주길이:l1,l2,...,ln  li들의 합=10

n개의 원의 지름:l1/π,l2/π...,ln/π 지름들의 합=10/π>3

정사각형의 한 변 AB=1이라 비둘기집의 원리에 의해 AB위의 어떤점 P를 덮는 사영선분이 4개 이상

P를 지나는 AB의 수선이 존재->문제조건 성립

 

#3.임의의 두 수의 최소 공배수가 2n보다 큰 n개의 양의 정수 a1≤a2≤...≤an≤2n 가 있다. a1>2n/3 임을 증명하여라.

귀류법:a1≤2n/3

1≤2a1,3a1,a2,...,an≤2n

약수배수인 두 수가 있다.(이건 증명해야 한다.)

그런데 2a1,3a1은 약수배수관계가 아니다.

a_i가 2a₁의 배수일때 최소공배수가 2n보다 크지 않다.

a_j가 3a₁의 배수일때 최소공배수가 2n보다 크지 않다.

약수배수관계가 생기지 않아 모순

따라서 a1>2n/3

 

#4.한 평면이 어떤 식으로든 파란색과 빨간색으로 칠해져 있다고 하자. 꼭지점이 같은 색을 가진 직사각형이 존재함을 보여라.

한 직선 위에 7개의 임의점이 있다. WLOG:어떤 4개의 점(P,Q,R,S)은 빨강색으로 잡자.

2번째 줄과 3번째 줄 옆에 점이 하나 더 있다.

2번째 줄은 직사각형을 만들지 않기 위해 파랑색 점이 3개 이상이고 빨강색 점이 1개 이하이도록 점을 칠하고

3번째 줄도 직사각형을 만들지 않기 위해 빨강색 점이 3개 이상이고 파랑색 점이 1개 이하이도록 점을 칠했지만,

3번째 줄의 저 3개의 점에는 빨강색이 2개 이상 존재하거나 파랑색이 2개 이상 존재하면 직사각형이 만들어지기 때문에 직사각형이 생길 수 밖에 없다.

 

#5.a1,a2,...,a100과 b1,b2,...,b100은 1부터 100까지의 정수들의 치환이다. 그들의 곱 a1b1,a2b2,...,a100b100 중에는 100으로 나누었을 때 같은 나머지를 가지는 두 수가 있음을 증명하여라.

귀류법:a1b1,a2b2,...,a100b100 은 mod 100에 대한 완전잉여계 

이제 홀짝을 비교하여 aibi가 mod 100에 대해 짝수려면 ai,bi가 다 짝수여야 하는데, 그러면 mod 100에 대해 비교시 나오는 값이 4k+2꼴인 값들은 존재하지 않아 모순이다.

 

#6.200 이하의 70개의 서로 다른 자연수 중에는 두 수의 차가 4 또는 5 또는 9인 수가 존재함을 보여라.

4+5=9인 것을 보고 무언가 눈치챘는가? 이 문제는 비둘기집의 원리1에 3번을 풀 때 사용했던 전략을 다시 사용한다.

A={a1,a2,...a70}

B={a1+4,a2+4,...,a70+4}

C={a1+9,a2+9,...,a70+9}

A,B,C에 속하는 모든 원소들은 209 이하이고 원소의 개수는 210개이다. 따라서 비둘기집의 원리에 의해 ai,aj+4,al+9 중에서 같은 두 꼴이 존재한다.

ai=aj+4면 차가 4인 두 수(ai,aj) 존재

ai=al+9면 차가 9인 두 수(ai,al) 존재

aj+4=al+9면 차가 5인 두 수(aj,al) 존재

 

다음에는 불변량에 대해 다룰 것 같다.