AMC 10 · 2025 · #21

학년 3 number-theory

유형 Pair-Sum Invariant └ 세부 유형 Forbidden-Complement Selection

sum-free-setpair-countingparity extremal-construction ↑ 선수 지식: sum-free-set

📏 긴 풀이 💡 3 개 인사이트

문제

어떤 집합에서 두 원소(x와 y, 서로 같아도 됨)를 골라 더한 값 x+y가 그 집합의 원소가 되는 일이 절대 없을 때, 그 집합을 합-자유(sum-free) 집합이라 하자. 1부터 20까지의 자연수만 사용할 때, 합-자유 부분집합이 가질 수 있는 원소의 최대 개수를 구하라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 극단의 원리

'최대 크기' 문제는 사실 두 개의 작은 문제이다(도구 #7): 목표 크기에 도달하는 집합을 하나 만들고, 그보다 큰 집합은 없음을 증명하는 것. 만드는 일은 추측하고 확인하기(도구 #6)로 빠르게 끝난다. 증명의 핵심은 도구 #14(극단의 원리)이다. 복잡한 집합 전체를 다루는 대신, 그 집합의 가장 큰 원소 m 하나에만 집중한다. 이 극단값을 고정하면 그 아래의 모든 수에 강한 구조가 생긴다. 그 구조를 만드는 엔진이 여집합 짝짓기(도구 #16)이다. m보다 작은 수들을 합이 m이 되는 짝 {x, m-x}으로 묶으면, m이 집합에 있으므로 어떤 짝도 통째로 집합 안에 들어갈 수 없다. 그 짝들을 나열하면(도구 #2) 개수가 정확히 세어지고, 그 상한을 선택지와 비교하면(도구 #3) 11과 12를 지울 수 있다.

1STEP 1

크기 10인 합-자유 집합 만들기

A={11,12,…,20}은 가장 작은 합이 11+11=22라 20을 넘으므로, 원소 10개짜리 합-자유 집합이다.

A={11,12,…,20}, min-합=11+11=22 ＞ 20 → |A|=10

2STEP 2

가장 큰 원소에 집중하기

이제 상한. 임의의 합-자유 집합 A에서 가장 큰 원소를 m이라 하면, 나머지 원소는 모두 {1,2,…,m-1} 안에 있다.

m=max A, A∖{m}⊆{1,2,…,m-1}

3STEP 3

합이 m이 되도록 짝짓기

m보다 작은 수를 x와 m-x로 짝짓는다. 둘 다 A에 있으면 합 m이 A에 있어 금지되므로, 각 짝은 최대 하나만 준다.

{x, m-x}: x+(m-x)=m∈ A 금지 → x, m-x 중 최대 하나만 A에

4STEP 4

m이 홀수일 때 상한 세기

홀수 m=2k-1이면 아래 수들이 k-1개 짝으로 딱 나뉘어 |A|는 최대 (m+1)/2, m=19에서 10.

m=2k-1: |A| ≤ (k-1)+1=(m+1)/2 ≤ (19+1)/2=10

5STEP 5

m이 짝수일 때 상한 세기

짝수 m=2k면 k+k=m이라 홀로 남는 가운데 k도 금지되어, |A|는 최대 m/2로 여전히 10.

m=2k: k+k=m∈ A 로 k 금지; |A| ≤ (k-1)+1=m/2 ≤ 20/2=10

6STEP 6

종합하고 11과 12 지우기

두 경우 모두 상한이 걸려 11과 12는 불가능하고, 1단계가 그 상한에 도달했으니 최댓값은 정확히 10, 선택지 (C).

|A| ≤ 10 항상, 그리고 10 달성 가능 → max|A|=10 (C)

정답

상한 |A| ≤ m/2 ≤ 10은 양쪽에서 딱 맞다. 홀수 꼭대기 m=19는 모든 홀수 집합 {1,3,…,19}(크기 10)을 주고, 짝수 꼭대기 m=20은 {11,…,20}(크기 10)을 주어 상한과 일치한다. 선택지(8부터 12)가 20의 절반 근처에 몰려 있는 것도 짝짓기 논증이 예측하는 바와 정확히 맞고, 그 논증은 11과 12가 불가능함을 보여준다. 함정 점검: 작은 수 {1,2,…}부터 모으면 1+2=3이라 즉시 실패한다. 즉 범위가 넓다고 집합이 커지는 게 아니라, 천장은 20 아래 여유가 얼마나 남았느냐가 아니라 구조에서 나온다.

💡핵심 정리

집합에서 가장 큰 수를 보라. 그보다 작은 수들은 그 큰 수를 합으로 만드는 짝으로 나뉘고, 각 짝은 한 명만 빌려줄 수 있으니, 합-자유 집합은 1부터 20까지의 절반인 열 개까지만 담을 수 있다.

크기 10인 합-자유 집합 만들기
가장 큰 원소에 집중하기
합이 m이 되도록 짝짓기
m이 홀수일 때 상한 세기
m이 짝수일 때 상한 세기
종합하고 11과 12 지우기