https://arca.live/b/math/101651649

선요약:
점 v마다 집합 A(v)를 붙이고
문제의 조건을 A(v)에 대해 바꿔쓰면
귀납법으로 해결됨

질문자가 원하는 방향으로 풀고자했고
그래서 3개에 대한 얘기도 추가함

u,v∈V(T)에 대해 다음을 정의한다:
A(u)={i:u∈F_i}
p(u,v)=u에서 v로 가는 유일한 path


문제를 위의 단어들로 번역하면
(1) F_i가 tree:
i∈A(u), i∈A(v)이면 모든 w∈p(u,v)에 대해 i∈A(w)
(2') F_i끼리 항상 겹침:
어떤 i,j에 대해서도 i,j∈A(w')인 w'가 존재


여기서 사실 w'을 p(u,v) 위의 점으로 잡을 수 있다

(∵) i∈A(u), j∈A(v)일 때 i,j∈A(w')인 w'를 잡으면
p(u,w')와 p(w',v)의 교집합은 p(w',w) 꼴로 쓸 수 있고
(1)에 의해 i,j∈A(w)이다
w∈p(u,v)=p(u,w)∪p(w,v)이므로
p(u,v) 위에서 점을 고른 것이 된다

그러므로 (2')를 아래와 같이 바꾸자

(2)
i∈A(u), j∈A(v)일 때 어떤 w∈p(u,v)에 대해 i,j∈A(w)





이제 n에 대한 귀납법으로 "어떤 n개의 F_i들을 골라도 그것들의 교집합이 공집합이 아님"을 보이자

번역하면 "어떤 n개의 index를 골라도 그것들을 포함하는 A(w)가 있다"가 된다


n=1,2는 문제에서 자명
이해를 위해 n=3인 예시를 먼저 보자

1,2∈A(u), 1,3∈A(v)라면
(2)에 의해 2,3∈A(w)인 w∈p(u,v)가 있고
(1)에 의해 1∈A(w)가 되어 A(w)는 1,2,3을 모두 포함한다


이제 3을 k+2로 바꾸고 귀납법을 서술하면 다음과 같이 된다:
k+2개의 subtree를 고르고 index를 다시 넘버링해 1,···,k+2라 하자

귀납법에 의해 k+1일 때는 성립하므로
1,···,k,k+1∈A(u), 1,···,k,k+2∈A(v)인 u,v가 존재한다
(2)에 의해 k+1,k+2∈A(w)인 w∈p(u,v)가 있고
(1)에 의해 1,···,k∈A(w)가 되어 A(w)는 1,···,k+2을 모두 포함한다


따라서 귀납법이 증명되었고
모든 index(유한개)를 포함하는 A(w)도 존재한다
이는 곧 w가 모든 subtree에 포함된다는 말이 되고 문제를 풀었다




아이디어는 간단한데 막상 적어보니 기네

전부 교집합하는걸 임의의 n개의 교집합으로 약화해서 귀납법을 쓰기 좋게 만들고
3개의 교집합에서 발견한 아이디어를 그대로 적용했음