뭐 원문은 


Q1. 45개 숫자 중 6개를 뽑는 로또에서 몇개의 제비를 뽑아둬야 적어도 세개 이상 일치하는(4등이상) 가지수가 하나 이상 존재하도록 할 수 있는가?

Q2. 45개 숫자 중 6개를 뽑는 로또에서 몇개 이상의 제비를 뽑아야 모든 세개짜리 순서쌍을 빠짐없이 포함할 수 있는가?


좀더 잘 적으면 [n]을 {1,...,n} 집합으로, P(X,k)= 원소 k짜리 X의 부분집합으로 둘때,

X=P([45],6), Y=P([45],3)일때, Q subset X를 잡아서 다음을 만족한다고 할 때 n(Q)의 최소값은?

Q1. for all x in X, exist q in Q such that n(q intersect x) >= 3

Q2. for all y in Y, exist q in Q such that y subset q.


보통 lower bound와 upper bound로 나뉘는데, upper bound쪽은 Q1 (문제가 Q2면 Q2)의 조건을 만족하는 집합 Q를 제시하면 됨.

이건 컴퓨터로 열심히 돌려서 찾으면 된다.

lower bound쪽 증명은 보통 다음의 double counting 논법으로 보인다. Q2가 더 쉬우니 Q2부터


(y,q) : y in Y, q in Q, y subset q의 순서쌍을 센다. q부터 세면 n(Q)개, 그 각각에 대해 6C3=20개의 y의 가지수가 생긴다.

식으로 적으면 sum_{q in Q} sum_{y in Y, y subset q} 1을 세는것. 그래서 저 가지수가 20 n(Q)가 됨.

반대로 저 합을 순서를 바꿔서 sum_{y in Y} sum_{q in Q, y subset q} 1 로 세면, Q의 집합의 정의가 적어도 하나의 Y는 포함하기때문에

 안쪽 합이 1 이상이 된다.

그래서 저 합은 n(Y) 이상인걸 알 수 있음.

따라서 n(Q)*20 >= n(Y)로부터 n(Q) >= n(Y)/20 = 709.5를 얻음. 물론 적어도 710개 이상이 있어야한단거지 710개짜리 어떤 조합이 존재하는건 아닐수 있기 때문에 컴퓨터로 예시를 찾아 제시해줘야함. 그래서 답이 710일수도 있고 그보다 더 클수도 있음.


이제 원래문제로 돌아가서, 저걸 세는 방법은 비슷하게 (y, q, x) : y in Y, q in Q, x in X, y subset q, y subset x의 수를 세면 된다.

q부터 세면, n(Q) 각각에 대해 y를 20가지 choice가능하고, 그 각각에 대해 42C3의 X의 가지수가 존재한다. 즉 n(Q)*20*42C3

반대로 X부터 세면 모든 X에 대해 문제 가정에 의해 어떤 q와 어떤 y가 적어도 하나 존재한다. 즉 n(X)=45C6 이상.

그래서 n(Q) >= 45 C 6 / 20*42C3 해서 계산하면 n(Q) >= 35.xx 가 나와서 36이상이 되야함을 알 수 있다.


물론 45개이상인걸 증명할 수 있으면 더 좋은 lower bound니까 좋겠지. 근데 그냥은 잘 안됨. 물론 추정은 할 수 있는데, 애초에 45개로 추정했다고 해봐야 실제값은 그거보다도 더 클거기때문에..


다른 counting argument로 45개 이상을 증명할 수 있으면야 환영.