AMC 10 · 2018 · #17

쉬운 모드 학년 4

문제

$1$ 부터 $12$ 까지의 수 중에서 서로 다른 $6$ 개를 고르세요. 규칙은 하나입니다. 고른 수 중 어떤 수도 다른 고른 수의 배수가 되면 안 됩니다. (예를 들어 $6$ 은 $3$ 의 배수이므로, $3$ 과 $6$ 을 함께 고를 수 없습니다.)

이렇게 고르는 모든 방법 중에서, 가장 작은 수가 될 수 있는 가장 작은 값은 무엇일까요?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $\{1,2,\dots,12\}$에서 $6$개의 수로 이루어진 집합 $S$를 고르되, $S$의 어떤 원소도 $S$의 더 작은 원소의 배수가 되지 않도록 한다. 이런 집합들 가운데 가장 작은 원소는 얼마까지 작아질 수 있는가?

주어진 것: $S$는 $\{1,2,\dots,12\}$에서 고른 정확히 $6$개의 원소를 가진다; $a<b$가 모두 $S$에 있으면 $b$는 $a$의 배수가 아니다; 가장 작은 원소에 대한 보기: $2,\ 3,\ 4,\ 5,\ 7$

구하는 것: $S$의 가장 작은 원소가 가질 수 있는 최솟값

이해

계획

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

보조 도구: #6 추측하고 확인하기, #3 가능성 지우기, #2 빠짐없이 나열하기

문제는 가장 작은 원소가 가질 수 있는 최솟값을 묻는데, 이것은 경계를 최소화하는 질문이므로 Tool #14(극단의 원리)이다. 똑똑한 방법은 후보가 되는 가장 작은 값을 아래에서부터 ($2$, 그다음 $3$, 그다음 $4$) 시험해 보고, $6$개를 모두 채울 수 있는 첫 값에서 멈추는 것이다. Tool #6(추측하고 확인하기): 각 후보 최솟값마다 유효한 $6$개 집합을 만들어 본다. Tool #2(빠짐없이 나열하기): 가장 작은 원소를 정한 뒤, 아직 허용되는 더 큰 수들을 정확히 나열한다. Tool #3(가능성 지우기): 보기 덕분에 $2$와 $3$을 지울 수 있으므로, 살아남는 첫 보기가 답이다.

실행 — 정답: C

#14 극단의 원리 4.OA.B.4 단계 1

아래에서부터 찾기

가장 작은 원소를 최대한 작게 만들고 싶으므로, 후보 최솟값을 작은 것부터 시험해 처음으로 성공하는 값을 택한다.
$1$은 제외된다: $1$은 모든 수를 나누므로 $1\in S$이면 다른 어떤 원소도 $1$의 배수가 되어 규칙을 깬다.
따라서 가장 작은 원소는 적어도 $2$이고, $2$, $3$, $4$ 순서로 확인한다.

모든 $n$에 대해 $1\mid n$이므로 $1\in S$이면 배수 쌍이 생긴다 $\Rightarrow$ 가장 작은 원소 $\ge 2$

💡 가능한 가장 작은 시작점을 찾으려면 작은 값부터 시험해 처음 되는 곳에서 멈춘다.

#6 추측하고 확인하기 4.OA.B.4 단계 2

가장 작은 값 $=2$ 시험

$2$가 가장 작은 원소이면 모든 짝수 $4,6,8,10,12$는 $2$의 배수라 금지된다.
나머지 $5$자리를 채울 수 있는 것은 홀수 $3,5,7,9,11$뿐이다.
그런데 $9$는 $3$의 배수이므로 $3$과 $9$를 함께 넣을 수 없어, 이 $5$개 홀수 중 많아야 $4$개만 살아남는다.
그러면 원소가 많아야 $1+4=5$개로 $6$에 못 미친다.
따라서 $2$는 가장 작은 원소가 될 수 없다.

$2\in S\Rightarrow$ 허용 $=\{3,5,7,9,11\}$, 그러나 $3\mid 9\Rightarrow$ 많아야 $4$개; $1+4=5<6$

💡 $2$에서 시작하면 모든 짝수가 버려져 여섯을 채우기에 수가 너무 적다.

#6 추측하고 확인하기 4.OA.B.4 단계 3

가장 작은 값 $=3$ 시험

$3$이 가장 작은 원소이면 그 배수 $6,9,12$를 버린다.
$3$보다 큰 수 중 아직 허용되는 것은 $4,5,7,8,10,11$이다.
그런데 $8$은 $4$의 배수, $10$은 $5$의 배수이므로 각 쌍에서 하나만 남길 수 있다.
여섯 개 중 많아야 $4$개가 살아남아 다시 많아야 $1+4=5$개가 된다.
따라서 $3$도 가장 작은 원소가 될 수 없다.

$3\in S\Rightarrow$ 허용 $=\{4,5,7,8,10,11\}$, 그러나 $4\mid 8$, $5\mid 10\Rightarrow$ 많아야 $4$개; $1+4=5<6$

💡 나누는 쌍마다 하나씩 포기하게 되어 허용 목록이 계속 하나 모자란다.

#3 가능성 지우기 4.OA.B.4 단계 4

가장 작은 값 $=4$ 시험하고 마무리

$4$가 가장 작은 원소이면 그 배수 $8,12$를 버린다.
$4$보다 큰 수 중 아직 허용되는 것은 $5,6,7,9,10,11$이다.
여기서 나누는 쌍은 $5$와 $10$뿐이므로($10=2\cdot 5$) $10$을 버리고 $5,6,7,9,11$을 남기면, 어느 것도 다른 것의 배수가 아니다($9=3^2$이지만 $3\notin S$, $6$의 배수 $12$도 사라짐).
여기에 $4$를 더하면 $S=\{4,5,6,7,9,11\}$로, 여섯 원소 중 어느 것도 더 작은 원소의 배수가 아니다.
따라서 $4$는 성공한다.
$2$와 $3$이 모두 실패했으므로 $S$의 원소의 최솟값은 $4$, 보기 $\textbf{(C)}$이다.

$S=\{4,5,6,7,9,11\}$; $a<b$인 어떤 쌍에서도 $a\mid b$ 아님 $\Rightarrow$ 가장 작은 원소 $=4=\textbf{(C)}$

💡 $2$와 $3$이 지워지면, 여섯이 들어맞는 첫 값이 바로 답이다.

[1] #14 4.OA.B.4 가장 작은 원소를 최대한 작게 만들고 싶으므로, 후보 최솟값을 작은 것부터 시험해 처음으로 성공하는 값을 택한다. $1$은 제외된다: $1$은

[2] #6 4.OA.B.4 $2$가 가장 작은 원소이면 모든 짝수 $4,6,8,10,12$는 $2$의 배수라 금지된다. 나머지 $5$자리를 채울 수 있는 것은 홀수 $3,

[3] #6 4.OA.B.4 $3$이 가장 작은 원소이면 그 배수 $6,9,12$를 버린다. $3$보다 큰 수 중 아직 허용되는 것은 $4,5,7,8,10,11$이다. 그런

[4] #3 4.OA.B.4 $4$가 가장 작은 원소이면 그 배수 $8,12$를 버린다. $4$보다 큰 수 중 아직 허용되는 것은 $5,6,7,9,10,11$이다. 여기서

검토

합리성 확인: 집합 $\{4,5,6,7,9,11\}$은 모든 검사를 통과한다: 각 쌍을 훑어보면 더 큰 수가 더 작은 수의 배수인 경우가 없고, 가장 작은 원소가 $4$인 정확히 $6$개의 원소를 가진다. 더 작은 값은 실제로 막히는데, $2$와 $3$은 모두 $5$개에서 멈췄다. 따라서 $4$가 가능한 가장 작은 최솟값이며, 보기 $\textbf{(C)}$와 일치한다.

대안 접근: Tool #2(빠짐없이 나열하기): $\{1,\dots,12\}$을 약수 사슬 여섯 개로 나눈다, 예를 들어 $\{1,2,4,8\},\{3,6,12\},\{5,10\},\{7\},\{9\},\{11\}$. 유효한 $S$는 각 사슬에서 정확히 하나씩 고른다. 가장 작은 원소를 낮게 유지하려면 사슬의 맨 위 수를 피해야 하고, 사슬을 따져 보면 가장 작은 원소가 $4$까지 내려갈 수 있지만 그보다 더 작아질 수는 없어 다시 $\textbf{(C)}$가 나온다.

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

4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (각 후보 최솟값마다 어떤 큰 수가 그것의 배수인지(따라서 금지인지) 판정하고, $3\mid 9$, $4\mid 8$, $5\mid 10$ 같은 나누는 쌍을 찾아내며, $\{4,5,6,7,9,11\}$이 더 작은 원소의 배수인 원소를 갖지 않음을 확인하기.)

⭐ 가장 작은 시작점부터 시험하라: $2$와 $3$은 배수가 아닌 수가 너무 적어 여섯을 못 채우지만, $4$에서 시작하면 집합 $\{4,5,6,7,9,11\}$이 들어맞으므로 가장 작은 원소는 $4$, 보기 $\textbf{(C)}$이다.