[일반] 경우의 수 문제

[기괴공학도(mecheng98)]

A := { a∈N | 0 ＜ a ∧ a ≤ 45 }.

X := { x∈P(A) | n(x) = 6 }.

Y := { y∈P(A) | n(y) = 3 }.

(∀y∈Y)(∃x∈Q)( y ⊆ x )을 만족하는 집합 Q⊆X에 대하여 n(Q)의 최솟값은?

[익명(119.203)]

6개 짜리가 어케 3개 짜리에 포함됨?

[기괴공학도(mecheng98)]

죄송합니다. 수정했어요.

[익명(119.203)]

710?

[기괴공학도(mecheng98)]

http://m.dcinside.com/board/programming/981827

[디피프(dlffff)]

저기엔 당장 1,2,3도 없는거 아님?

[기괴공학도(mecheng98)]

잉 진짜 그러네 잠시만요

[기괴공학도(mecheng98)]

"Any 6 numbers from [1..49] will intersect at least one of these tickets in at least three numbers." 여기서 these tickets의 개수는 163인데, 제가 문제를 잘못 낸 건가요?

[ㅇㅅㅇ(49.174)]

없어도 가능하지 않음?

[디피프(dlffff)]

로또 5등이면 n(y) 도 6이고 x,y의 교집합이 3인걸 세야할듯

[기괴공학도(mecheng98)]

아, 죄송. 문제 잘못 냈네요.

[ㅇㅅㅇ(49.174)]

몬가 램지이론 느낌 나는거 봐서는 open일거 같다

[ns(qwer2357)]

링크서 본 원문제는, 어떤 임의의 6-tuple을 가져와도 3tuple이 존재하여야 하는거라, find Q subset X s.t. forall x in X, exists q in Q such that n(x cup q) >=3 이 돼야 함.

[기괴공학도(mecheng98)]

네, 고쳐주셔서 감사합니다.

[기괴공학도(mecheng98)]

그런데 cup이 아니라 cap이지 않나요?

[ns(qwer2357)]

ㅇㅇ cap..