AMC 10 · 2022 · #14

학년 6 arithmetic

sum-free-setset-partitionextremal-constructionpattern-recognition easier-related-problempattern-recognitioncomplementary-counting ↑ 선수 지식: set-partitionsystematic-enumeration

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

문제

Suppose that $S$ is a subset of $\left\{ 1, 2, 3, \ldots , 25 \right\}$ such that the sum of any two (not necessarily distinct) elements of $S$ is never an element of $S.$ What is the maximum number of elements $S$ may contain?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $\{1, 2, 3, \ldots, 25\}$ 의 부분집합 $S$ 를 고르는데, 규칙은 단 하나: $S$ 의 두 원소(같은 원소를 두 번 골라도 됨) 의 합이 $S$ 의 원소가 아니어야 합니다. $S$ 의 최대 크기는?

주어진 것: 전체 집합 $U = \{1, 2, 3, \ldots, 25\}$; 규칙: $x, y \in S$ ($x = y$ 가능) 이면 $x + y \notin S$; 선택지: (A) 12, (B) 13, (C) 14, (D) 15, (E) 16

구하는 것: $|S|$ 의 최댓값

이해

주어진 것: 전체 집합 $U = \{1, 2, 3, \ldots, 25\}$; 규칙: $x, y \in S$ ($x = y$ 가능) 이면 $x + y \notin S$; 선택지: (A) 12, (B) 13, (C) 14, (D) 15, (E) 16

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #5 패턴 찾기, #1 그림 그리기, #16 관점 바꾸기, #3 가능성 지우기

도구 #9(더 쉬운 문제): 먼저 $\{1, \ldots, 5\}$ 로 줄여 보기. $\{3, 4, 5\}$ 는 가장 작은 합이 $3 + 3 = 6 > 5$ 라 안전 — 3 개 가능. 이는 "위쪽 절반" 아이디어를 알려줍니다 — 큰 수만 고르면 모든 합이 전체 집합을 벗어남. 도구 #5(패턴): $\{1, \ldots, n\}$ 에서 위쪽 절반 가족 $\{\lceil n/2 \rceil + 1, \ldots, n\}$ 은 약 $\lceil n/2 \rceil$ 개; $n = 25$ 면 $\{13, \ldots, 25\}$ 의 13 개. 도구 #1(그림): 1-25 의 수직선에 후보를 표시하면 $i$ 와 $25 - i$ (또는 $S$ 의 최댓값 $M$) 의 쌍짓기로 둘 중 하나만 $S$ 에 들어갈 수 있음이 보입니다. 도구 #16(관점 바꾸기) 가 그 상한을 깔끔히 정리: 쌍 $(1,24), (2,23), \ldots, (12,13)$ 이 최대 12 개 + 최댓값 $M$ 자체 = 최대 13. 도구 #3(가능성 지우기) 으로 13 이 선택지에서 14, 15, 16 을 이김.

실행 — 정답: B

#9 더 쉬운 문제로 줄이기 3.OA.D.8 단계 1

$\{1, 2, 3, 4, 5\}$ 로 워밍업.
위쪽 절반 시도: $S = \{3, 4, 5\}$.
가장 작은 두 원소의 합은 $3 + 3 = 6$, 이미 전체 집합 밖이므로 어떤 합도 $S$ 로 돌아올 수 없음.
3 개 원소가 깔끔히 가능.

$$S = \{3, 4, 5\} \subset \{1, \ldots, 5\}; \; \min(x+y) = 6 > 5$$

💡 3학년 두 단계 응용: 작은 사례에서 큰 수만 고르면 합이 원래 집합 밖으로 나감을 봅니다.

#5 패턴 찾기 4.OA.A.3 단계 2

$\{1, \ldots, 25\}$ 에 같은 수법 적용.
$S = \{13, 14, 15, \ldots, 25\}$ 고르기.
원소 수는 $25 - 13 + 1 = 13$.
가장 작은 합은 $13 + 13 = 26 > 25$ 이므로 어떤 쌍의 합도 $S$ 안에 안 들어옴.
13 개 달성 가능.

$$S = \{13, 14, \ldots, 25\}; \;|S| = 13; \; \min(x+y) = 26 > 25$$

💡 4학년 여러 단계: "절반 이상에서 시작" 패턴을 그대로 옮기면 합이 전체 집합을 넘어감.

#1 그림 그리기 5.G.B.3 단계 3

이제 14 가 불가능함을 보이기 — 상한 증명.
$M$ 을 $S$ 의 최댓값이라 합시다.
$1 \le i < M/2$ 인 각 쌍 $(i, M - i)$ 에 대해 둘 다 $S$ 에 있으면 합이 $M \in S$ 가 되어 규칙 위반.
따라서 각 쌍에서 최대 하나만 $S$ 에.
$M$ 이 짝수이면 가운데 값 $M/2$ 도 $\tfrac{M}{2} + \tfrac{M}{2} = M \in S$ 이므로 $S$ 에서 제외.

$$i + (M - i) = M \in S \Rightarrow \text{쌍에서 최대 하나만 } S \text{ 에}$$

💡 5학년 속성·하위집단: 쌍 $(i, M-i)$ 는 "하나만 고름" 슬롯처럼 작동.

#16 관점 바꾸기 4.OA.A.3 단계 4

쌍 개수 세기.
$1, 2, \ldots, M - 1$ 중 쌍 $(i, M - i)$ 는 약 $\lfloor (M - 1) / 2 \rfloor$ 개.
거기에 $M$ 자신 한 개를 더하면 $|S| \le \lfloor (M-1)/2 \rfloor + 1 = \lceil M / 2 \rceil$.
$M$ 의 최댓값은 25, 따라서 $\lceil 25/2 \rceil = 13$.

$$|S| \le \lceil M / 2 \rceil \le \lceil 25 / 2 \rceil = 13$$

💡 4학년: 쌍은 "둘 중 하나 고르기" — 정확히 여사건 스타일의 세기 트릭.

#9 더 쉬운 문제로 줄이기 6.EE.B.5 단계 5

두 결과 결합.
2 단계 구성이 $|S| = 13$ 을 달성, 4 단계 상한이 $|S| \le 13$ 을 줌.
따라서 최댓값은 정확히 13.

$$\max |S| = 13$$

💡 6학년: 도달 가능한 상한이 곧 최댓값 — 두 결과 사이에 빈틈이 없음.

#3 가능성 지우기 6.EE.B.5 단계 6

13 을 선택지와 매칭: (B).

$$13 \;\Rightarrow\; \textbf{(B)}$$

💡 마지막 비교 — 13 은 (B) 하나뿐.

[1] #9 3.OA.D.8 $\{1, 2, 3, 4, 5\}$ 로 워밍업. 위쪽 절반 시도: $S = \{3, 4, 5\}$. 가장 작은 두 원소의 합은 $3 + 3 =

[2] #5 4.OA.A.3 $\{1, \ldots, 25\}$ 에 같은 수법 적용. $S = \{13, 14, 15, \ldots, 25\}$ 고르기. 원소 수는 $25

[3] #1 5.G.B.3 이제 14 가 불가능함을 보이기 — 상한 증명. $M$ 을 $S$ 의 최댓값이라 합시다. $1 \le i < M/2$ 인 각 쌍 $(i, M -

[4] #16 4.OA.A.3 쌍 개수 세기. $1, 2, \ldots, M - 1$ 중 쌍 $(i, M - i)$ 는 약 $\lfloor (M - 1) / 2 \rfloor

[5] #9 6.EE.B.5 두 결과 결합. 2 단계 구성이 $|S| = 13$ 을 달성, 4 단계 상한이 $|S| \le 13$ 을 줌. 따라서 최댓값은 정확히 13.

[6] #3 6.EE.B.5 13 을 선택지와 매칭: (B).

검토

합리성 확인: 또 다른 13 개 가족으로 교차 확인: 1 부터 25 까지의 홀수 $\{1, 3, 5, \ldots, 25\}$ 도 정확히 13 개. 두 홀수의 합은 짝수, 그런데 우리 집합엔 짝수가 없으므로 $x + y \notin S$ 가 자동으로 성립. 전혀 다른 두 가족이 모두 13 개에 도달하고 상한도 13 이라는 점이 답을 강력히 지지. $\{13, \ldots, 25\}$ 의 원소 수도 $25 - 13 + 1 = 13$ 으로 일치.

대안 접근: 도구 #2(나열) 만으로 직접: 14 개로 늘리려고 시도. 14 개 가장 큰 원소들엔 12 이하의 어떤 수 $a$ 가 포함되어야 함. 그러나 $a + 13$ 은 $\{13, \ldots, 25\}$ 안에 들어가므로 규칙 위반. 14 번째 원소를 어디 넣어도 기존 두 원소가 그 값을 합으로 만들어 줌 — 쌍 상한 논증을 실제로 손으로 확인하는 방법.

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

3.OA.D.8 100 이내 네 연산을 이용한 두 단계 응용 문제 풀기 ($\{1, \ldots, 5\}$ 워밍업에서 $\{3, 4, 5\}$ 고르고 최소 합 $3+3=6 > 5$ 확인하는 데 사용.)
4.OA.A.3 자연수 네 연산을 이용한 여러 단계 응용 문제 풀기 (워밍업 패턴을 $\{1, \ldots, 25\}$ 에 옮겨 $\{13, \ldots, 25\}$ 구성, 그리고 쌍 구조 $1 + \lfloor (M-1)/2 \rfloor$ 로 상한 세는 데 사용.)
5.G.B.3 한 범주에 속하는 속성은 그 모든 하위 범주에도 적용됨을 이해하기 (각 쌍 $(i, M-i)$ 을 "하나만 들어갈 수 있는" 하위 슬롯으로 보는 데 사용.)
6.EE.B.5 방정식·부등식 풀기를 "값 찾기" 과정으로 이해하기 ("$|S| \le 13$" 과 달성 가능한 "$|S| = 13$" 을 결합해 최댓값을 13 으로 확정하고 (B) 와 매칭하는 데 사용.)

⭐ 이 AMC 10 문제는 사실 6학년 때 배운 쌍짓기와 범주 멤버십만 알면 풀 수 있어요! 위쪽 절반 가족 $\{13, \ldots, 25\}$ 는 모든 합이 25 를 넘어 안전, 그리고 쌍 $(i, 25-i)$ 짓기로 13 이 최댓값임도 증명할 수 있어요.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: B

검토

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

비슷한 유형 더 풀어보기