AMC 10 · 2005 · #25

학년 5 arithmetic

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

set-partitionpair-counting extremal-constructioncomplementary-counting ↑ 선수 지식: set-partition

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

📘 쉬운 버전 보기 →

문제

$1$ 부터 $100$ 까지의 정수의 집합의 부분집합 $B$ 가, 어떤 두 원소의 합도 $125$ 가 되지 않는 성질을 가집니다. $B$ 의 원소의 최대 개수는 얼마입니까?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $1$ 부터 $100$ 까지의 정수 중에서, 선택한 두 수의 합이 $125$ 가 되지 않도록 가능한 한 큰 모임 $B$ 를 고릅니다. $B$ 가 가질 수 있는 원소의 최대 개수를 구하세요.

주어진 것: 수의 범위는 $1$ 부터 $100$ 까지의 모든 정수입니다; $B$ 는 그 범위에서 고른 부분집합입니다; 금지 조건: $B$ 의 두 원소의 합이 $125$ 가 되어서는 안 됩니다; 선택지: (A) $50$, (B) $51$, (C) $62$, (D) $65$, (E) $68$

구하는 것: $B$ 의 원소가 될 수 있는 최대 개수

이해

계획

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

보조 도구: #4 변수 도입하기, #7 작은 문제로 쪼개기, #2 빠짐없이 나열하기

문제가 가장 큰 집합을 물으므로, 도구 #14(극단의 원리)가 전체 전략을 잡아 줍니다: 어떤 집합도 넘을 수 없는 확고한 상한을 찾은 뒤, 그 상한에 실제로 도달하는 집합을 하나 만듭니다. 도구 #4(변수 도입하기)로 일반적인 수 $x$ 에 이름을 붙이면, 금지된 짝 $125-x$ 를 적어 두고 경계 $x\ge 25$ 를 한 번에 풀 수 있습니다. 금지 조건은 수들을 짝 $(x,\,125-x)$ 으로 묶으므로, 도구 #7(작은 문제로 쪼개기)로 범위를 두 무리로 나눕니다 — 금지된 짝이 범위 밖이라 항상 안전한 수들, 그리고 금지된 짝을 이루는 수들. 도구 #2(빠짐없이 나열하기)로 그 짝들을 적어 정확히 세는데, 각 짝에서 최대 한 수만 남길 수 있기 때문입니다.

실행 — 정답: C

#4 변수 도입하기 3.NBT.A.2 단계 1

각 수의 금지된 짝 찾기

두 원소는 합이 $125$ 일 때만 충돌합니다.
그래서 어떤 수 $x$ 든 함께 있을 수 없는 유일한 수는 $125-x$ 입니다.
한 수가 위험한 것은 그 짝 $125-x$ 가 범위 $1$ 부터 $100$ 안에 있을 때뿐입니다.
$125-x\le 100$ 을 풀면 $x\ge 25$ 가 됩니다.
즉 한 수가 범위 안에 짝을 갖는 것은 정확히 그 수가 $25$ 이상일 때입니다.

$$x+\,(125-x)=125;\quad 125-x\le 100 \iff x\ge 25$$

💡 한 수는 합 $125$ 를 완성할 바로 그 수가 범위 안에 실제로 존재할 때만 위험합니다.

#7 작은 문제로 쪼개기 4.OA.A.3 단계 2

범위를 안전한 수와 짝지어진 수로 나누기

$1$ 부터 $24$ 까지의 수는 완전히 안전합니다: 각각의 짝 $125-x$ 는 $101$ 이상이라 범위 밖이므로, 이 수들은 결코 합 $125$ 를 만드는 데 쓰일 수 없습니다.
이 $24$ 개는 모두 위험 없이 남길 수 있습니다.
그러면 금지된 짝을 이루는 $76$ 개의 수인 $25$ 부터 $100$ 까지만이 선택을 해야 하는 유일한 영역으로 남습니다.

$$\text{안전: }1..24\;(24\text{개});\quad \text{짝지어짐: }25..100\;(76\text{개})$$

💡 위험 없는 수들을 먼저 처리해 두면 까다로운 수들만 남겨 두고 따질 수 있습니다.

#2 빠짐없이 나열하기 5.OA.B.3 단계 3

금지된 짝을 나열하고 세기

$25$ 부터 $100$ 까지의 각 수를 합이 $125$ 가 되는 짝과 묶습니다: $(25,100),\,(26,99),\,(27,98),\,\ldots,\,(62,63)$.
$76$ 개의 수는 모두 정확히 하나의 짝에 속합니다.
더 작은 쪽 원소들은 $25,26,\ldots,62$ 로 이어지므로 짝의 개수는 $62-25+1=38$ 입니다.

$$(25,100),(26,99),\ldots,(62,63):\quad 62-25+1=38\text{개의 짝}$$

💡 위험한 수마다 오직 하나의 짝에 속하므로, 줄 세워 보면 금지 조건이 짝의 개수 세기로 단순해집니다.

#14 극단의 원리 4.OA.A.3 단계 4

상한 적용: 짝마다 최대 한 개

금지된 각 짝에서 두 수를 모두 남기면 합이 $125$ 가 되므로, 각 짝에서 $B$ 에 들어갈 수 있는 것은 최대 한 수입니다.
이것이 짝지어진 영역을 $38$ 개로 제한합니다.
안전한 $24$ 개를 더하면 어떤 집합도 $24+38=62$ 를 넘을 수 없습니다.
이것은 확고한 상한입니다: $24$ 개의 홑수와 $38$ 개의 짝으로 이루어진 전체에서 $63$ 개를 고르면 어떤 짝에서 두 개를 골라야 하므로 규칙이 깨집니다.

$$\underbrace{24}_{\text{안전}}+\underbrace{38}_{\text{짝마다 하나}}=62\;\text{(상한)}$$

💡 두 수가 한 짝을 이룰 수는 있어도 $B$ 안의 자리는 하나뿐이므로, 짝이 확고한 상한을 정합니다.

#14 극단의 원리 3.NBT.A.2 단계 5

62 에 도달하는 집합 만들기

$B=\{1,2,3,\ldots,62\}$ 를 잡습니다.
가장 큰 두 원소는 $61$ 과 $62$ 이고 그 합은 $61+62=123$ 으로 $125$ 보다 작으므로, 이 집합의 어떤 두 원소도 $125$ 에 이르지 못합니다.
이 집합은 정확히 $62$ 개의 원소를 가지며 규칙을 어기지 않으므로, 상한 $62$ 는 실제로 도달됩니다.
따라서 원소의 최대 개수는 $62$, 선택지 (C)입니다.

$$B=\{1,\ldots,62\}:\;\max\text{ 합}=61+62=123<125,\;|B|=62\Rightarrow\textbf{(C)}$$

💡 $62$ 개의 가장 작은 수들은 너무 작아 위쪽 두 개조차 $125$ 에 못 미치므로, 전부 한꺼번에 들어갈 수 있습니다.

[1] #4 3.NBT.A.2 두 원소는 합이 $125$ 일 때만 충돌합니다. 그래서 어떤 수 $x$ 든 함께 있을 수 없는 유일한 수는 $125-x$ 입니다. 한 수가 위험

[2] #7 4.OA.A.3 $1$ 부터 $24$ 까지의 수는 완전히 안전합니다: 각각의 짝 $125-x$ 는 $101$ 이상이라 범위 밖이므로, 이 수들은 결코 합 $12

[3] #2 5.OA.B.3 $25$ 부터 $100$ 까지의 각 수를 합이 $125$ 가 되는 짝과 묶습니다: $(25,100),\,(26,99),\,(27,98),\,\l

[4] #14 4.OA.A.3 금지된 각 짝에서 두 수를 모두 남기면 합이 $125$ 가 되므로, 각 짝에서 $B$ 에 들어갈 수 있는 것은 최대 한 수입니다. 이것이 짝지어

[5] #14 3.NBT.A.2 $B=\{1,2,3,\ldots,62\}$ 를 잡습니다. 가장 큰 두 원소는 $61$ 과 $62$ 이고 그 합은 $61+62=123$ 으로 $1

검토

합리성 확인: 두 관점이 일치합니다: 짝 논증은 어떤 집합도 $62$ 를 넘을 수 없다고 하고, 구체적 집합 $\{1,\ldots,62\}$ 는 $62$ 에 도달하므로, $62$ 는 상한이면서 동시에 도달 가능합니다. 경계 짝 $(62,63)$ 을 빠르게 확인하면 뒷받침됩니다: $62+63=125$ 이므로 $62$ 와 $63$ 은 함께 있을 수 없고, $62$ 를 남기고 $63$ 을 버리는 것이 바로 $\{1,\ldots,62\}$ 가 하는 일입니다. 함정 선택지 (A) $50$ 은 홀수/짝수로만 나누거나 $100$ 의 절반에서 멈출 때 나옵니다; 작은 안전한 수 $24$ 개에 각 짝에서 하나씩을 더하면 어떤 반반 분할보다 크므로 이는 과소 계산입니다. 선택지 (D) $65$ 와 (E) $68$ 은 상한 $62$ 를 넘어 금지된 쌍을 강제하므로 불가능합니다.

대안 접근: 자리를 아래에서부터 욕심껏 채운다고 생각합니다. $1,2,3,\ldots$ 을 차례로 넣는데, 새 수 $n$ 은 그 짝 $125-n$ 이 아직 뽑히지 않은 한 안전합니다. 짝이 범위 안에 들어오기 시작하는 것은 $n$ 이 $63$ 에 이를 때부터입니다($63$ 의 짝 $62$ 는 이미 들어 있음). 그래서 $1$ 부터 $62$ 까지는 모두 자유롭게 들어가고 $63$ 이 처음으로 거절해야 하는 수입니다. 이렇게 하면 짝을 전부 나열하지 않고도 다시 $62$ 개가 나옵니다.

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

3.NBT.A.2 $1000$ 이내에서 능숙하게 덧셈과 뺄셈을 한다 (각 수의 금지된 짝 $125-x$ 를 찾고, $61+62=123$, $62+63=125$ 같은 합을 확인해 어떤 수들이 함께 있을 수 있는지 판정하는 데 사용.)
5.OA.B.3 두 규칙으로 두 수열을 만들고 그 관계를 파악한다 (합이 각각 $125$ 가 되는 두 수열로서 짝 $(25,100),(26,99),\ldots,(62,63)$ 을 만들고, 그것이 $38$ 개임을 세는 데 사용.)
4.OA.A.3 네 가지 연산을 사용해 여러 단계의 문장제를 해결한다 (범위를 안전한 $24$ 개와 짝 $38$ 개로 나누고, 짝마다 하나씩으로 제한한 뒤 $24+38=62$ 로 결합해 최댓값을 구하는 데 사용.)

⭐ 규칙을 깨뜨릴 수들을 서로 짝지어 각 짝에서 하나씩만 남기고, 짝지을 수조차 없는 작은 수들은 모두 넣으면, 가장 작은 $62$ 개의 수가 곧 조건에 맞는 집합이 됩니다.