말랑말랑 수학문제 #4

<문제>

$40$ 명의 출제위원단이 시험 문제를 출제하기 위해 모여있다. 출제를 위한 후보 문제들이 총 $30$ 개가 존재하고, 각 심사위원들은 정확하게 $30$ 문제 중 $26$ 문제를 풀었다. (단, 임의의 두 출제위원이 푼 문제 집단은 동일하지 않다)

출제위원단이 문제를 출제할 때 출제기준이 '출제위원단 절반 이상이 풀었고, 모든 출제위원이 풀지 않아야 한다'일 때 $40$ 명의 출제위원단은 $30$ 개의 문제 중 적어도 한 문제를 출제할 수 있음을 보여라.

 

-----풀이 스포를 주의하세요-----

 

 

 

 

 

 

 

 

 

 

<풀이>

이 문제도 '더블카운팅'의 개념을 사용하면 풀 수 있다. 출제위원단이 푼 총문제의 수는 $40 \times 26 = 1040$ 이다. 이 값을 문제를 기준으로 카운팅을 해보겠다.

$40$ 명이 모두 푼 문제의 수를 $k$ 개라고 하자. $40$ 명이 모두 푼 $k$ 개의 문제들은 출제위원단이 푼 총문제의 집합에 포함되므로 $40 \times k \leq 40 \times 26$ 이다. 따라서 $k \leq 26$ 이 성립한다. 

 

case1) $k = 26$ 인 경우

출제위원 $40$ 명이 모두 푼 문제가 동일하므로 문제의 조건에 모순이다.

 

case2) $k = 25$ 인 경우

전체 문제가 $30$ 문제이고 각각 $40$ 명이 한 문제씩만 다르게 풀어야 한다. 즉, 남은 $5$ 문제를 $40$ 명이 나눠서 풀어야 하는데 $\binom{5}{1} = 5 < 40$ 이므로 모순이다.

 

case3) $k=24$ 인 경우

마찬가지로 남은 $6$ 문제 중 $2$ 쌍을 $40$ 명이 나눠서 풀어야 하는데 $\binom{6}{2} = 15 < 40$ 이므로 모순이다.

 

case4) $k=23$ 인 경우

마찬가지로 남은 $7$ 문제 중 $3$ 쌍을 $40$ 명이 나눠서 풀어야 하는데 $\binom{7}{3} = 35 < 40$ 이므로 모순이다.

따라서 $k \leq 22$ 임을 얻을 수 있다.

 

귀류법을 사용하기 위해 문제를 한 문제도 출제할 수 없다고 가정해보자. $40$ 명이 모두 푼 $k$ 개의 문제를 제외한 나머지 $30-k$ 개의 문제들은 귀류법 가정에 의해 $19$ 명 이하가 풀게 된다. 출제위원단이 푼 총문제의 수는 $1040$개인데, 문제 각각 푼 출제위원단 수를 더한 값은 $40k + 19(30-k)$명 이하이므로 아래와 같은 부등식이 성립한다.

 

$$1040 \leq 40k + 19(30-k) \Rightarrow 470 \leq 21k$$

 

$k \leq 22$ 이므로 $470 \leq 21k \leq 462$ 여서 모순이다.

따라서 귀류법 가정이 모순되어 적어도 한 문제는 출제할 수 있게 된다. $\blacksquare$