대54 풀이

-구머

1-1. 보조정리:

우선 [eqn: F_all = BIGCUP _{x in f } x]을 생각하자. ([eqn: f]에 있는 집합들의 원소를 모두 모아놓은 것으로 생각하면 된다). 이때, [eqn: F_all]의 원소의 개수는 [eqn: s(k-1)]개 이상이다.

1-1 증명: [eqn: s(k-1)]개의 원소 중 s개의 원소를 뽑는 경우의 수는 [eqn: {}_s(k-1) C_{ ```s}]인데, [eqn: {}_{s(k-1)} C _{``s} = {s(k-1)*(s(k-1)-1)*...*(s(k-1)-s+1)} over {s!} <= {s^s (k-1)^s} over s!]이고, [eqn: (s!)^2 = (1*s)(2*(s-1))...((s-1)*2)(s*1)>=s^s]이므로

[eqn: {}_s(k-1) C _{``s} <= s! (k-1)^s]이다. 따라서 [eqn: s(k-1)]개의 원소로는 [eqn: s!(k-1) ^{s}]보다 큰 개수의 집합을 만들 수 없고, 원소 개수는 [eqn: F_all]의 원소의 개수는 [eqn: s(k-1)]개보다 크다.

1-2. 보조정리:

[eqn: s=1]이거나 [eqn: k=1]인 경우 문제 1번은 성립한다. (즉, 연합 숫자 k인 어색한 모임을 만들 수 있다.)

1-2. 증명: 당연한 거임

1-3. 본 문제 증명:

문제가 [eqn: s-1]일 때 성립한다고 가정하자. 또, [eqn: F _{all} =` LEFT { v_1 , ```v_2 , ```...``,v_N RIGHT }]이라고 하자. 이제 다음 두 상황으로 집합 [eqn: f]를 구분하여 생각하자.

case 1) 각 [eqn: i=1,2,...,N]에 대해, [eqn: f]에 속하고 [eqn: v_i]를 원소로 가지는 집합의 개수가 [eqn: (s-1)!(k-1)^s-1]개 이하인 경우

:

이때 다음 과정을 반복하면 연합 숫자 [eqn: k]인 어색한 모임을 만들 수 있다.

0) [eqn: f]에 있는 집합들에 색깔을 부여하자. (음... 흰색으로 색칠합시다)

1) 흰색인 집합 중 임의로 하나를 선택한다. 선택한 집합을 [eqn: S_i]라고 두자.

2) [eqn: S_i]의 원소를 [eqn: v _{a _{i1}} ,``v _{a _{i2}} ,``...``,``v _{a _{is}}]라 하자. ([eqn: a_i1 , ``a_i2 ,`...`, `a_is]는 [eqn: N] 이하의 자연수)

3) 각 [eqn: v _{a _{i1}} ,``v _{a _{i2}} ,``...``,``v _{a _{is}}]를 포함하는 집합들을 검은색으로 색칠한다.

가정에 의해 3) 과정에서 검은색으로 칠해지는 집합의 개수는 [eqn: s!(k-1) ^{s-1}]개 이하이고, 집합 [eqn: f]에 속한 원소의 개수는 [eqn: s!(k-1)^s]개보다 크므로 이 과정(1~3)을 반복하면 적어도 [eqn: k]번 이상 [eqn: S_i]들을 선택할 수 있다. 이때 선택한 집합들을 모으면 어떤 두 집합도 공통 원소를 가지지 않게 되므로, 연합 숫자가 [eqn: k]인 어색한 모임을 만들 수 있다.

case 2) 어떤 [eqn: i]가 존재하여 [eqn: v_i]를 원소로 가지는 집합의 개수가 개보다 큰 경우

:

이때 [eqn: v_i]를 포함한 집합들의 모임을 [eqn: LEFT { A_1 , ``A_2 ,``...``,A_n RIGHT }]이라고 하자. 가정에 의해 [eqn: n > (s-1)!(k-1)^{s-1}]이다.

이제 집합 [eqn: B= LEFT { B_r = A_r -v_i ````|```` r은 ```n 이하의```자연수 RIGHT }]를 잡으면, [eqn: B_i]의 원소의 개수는 모두 [eqn: s-1]개이고, [eqn: B]의 원소 개수도 [eqn: (s-1)!(k-1)^s-1]보다 크므로 [eqn: B]에서 적당히 [eqn: k]개의 집합을 골라 연합 숫자가 [eqn: k]인 어색한 모임을 만들 수 있다. 그런데 어색한 모임의 정의에 의해 [eqn: B]에서 뽑은 어색한 모임의 집합들에 [eqn: v_i]가 포함된 집합들 또한 연합 숫자가 [eqn: k]인 어색한 모임이 된다. 따라서 [eqn: LEFT { A_1 , ``A_2 ,``...``,A_n RIGHT }]로부터 연합 숫자 [eqn: k]인 어색한 모임을 만들 수 있으므로 case 2에서 1번 문제는 성립한다.