포함배제의 원리 고난도 문제

문제

1부터 $n$까지의 번호를 붙인 $n$장의 카드가 있다. $2l \leq n$을 만족하는 자연수 $l$이 있다. $1 \leq k \leq l$인 각 정수 $k$에 대해 $2k-1$와 $2k$의 번호 카드를 페어라 생각하자. 이 $n$장의 카드를 $X, Y, Z$의 세 상자에 나눠 넣는다. 세 상자 중 적어도 한 상자에 하나 이상의 페어가 있는 경우의 수를 구하시오. 단, 어떤 상자에도 적어도 한 장은 넣는다고 하자.

풀이

포함-배제의 원리에 관한 문제 중 최고난도 수준이 아닐까 싶습니다.
이렇게 복잡하고 헷갈리는 포함-배제 문제는 집합을 올바르게 설정하는 것이 무엇보다 중요합니다.
다음과 같이 집합을 설정합시다.

 

$A = \text{어떤 상자에도 적어도 한 장은 넣는 경우}$

$B=\text{세 상자 중 적어도 한 상자에 하나 이상의 페어가 있는 경우}$

 

이를 논리기호를 이용해서 조금 더 명확히 표현하면 다음과 같습니다.

 

$A = \forall \text{상자, 카드의 수}\geq 1$

$B=\exists \text{상자, 페어의 수}\geq 1$

 

이 둘의 부정은 다음과 같습니다.

 

$A^c = \exists \text{상자, 카드의 수}= 0$

$B^c=\forall \text{상자, 페어의 수}= 0$

 

부정의 경우, 부등식이 아닌 등호로 깔끔하게 표현되기 때문에 계산하기 수월해 보입니다.
따라서 $A, B$가 아닌 $A^c, B^c$를 이용해 문제를 접근하도록 하겠습니다.

포함-배제의 원리

구하고자 하는 경우는 $n(A\cap B)$입니다. 이는 다음과 같이 구할 수 있습니다.
$$
n(A \cap B)=n(U)-n(A\cap B)^c=n(U)-n(A^c\cup B^c)
$$
그리고 $n(U)$는 전체 경우이므로, $3^n$임을 쉽게 알 수 있습니다.
포함-배제의 원리로부터 $n(A^c \cup B^c)$는 다음과 같이 구할 수 있습니다.
$$
n(A^c \cup B^c)=n(A^c)+n(B^c)-n(A^c \cap B^c)
$$
따라서 $n(A^c), n(B^c), n(A^c \cap B^c)$를 구하면 문제는 해결됩니다.

$n(A^c)$

먼저 $n(A^c)$, 카드가 하나도 없는 상자가 존재하는 경우의 수를 구해봅시다.
$X, Y, Z$에 카드가 하나도 없는 경우의 수를 각각 $n(X), n(Y), n(Z)$라고 하면,
우리가 구하고자 하는 경우의 수는 $n(X\cup Y\cup Z)$입니다. 포함-배제의 원리로부터 이는,
$$
n(X\cup Y \cup Z)=n(X)+n(Y)+n(Z)-n(X\cap Y)-n(Y \cap Z)-n(Z \cap X)+n(X\cap Y \cap Z)
$$
입니다. 이 문제는 포함-배제 속에 포함-배제가 들어있는 까다로운 문제네요.
$n(X)$는 $Y, Z$에만 카드를 분배하는 경우이므로 $2^n$입니다.
마찬가지로 $n(Y)=n(Z)=2^n$입니다.

$n(X\cap Y)$는 $Z$에만 카드를 분배하는 경우이므로 $1$입니다.
마찬가지로 $n(Y \cap Z)=n(Z \cap X)=1$입니다.

$n(X \cap Y \cap Z)$는 불가능합니다. 따라서 $0$입니다.
따라서 $n(A^c)=n(X\cup Y \cup Z) = 3\cdot 2^n - 3$입니다.

$n(B^c)$

다음, 모든 상자에 페어가 없는 경우인 $n(B^c)$를 구해봅시다.
먼저 페어에 대해 조금 더 직관적으로 이해해 봅시다. $n=8, l=3$인 경우, 페어는
$$
(1, 2), (3, 4), (5, 6)
$$
이 되며, $7, 8$은 아무 페어를 이루지 않습니다.

그러면 이렇게 생각해 봅시다. 먼저 페어를 이루는 수 중 홀수($1, 3, 5$)를 3개의 상자에 배열합니다.
그러면 짝수($2, 4, 6$)는 자신과 페어를 이루는 홀수를 피해서 상자에 넣어야 합니다.
예를 들어서 $1$이 1번 상자에 있다면 $2$는 1번 상자가 아닌 2번, 3번 상자에 들어가야 합니다.
나머지 $n-2l$개의 수는 아무 눈치 보지 않고 3개의 상자에 들어가면 됩니다.

따라서 $n(B^c)=3^l(\text{홀수 배열})\times 2^l(\text{짝수 배열})\times 3^{n-2l}(\text{나머지 숫자 배열})=3^{n-l}\cdot 2^l$이 됩니다.

$n(A^c \cap B^c)$

마지막입니다. 먼저 $A^c$를 고려해주기 위해 적어도 하나의 상자는 사용하지 말아야 합니다.
그런데 두 개의 상자를 사용하지 않는 것은 불가능합니다.
왜냐하면 하나의 상자만 남아 $B^c$의 "페어를 이루지 않는다"는 조건을 만족시킬 수 없기 때문입니다.

따라서 단 하나의 상자가 비고, 나머지 두 개의 상자에 페어를 이루지 않게 카드를 넣으면 됩니다.
편의상 1번 상자가 빈다고 합시다. 페어가 없도록 2번, 3번 상자에 카드를 넣어야 합니다.
이를 위해 어떤 홀수가 2번에 들어가면 해당하는 짝수는 3번에, 홀수가 3번에 들어가면 해당하는 짝수는 2번에 들어가야 합니다. 따라서 페어가 없도록 하는 경우의 수는 $2^l$임을 알 수 있습니다.

한편 나머지 $n-2l$개의 수는 아무렇게나 2개의 상자에 넣으면 됩니다.
빈 상자를 고르는 경우의 수가 $3$이므로, $n(A^c \cap B^c)=3\cdot 2^l\cdot 2^{n-2l} = 3\cdot 2^{n-l}$임을 알 수 있습니다.

결론

따라서 $n(A^c \cup B^c)=3\cdot 2^n - 3 + 3^{n-l}\cdot 2^l - 3\cdot 2^{n-l}$입니다.
이로부터 $n(A\cap B)=3^n-3\cdot 2^n + 3 - 3^{n-l}\cdot 2^l + 3\cdot 2^{n-1}$이 됩니다.

교훈

• 복잡한 포함-배제의 원리는 머리 속에서 하려면 무조건 망칩니다. 반드시 집합을 설정한 뒤 드 모르간의 법칙 등을 응용하여 정확한 집합 처리를 해야 합니다.
• 모든의 부정은 어떤, 어떤의 부정은 모든임을 기억합시다. 논리기호를 사용하여 이를 더 명확히 하면 좋습니다.
• "강요되는 것"들에 집중합시다. 이 문제에서는 홀수의 위치가 짝수의 위치를 강요하는 것이 풀이의 핵심이었습니다.