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,4,6\}$ 과 공집합은 합-자유이지만 $\{1,4,5\}$ 는 그렇지 않다. $\{1,2,3,...,20\}$ 의 합-자유 부분집합이 가질 수 있는 원소 개수의 최댓값은 얼마인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

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

주어진 것: 전체 집합은 $\{1,2,3,\dots,20\}$이다; 합-자유 집합이란 모든 원소 $x,y$(같아도 됨)에 대해 합 $x+y$가 그 집합에 속하지 않는 집합이다; $\{1,4,6\}$은 합-자유이지만, $\{1,4,5\}$는 $1+4=5$이므로 합-자유가 아니다; 선택지: (A) $8$, (B) $9$, (C) $10$, (D) $11$, (E) $12$

구하는 것: $\{1,2,\dots,20\}$의 합-자유 부분집합이 가질 수 있는 최대 크기

이해

계획

주요 도구: #14 극단의 원리

보조 도구: #7 작은 문제로 쪼개기, #6 추측하고 확인하기, #16 관점 바꾸기, #2 빠짐없이 나열하기, #3 가능성 지우기

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

실행 — 정답: C

#6 추측하고 확인하기 2.NBT.B.5 단계 1

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

먼저 실제로 작동하는 집합을 하나 찾자.
가장 큰 열 개의 수 $A=\{11,12,13,\dots,20\}$를 추측한다.
두 원소의 합 중 가장 작은 것은 $11+11=22$이고, 나머지 합은 모두 그보다 크다.
$22>20$이므로 두 원소의 합은 애초에 범위 안으로 돌아올 수 없고, 당연히 $A$ 안에도 들어갈 수 없다.
따라서 $A$는 합-자유이고 원소가 $10$개이다.
(모든 홀수 집합 $\{1,3,5,\dots,19\}$도 작동한다.
홀수 $+$ 홀수는 짝수인데 짝수가 하나도 없어서 맞힐 대상이 없기 때문이다.) 이로써 $10$은 도달 가능하다.

$$A=\{11,12,\dots,20\},\qquad \min\text{-합}=11+11=22>20\;\Rightarrow\;|A|=10$$

💡 두 수를 더하면 이미 $20$을 넘어버릴 만큼 큰 수들만 고르면, 어떤 합도 되돌아올 수 없다.

#14 극단의 원리 2.OA.C.3 단계 2

가장 큰 원소에 집중하기

이제 $10$을 절대 넘을 수 없음을 증명하자.
임의의 합-자유 부분집합 $A$를 잡고, 그 가장 큰 원소를 $m$이라 하자.
이것이 극단의 원리이다.
집합 전체를 저글링하는 대신 경계값 하나를 고정하고 그것이 나머지 전부를 옭아매게 한다.
$m$ 이상인 원소는 $m$ 자신뿐이고, $A$의 다른 원소들은 모두 $\{1,2,\dots,m-1\}$ 안에, 즉 $m$보다 엄격히 작은 곳에 있다.

$$m=\max A,\qquad A\setminus\{m\}\subseteq\{1,2,\dots,m-1\}$$

💡 가장 큰 원소가 천장을 정하므로, 모든 사건은 그 아래에서 일어난다.

#16 관점 바꾸기 2.OA.B.2 단계 3

합이 m이 되도록 짝짓기

$m$보다 작은 수들을 합이 $m$이 되는 여집합 짝으로 묶는다: $\{1,m-1\},\{2,m-2\},\{3,m-3\},\dots$.
핵심은 이것이다.
$m$이 $A$에 있으므로 어떤 짝도 통째로 $A$에 들어갈 수 없다.
만약 $x$와 $m-x$가 둘 다 $A$에 있다면 그 합 $x+(m-x)=m$이 $A$의 원소가 되어 금지된 상황이 된다.
따라서 각 짝은 $A$에 최대 하나만 넘겨줄 수 있다.

$$\{x,\,m-x\}:\ x+(m-x)=m\in A\ \text{금지}\;\Rightarrow\;x,\,m-x\ \text{중 최대 하나만 }A\text{에}$$

💡 금지된 합을 이루는 두 수는 동시에 초대될 수 없다.

#2 빠짐없이 나열하기 3.OA.D.9 단계 4

m이 홀수일 때 상한 세기

$m$이 홀수, $m=2k-1$이라 하자.
그러면 수 $1,\dots,m-1$은 남는 것 없이 $k-1$개의 여집합 짝으로 딱 나뉜다: $\{1,m-1\},\{2,m-2\},\dots,\{k-1,k\}$.
각 짝은 최대 하나를 주고 $m$ 자신이 하나 더해지므로 $|A|\le (k-1)+1=k=\tfrac{m+1}{2}$이다.
$20$ 이하의 가장 큰 홀수 $m$은 $19$이고, $\tfrac{19+1}{2}=10$이 된다.

$$m=2k-1:\ |A|\le (k-1)+1=\tfrac{m+1}{2}\le \tfrac{19+1}{2}=10$$

💡 홀수 꼭대기는 아래 수들을 깔끔하게 짝지어, 그 절반(에 꼭대기 하나)이 천장이 된다.

#14 극단의 원리 2.OA.C.3 단계 5

m이 짝수일 때 상한 세기

$m$이 짝수, $m=2k$라 하자.
짝은 $\{1,m-1\},\dots,\{k-1,k+1\}$이고 가운데 수 $k$가 홀로 남는다.
그런데 $k$도 금지된다.
$k+k=2k=m$이 $A$에 있으므로 $k$는 합류할 수 없다.
그래서 짝 $k-1$개(각각 최대 하나)에 $m$ 자신을 더해 $|A|\le (k-1)+1=k=\tfrac{m}{2}\le\tfrac{20}{2}=10$이다.
이 경우에도 상한은 $10$이다.

$$m=2k:\ k+k=m\in A\ \text{로 }k\text{ 금지};\quad |A|\le (k-1)+1=\tfrac{m}{2}\le\tfrac{20}{2}=10$$

💡 짝수 꼭대기는 자기 절반값도 막아버려서, 천장은 여전히 정확히 $m$의 절반이다.

#3 가능성 지우기 3.OA.D.9 단계 6

종합하고 11과 12 지우기

두 경우 모두 임의의 합-자유 부분집합에 대해 $|A|\le 10$이므로 $11$과 $12$는 불가능하고, (D)와 (E)가 지워진다.
1단계에서 크기 $10$인 집합을 실제로 만들었으므로 이 상한은 달성된다.
따라서 원소의 최대 개수는 정확히 $10$이고, 선택지 (C)이다.

$$|A|\le 10\ \text{항상},\ \text{그리고}\ 10\ \text{달성 가능}\;\Rightarrow\;\max|A|=10\ \textbf{(C)}$$

💡 증명된 천장 $10$과 실제 예시 $10$이 만나면 답이 정확히 못 박힌다.

[1] #6 2.NBT.B.5 먼저 실제로 작동하는 집합을 하나 찾자. 가장 큰 열 개의 수 $A=\{11,12,13,\dots,20\}$를 추측한다. 두 원소의 합 중 가장

[2] #14 2.OA.C.3 이제 $10$을 절대 넘을 수 없음을 증명하자. 임의의 합-자유 부분집합 $A$를 잡고, 그 가장 큰 원소를 $m$이라 하자. 이것이 극단의 원

[3] #16 2.OA.B.2 $m$보다 작은 수들을 합이 $m$이 되는 여집합 짝으로 묶는다: $\{1,m-1\},\{2,m-2\},\{3,m-3\},\dots$. 핵심은

[4] #2 3.OA.D.9 $m$이 홀수, $m=2k-1$이라 하자. 그러면 수 $1,\dots,m-1$은 남는 것 없이 $k-1$개의 여집합 짝으로 딱 나뉜다: ${1

[5] #14 2.OA.C.3 $m$이 짝수, $m=2k$라 하자. 짝은 $\{1,m-1\},\dots,\{k-1,k+1\}$이고 가운데 수 $k$가 홀로 남는다. 그런데 $

[6] #3 3.OA.D.9 두 경우 모두 임의의 합-자유 부분집합에 대해 $|A|\le 10$이므로 $11$과 $12$는 불가능하고, (D)와 (E)가 지워진다. 1단계에

검토

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

대안 접근: 짝짓기 대신 $\{1,\dots,20\}$을 두 절반 $L=\{1,\dots,10\}$과 $H=\{11,\dots,20\}$으로 나눠 생각해도 된다. $H$만으로도 이미 원소 $10$개의 합-자유 집합이므로 답은 적어도 $10$이고, 3단계의 여집합-짝 상한(가장 큰 원소에 적용)이 $10$을 결코 넘을 수 없음을 보여준다. 이 '위쪽 절반 구성 + 극단 원소 상한'은 $\{1,\dots,n\}$의 최대 합-자유 부분집합이 $\lceil n/2\rceil$개의 원소를 가진다는 고전적 결과로 가는 표준 경로이며, 여기서는 $\lceil 20/2\rceil=10$이다.

사용된 CCSS 표준 (최저 학년 3)

2.NBT.B.5 Fluently add and subtract within 100 (구성 확인: 가장 작은 합 $11+11=22$가 $20$을 넘으므로 $\{11,\dots,20\}$이 합-자유임을 확인한다.)
2.OA.C.3 Determine whether a group of objects has an odd or even number (가장 큰 원소 $m$의 홀짝으로 논증을 나누고, 짝수 $m$이 $k+k=m$을 통해 자기 절반 $k$를 막는 것을 파악한다.)
2.OA.B.2 Fluently add and subtract within 20 using mental strategies (합이 $m$이 되는 여집합 짝 $\{x, m-x\}$을 만든다($m\le 20$).)
3.OA.D.9 Identify arithmetic patterns and explain using properties of operations ('짝당 최대 하나' 패턴을 인식해 개수 $m/2$로 바꾸고, 상한 $10$으로 $11$과 $12$를 지운다.)

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