문제 하나 질문입니다!!
게시글 주소: https://image.orbi.kr/0001076018
U = {1,2,3,4,5} 라는 전체 집합이 있는데 이것의 부분집합 A, B 가 있다고 합니다.
이때 A 와 B 의 교집합이 공집합이 되도록하는 A, B 들의 쌍의 개수를 구하시오.
(단, A 와 B 는 구분하지 않는다. 예를 들어 A = {1}, B = {2} 인 경우와 A = {2} , B = {1} 인 경우는 같은 쌍으로 간주한다.)
이문제좀 한번 풀어주세요..
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
집합을 A,B,C(=(A∪B)c)
로 두면, C에 들어갈 원소의 갯수에 따라 가짓수가 갈리겠죠
1. C에 0개 : 5개원소를 2개 집합에 위치 시킴 : 2^5
2. C에 1개 : 5개원소중 1개 C에 넣음 5C1 * 4개원소를 2개집합에 위치시킴 2^4
3. C에 2개 : 5개원소중 2개 C에 넣음 5C2 * 3개원소를 2개집합에 위치시킴 2^3
4. C에 3개 : 5개원소중 3개 C에 넣음 5C3 * 2개원소를 2개집합에 위치시킴 2^2
5. C에 4개 : 5개원소중 4개 C에 넣음 5C4 * 1개원소를 2개집합에 위치시킴 2^1
6. C에 5개 : 5개원소를 5개 C에 넣음 5C5
단 1~5 case는 두개집합은 구분하지 않으므로 반으로 나눠준다.
(32+80+80+40+10)/2 = 121
6case : 1개
총합 122개
맞나요?
저도 이런식으로 풀어서 똑같이 답이 나왔는데 답은 147 이더라구요 ...... 도저히 이해가안되서 ;;
게다가 이거 중1 문제라서 더 열받네요 ㅋㅋㅋㅋ......
1. C에 0개 : 5C0 * (5C0 + 5C1 + 5C2) 16
2. C에 1개 : 5C1 * (4C0 + 4C1 + 4C2) 55
3. C에 2개 : 5C2 * (3C0 + 3C1) 40
4. C에 3개 : 5C3 * (2C0 + 2C1) 30
5. C에 4개 : 5C4 * (1C0) 5
6. C에 5개 : 5C5 * (0C0) 1
이렇게 풀어야 합니다.
나누기에서 나뉘지 말아야 할 것들이
나뉘어져서 답이 달리 나온 것입니다.
경우의 수 문제에서 나누기를 할 떄는 정말 신중해야 합니다.
오 그렇네요
답은 122 쌍이 맞습니다. 147은 잘못된 답입니다.
C에 1개 있는 경우 5C1 × ( 4C0 + 4C1 + 4C2 ) = 55 가 되는 것이 아니고, 5C1 × ( 4C0 + 4C1 + (4C2) / 2 ) = 40 이 되어야 맞습니다.
이는 U = { 1, 2 } 일 때, A, B의 쌍이 { Φ, Φ }, { { 1 }, Φ }, { { 2 }, Φ }, { { 1, 2 }, Φ }, { { 1 }, { 2 } } 의 5가지가 존재한다는 것을 보아도 알 수 있습니다.
일반적으로는 U 의 원소의 개수가 n 개 일 때에는, ( 3^n + 1 ) / 2 개의 쌍이 존재합니다.
그렇네요. 제 풀이에서 말씀대로 2nCn 의 경우는 반으로 나눠야만 하네요. 즉 제 풀이는 틀렸네요.
2^n 이 잘못된 것 같지가 않았는데 도저히 뭐가 잘못된 지 몰라서 어떻게 하면 147이 나올까 역추적하다보니 이런 결과가 나온 듯 싶습니다.