AMC 10 · 2025 · #15

학년 7 counting
유형 Pair-Sum Invariant └ 세부 유형 Forbidden-Complement Selection
sum-free-setpair-countingparity extremal-constructioncasework ↑ 선수 지식: pair-counting
📏 중간 풀이 💡 3 개 인사이트
문제
1부터 20까지의 수 중에서 부분집합 A를 고른다. 고른 두 수를 더한 값이 또 다른 고른 수와 절대 같아지지 않을 때, 즉 x와 y가 A에 있으면(둘은 같은 수여도 된다) 합 x + y가 A에 없을 때, 이 부분집합을 합-없는(sum-free) 집합이라 한다. 이런 합-없는 부분집합이 가질 수 있는 원소의 최대 개수를 구하여라.

답을 골라 클릭하세요.

(A)
8
(B)
9
(C)
10
(D)
11
(E)
12
풀이 과정
전략 극단의 원리

최대 크기를 묻는 문제는 두 부분으로 이루어진다: 실제로 그만큼 큰 집합을 만들어 보이는 것(하한)과 그보다 큰 것은 존재할 수 없음을 증명하는 것(상한)이다. 잘 고른 큰 집합 하나를 확인하면 하한은 금방 해결된다. 상한을 위한 열쇠는 극단의 원리이다: 어떤 합-없는 집합이든 그 가장 큰 원소 m 하나에 시선을 고정한다. m은 존재하는 가장 큰 수이므로, m을 x + (m - x)로 쓰는 모든 방법이 함정이 되어, m은 자신을 이루는 각 쌍의 한쪽을 금지한다. 그 쌍의 개수를 세면 크기가 제한된다. 극단 원소에 집중하는 것이 막연한 탐색을 깔끔한 셈으로 바꾼다.

1STEP 1

큰 합-없는 집합 만들기

윗절반 {11, …, 20}은 열 개, 11 + 11 = 22로 이미 20을 넘어 어떤 합도 안에 들지 않는다 — 크기 10 집합이 존재한다.

11 + 11 = 22 ＞ 20 → x + y ＞ 20 for all x, y ∈ {11, …, 20}
2STEP 2

가장 큰 원소에 시선 고정하기

가장 큰 원소를 m이라 하자. 짝 m - x는 A에 함께 못 든다, x + (m - x) = m이 한 원소와 같기 때문이다.

x + (m - x) = m → x and m - x cannot both lie in A
3STEP 3

짝을 지어 상한 세기

m 아래의 각 x를 m - x와 짝지으면 각 쌍의 합이 m이라 쌍마다 최대 하나만 남고, m은 많아야 20이라 개수는 10에서 멈춘다.

m even: |A| ≤ m/2 ≤ 10; m odd: |A| ≤ (m+1)/2 ≤ 10
4STEP 4

두 부분이 10에서 만난다

1단계는 10을 만들고 2·3단계는 그 초과를 막으니, 두 경계가 최대를 정확히 10에 못 박는다 — 선택지 (C).

10 ≤ |A|_max ≤ 10 → |A|_max = 10
정답
10
이 경계는 딱 맞고 서로 일관된다. 집합 {11, ..., 20}은 실제로 10을 달성하고, 열 개의 홀수 {1, 3, 5, ..., 19}도 또 하나의 크기-10 증거를 준다. 홀수 + 홀수는 항상 짝수라서 어떤 홀수 원소와도 같아질 수 없기 때문이다. 한편 어떤 집합도 11에는 이를 수 없다: 가장 큰 원소 하나만으로도 자신을 이루는 각 쌍의 한쪽, 즉 작은 수들의 약 절반을 밀어내기 때문이다. 따라서 선택지 (D) 11과 (E) 12는 증명된 상한을 넘고, 10만이 구체적 예와 셈 논증 양쪽에 부합하는 유일한 값이다.
💡핵심 정리

두 원소의 합이 또 다른 원소가 되지 않는 가장 큰 집합을 찾으려면 가장 큰 원소를 보라. 그것은 자신을 이루는 각 쌍에서 한 수를 막으므로, 작은 수의 약 절반은 빠질 수밖에 없다.

  • 큰 합-없는 집합 만들기
  • 가장 큰 원소에 시선 고정하기
  • 짝을 지어 상한 세기
  • 두 부분이 10에서 만난다

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.