AMC 10 · 2022 · #14

학년 6 arithmetic

유형 Small-Domain Constrained Search └ 세부 유형 Logic-Deduction / Elimination

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

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

문제

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

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 더 쉬운 문제로 줄이기

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

1STEP 1

{1, …, 5} 워밍업: 위쪽 절반 S = {3, 4, 5}. 최소 합 3 + 3 = 6 이 전체 밖이라 3 개 가능.

S = {3, 4, 5} ⊂ {1, …, 5}; min(x+y) = 6 ＞ 5

2STEP 2

{1, …, 25} 에 적용: S = {13, …, 25}, 즉 13 개. 최소 합 13 + 13 = 26 ＞ 25 이라 모든 쌍이 안전.

S = {13, 14, …, 25}; |S| = 13; min(x+y) = 26 ＞ 25

3STEP 3

상한: M 을 최댓값이라 하면 i + (M − i) = M 이므로 각 쌍 (i, M − i) 은 S 에 최대 하나만.

i + (M - i) = M ∈ S → 쌍에서 최대 하나만 S 에

4STEP 4

쌍의 수에 M 을 더하면 |S| 는 M 절반(올림) 이하; M ≤ 25 이므로 |S| ≤ 13.

|S| ≤ ⌈

\frac{M}{2}

⌉ ≤ ⌈

\frac{25}{2}

⌉ = 13

5STEP 5

2 단계가 13 달성, 4 단계가 13 상한 — 둘이 만나 최댓값은 정확히 13.

max |S| = 13

6STEP 6

13 을 선택지와 맞추면 (B).

13 → (B)

정답

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

💡핵심 정리

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

비슷한 유형 더 풀어보기