AMC 10 · 2024 · #12

• 언어 조건을 집합으로 바꿉니다.
• 학생 $A$ 의 언어 집합을 $L_A$ 라 하면, "$A$ 는 $B$ 가 모르는 언어를 안다" 는 $L_A \not\subseteq L_B$, "$B$ 는 $A$ 가 모르는 언어를 안다" 는 $L_B \not\subseteq L_A$.
• $|L_A| = |L_B| = k$ 와 합치면 결국 $L_A \neq L_B$ — 같은 크기의 두 집합이 서로 포함관계에 있으면 같은 집합이므로, "포함관계 아님" 은 "같지 않음" 과 같습니다.

💡 크기가 같은 두 집합은 포함관계라면 곧 같은 집합이라, "포함 아님" 이 "다름" 으로 줄어듭니다 — 점검 한 번이면 충분.

• 더 쉬운 경우로 구조를 봅니다.
• $n$ 개 언어가 있을 때, 서로 다른 $k$-원소 부분집합의 개수는 $\binom{n}{k}$.
• 그래서 $(n,k)$ 가 감당할 수 있는 학생 수는 최대 $\binom{n}{k}$.
• $n=3$ 이면 $\binom{3}{1}=\binom{3}{2}=3$, 최대 $3$ 명.
• $n=4$ 면 $\binom{4}{2}=6$, 최대 $6$ 명.
• 결국 $\binom{n}{k}$ 만 보면 됩니다.

💡 $100$ 명을 $3, 4$ 명으로 줄여서 셈해 보면 일반 한계 $\binom{n}{k}$ 가 그대로 튀어나옵니다 — Polya 의 "유추 원리".

• 탐색 범위를 정합니다.
• $\binom{n}{k} \geq 100$ 을 만족시키는 가장 작은 $n$ 을 찾는 것이 목표.
• 각 $n$ 에 대해 $\binom{n}{k}$ 는 $k$ 가 $n/2$ 에 가장 가까울 때 최대이므로, 그 한 값만 보면 충분합니다.

💡 $\binom{n}{\lfloor n/2 \rfloor}$ 은 파스칼 삼각형 $n$ 번째 줄의 가운데 항으로 그 줄 중 가장 큰 수, 그것만 확인하면 줄 전체가 정해집니다.

• $n = 7, 8, 9$ 를 차례로 확인.
• $\binom{7}{3} = 35 < 100$.
• $\binom{8}{4} = 70 < 100$.
• $\binom{9}{4} = 126 \geq 100$.
• 즉 가운데 항이 $100$ 을 처음 넘는 파스칼 줄은 $n = 9$ 이고, $k = 4$ 가 작동합니다.

💡 $n$ 을 하나씩 올리면 가운데 이항계수는 대략 두 배씩 커지니, $100$ 을 빠르고 깔끔하게 넘깁니다.

• 실제로 구성해서 검증합니다.
• $n = 9$, $k = 4$ 일 때 가능한 $4$-원소 부분집합 $126$ 개 중 서로 다른 $100$ 개를 골라 학생들에게 하나씩 배정.
• 모두 크기 $4$ 이고 서로 다르므로 포함관계가 아닙니다 — 조건 성립.

💡 한계만으로는 부족하고 "진짜 그렇게 만들 수 있다" 는 구성까지 보여야 최솟값이 확정됩니다 — $9$ 는 되고 $8$ 은 안 되니 답.