대54 풀이 – 구머

3번

이것 역시 귀류법으로 접근하자. 문제의 [eqn: f]에서 연합 숫자가 [eqn: k]인 어색한 모임 [eqn: S]를 만들 수 있다고 가정하자. 이때, [eqn: F_all = UNION _{ x in S} ^{ `}x]라고 하자. [eqn: S]의 집합들이 1 이상 n 이하의 정수만 원소로 가지므로, [eqn: F_all]의 원소의 개수는 [eqn: n] 이하이다. -- (1)

또, 어색한 모임에서의 [eqn: Y= LEFT { a_1 ,``a_2 ,...,a_r RIGHT }]라고 하자. ([eqn: a _{1} ,`a _{2} ,`...`,a _{r}]은 [eqn: n] 이하의 양의 정수). 이때 [eqn: S= left { S_1 , S_2 , ...,S_k right }]에 대해 각 [eqn: S_i]들은 공통원소 [eqn: r]개와 개별원소 [eqn: s-r]개를 가지므로, [eqn: F_all]의 원소의 개수는 [eqn: r+(s-r) TIMES k]개다. [eqn: k]가 양의 정수이고 [eqn: r<s]이므로, 원소의 개수는 [eqn: r=s-1]일 때 최소가 되고, 이때 [eqn: F_all]의 원소의 개수는 [eqn: s+k-1]개다. 그런데 문제 조건에 의해 [eqn: s+k-1>n]이므로 [eqn: F_all]의 원소의 개수는 무조건 [eqn: n]개보다 많게 된다.--(2)

(1)과 (2)에 의해 모순이 발생하고, 따라서 3번의 명제는 성립한다!