제 26회 전국 대학생 수학 경시대회 제 1 분야 #01-03

제 26회 전국 대학생 수학 경시대회 제 1 분야 #01-03

 

추천글 : 【전국 대학생 수학경시대회】 전국 대학생 수학경시대회 풀이 모음 

---

 

제 26회 전국 대학생 (공업)수학 경시대회

제 1 분야

2007년 11월 03일 (10:00 - 12:00)

 

1-3. 집합 A = {1, 2, 3, …, n}에 대하여 γ개의 원소로 이루어진 서로 다른 부분집합을 k개 선택하려고 한다. 이때, A의 임의의 원소가, 선택된 k개의 부분집합 중에서 적어도 p개의 부분집합에 항상 속하기 위해서는 k ≥ np / γ이어야 함을 보여라.

 

 

Solution. 

γ개의 원소로 이루어진 서로 다른 부분집합 k를 적당히 골랐더니 A의 임의의 원소가 k개의 부분집합 중에 적어도 p개 속해 있는 경우가 있다는 것이다. 이때 중복을 고려하면 k개의 부분집합의 원소는 모두 kγ개다. 그런데 이 경우 A의 임의의 원소가 적어도 각각 p번 이상 '중복'으로 나타나므로 kγ ≥ np라는 관계식을 얻는다. 이는 (준식)과 동치이다.

 

입력: 2015.10.29 23:56