조합[심화문제1] 5-1

내가 생각한 중요문제들만 담겠다.

 

#1.100개의 A1,...,A100, |Ai|=10 이 주어져 있는데, 임의의 두 집합의 공통 원소의 개수는 정확히 하나이다. A1∩A2∩...∩An≠∮ 임을 증명하시오.

귀류법:A1∩A2∩...∩An=∮

A1부터 Ad까지 a와 연결되어 있다고 마음의 눈으로 바라보도록 하자.

우선 왼쪽의 그림부터 보도록 하자.

a∈S, a∈A1,A2,...,Ad(a는 A_d+1에서 A₁₀₀에는 속하지 않는다.)

|Ai∩Aj|=1이기 때문에 A1,Ad에서 K집합으로 선을 1개씩은 그어야 한다.

그리고 선들이 같은 K집합의 원소로 향하면 |Ai∩Aj|≠1이 되어 모순이기 때문에 각 선은 다 다른 원소를 가리킨다.

|Ai|=10이라 d≤10을 만족, S의 임의 원소는 최대 10개의 Ai에 포함된다.

이제 오른쪽 그림이다.

|Ai∩Aj|=1로 인해 F'에서 S'로 99개의 선이 그어진다.

b∈S' b에는 적어도 F'에서의 선 [99/10]=10개가 그어진다.

b가 11개 이상의 Ai에 포함하게 되어 모순

 

#2.32명의 학생이 있는 학급에 33개의 클럽이 조직되었다. 각 클럽에는 3명의 학생이 속하고, 어떤 두 클럽도 구성원이 완전히 동일하지는 않다. 딱 한 명을 공유하는 두 클럽이 있음을 증명하여라.

귀류법:딱 한 명을 공유하는 두 클럽은 없다.

|S|=32 F={A1,A2,...,A33} |Ai|=3 |Ai∩Aj|=0,2

F를 F1,F2,...,Fm으로 나눈다. Fi={A1,A2,...,Au}에서 |A1∪A2∪...∪Au|≥u임을 보이면 가정에 모순이므로 증명 끝

A1={a,b,c}라 하자.

1)A1에서 공통원소가 될 수 있는 원소가 2개인 경우 WLOG 그 원소를 a,b라 하자.

A2={a,b,c1}

A3={a,b,c2}

.

.

.

An={a,b,c_n-1} 로 잡을 수 있고 |A1∪A2∪...∪Au|=u+2≥u라 모순

 

2)A1에서 공통원소가 될 수 있는 쌍이 2개인 경우

WLOG 그 쌍을 (a,b) (a,c)라 하자.

A2={a,b,c1} A3={a,c,b1}로 잡을 수 있는데, 그러면 조건을 만족하는 A4가 존재하지 않으므로 |A1∪A2∪A3|≥3라 모순

 

3)A1에서 공통원소가 될 수 있는 쌍이 3개인 경우

A2={a,b,c1} A3={b,c,c1} A4={c,a,c1}으로 잡을 수 있고, |A1∪A2∪...∪Au|=u≥u라 모순

따라서 딱 한 명을 공유하는 두 클럽이 존재한다.

 

#3.10×10표의 각 칸에 0,1,2...,9의 숫자를 하나씩 써넣는데, 각 숫자는 10번씩 사용할 수 있다.

4종류 이상의 숫자를 가진 행이나 열이 반드시 있음을 보여라.

k=0~9

k가 존재하는 가로줄개수=ak

k가 존재하는 세로줄개수=bk

i=1~10

i번 가로줄에 숫자 종류=ri

i번 세로줄에 숫자 종류=ci

임의의 줄에 숫자가 3종류 이하 존재한다고 가정

a₀+a₁+...+a₉+b₀+b₁+...+b₉=r₁+r₂+...+r₁₀+c₁+c₂+...+c₁₀

ai+bi≥2√aibi≥2√10

a0+a1+...+a9+b0+b1+...+b9=r1+r2+...+r10+c1+c2+...+c10≥20√10

비둘기집의 원리에 의해 ri≥[√10]=4

 

#4.8개의 축구팀이 풀리그를 벌인다. 비기는 경우는 없고, 각 두 팀은 꼭 한 번씩 경기를 한다. 대회가 끝났을 때, A가 B,C,D를 이기고, B가 C,D를 이기고, C가 D를 이긴 네 팀 A,B,C,D를 항상 찾을 수 있음을 보여라.

모든 차수의 총합=8C2=28이다.

[28/8]=4

A가 이긴 네 팀이 존재한다.

A가 이긴 네 명의 차수의 합은 4C2=6

[6/4]=2

B가 이긴 팀이 적어도 2개 존재한다

이 때 이 두 팀중 서로 경기를 했을때 이긴 팀을 C로 설정하고 진 팀을 D로 설정하면 조건을 만족하는 A,B,C,D를 찾을 수 있다.