AMC 10 · 2024 · #12

학년 8 arithmetic

유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint

combinations-basicset-partitionlogical-deduction easier-related-problembound-inequality-then-enumeratecomplementary-counting ↑ 선수 지식: combinations-basicset-partition

📏 중간 풀이 💡 3 개 인사이트

문제

수학 경시대회에 100 명의 학생이 모였습니다. 모든 학생은 같은 수(k)의 언어를 구사하고, 임의의 두 학생을 골라도 서로 상대가 모르는 언어를 적어도 하나씩 알고 있습니다. 이때 학생들 전체가 사용하는 서로 다른 언어의 개수 n 의 최솟값을 구하세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

100

AMC 10 2024 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정

전략 더 쉬운 문제로 줄이기

"상대가 모르는 언어를 서로 안다" 는 표현은 말로는 까다롭지만 집합으로 풀면 깔끔합니다 — 두 학생 모두 정확히 k 개를 알고 어느 쪽도 다른 쪽의 부분집합이 아니라면, 두 집합은 서로 다른 집합입니다. 도구 #9(더 쉬운 문제로 줄이기)로 추상도를 낮춥니다: n=2, k=1 이면 가능한 학생은 최대 C(2, 1)=2 명; n=3 이면 최대 3 명; 패턴은 "학생 수 ≤ C(n, k)". 그다음 도구 #6(추측하고 확인하기)으로 n = 7, 8, 9 를 순서대로 시험해 C(n, k) 가 처음으로 100 을 넘는 지점을 찾고 (k 는 $\frac{n}{2}$ 근처가 최대), 도구 #16(관점 바꾸기)이 "서로 모르는 언어가 있다" 는 양방향 조건을 "두 집합이 서로 부분집합이 아님" 한 개로 줄여줍니다 — 크기가 같다는 가정 위에서는 사실상 "서로 다른 집합" 과 같습니다.

1STEP 1

말을 집합으로: 크기가 같은 k 라서 "서로 포함 안 됨" 은 곧 두 집합이 다름.

|L_A| = |L_B| = k 이고 L_A ≠ L_B ⟺ 조건 성립

2STEP 2

작은 경우로: n 개 언어의 서로 다른 k-부분집합은 C(n, k) 개, 그래서 학생 수는 최대 C(n, k).

학생 수 ≤ C(n, k)

3STEP 3

목표: C(n, k) ≥ 100 을 만족하는 최소 n. C(n, k) 는 k 가 $\frac{n}{2}$ 근처일 때 최대라 그 값만 보면 됨.

min { n : max_k C(n, k) ≥ 100 }

4STEP 4

확인: C(7, 3)=35, C(8, 4)=70 은 부족, C(9, 4)=126 ≥ 100 통과 — n = 9, k = 4 가 처음.

C(7, 3)=35, C(8, 4)=70, C(9, 4)=126

5STEP 5

구성: 9 개 언어에서 서로 다른 4-집합을 학생마다 배정 — 126 개 존재, 모두 크기 같아 포함관계 없음. 최솟값 9.

n = 9, k = 4, C(9, 4) = 126 ≥ 100 → (A)

정답

100 명한테 언어 9 개는 너무 적어 보이지만, C(9, 4)=126 — 이항계수는 정말 빨리 자랍니다. 직관 점검: 9 개 언어 중 4 개씩 골라 두 학생이 "하나만 다른" 식으로도 조건을 만족시킬 수 있을 만큼 조건이 느슨합니다. 다른 선택지들 10, 12, 51, 100 은 모두 과잉 — 51 은 "각자 모국어 + 그 외 50 중 하나" 같은 발상이지만 셈이 맞지 않고, 100 은 "학생당 언어 하나" 라는 자명한 상한일 뿐입니다. (A) 가 조합론적 직관을 정확히 짚어줍니다.

💡핵심 정리

이 AMC 10 문제는 사실 7학년 "부분집합 세기" 조합 — C(n, k) — 만 알면 풀 수 있어요!

비슷한 유형 더 풀어보기