AMC 10 · 2018 · #17

학년 4 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Answer-Choice Plug-In

multiplesdivisibility-rulesset-partitionfactors extremal-constructioncasework ↑ 선수 지식: multiplesdivisibility-rules

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

📘 쉬운 버전 보기 →

문제

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

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 극단의 원리

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

1STEP 1

아래에서부터 찾기

1은 모든 수를 나누므로 S에 못 들어간다. 따라서 가장 작은 원소는 적어도 2이고, 2, 3, 4를 차례로 시험해 처음 되는 값을 택한다.

모든 n에 대해 1 ∣ n이므로 1∈ S이면 배수 쌍이 생긴다 → 가장 작은 원소 ≥ 2

2STEP 2

가장 작은 값 =2 시험

2에서 시작하면 짝수가 모두 금지되고 홀수 3,5,7,9,11만 남는데, 3이 9를 나누어 많아야 5개가 들어가 여섯에 못 미친다.

2∈ S→ 허용 ={3,5,7,9,11}, 그러나 3 ∣ 9→ 많아야 4개; 1+4=5 ＜ 6

3STEP 3

가장 작은 값 =3 시험

3에서 시작해 6,9,12를 버리면 4,5,7,8,10,11이 남지만 4–8, 5–10 쌍에서 하나씩 잃어 많아야 5개뿐, 여전히 모자란다.

3∈ S→ 허용 ={4,5,7,8,10,11}, 그러나 4 ∣ 8, 5 ∣ 10→ 많아야 4개; 1+4=5 ＜ 6

4STEP 4

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

4에서 시작하면 집합 {4,5,6,7,9,11}이 배수 없는 여섯 원소를 이루고, 2와 3이 실패했으므로 가장 작은 원소는 4, 보기 (C).

S={4,5,6,7,9,11}; a ＜ b인 어떤 쌍에서도 a ∣ b 아님 → 가장 작은 원소 =4=(C)

정답

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

💡핵심 정리

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

아래에서부터 찾기
가장 작은 값 =2 시험
가장 작은 값 =3 시험
가장 작은 값 =4 시험하고 마무리

아래에서부터 찾기

가장 작은 값 =2 시험

가장 작은 값 =3 시험

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

비슷한 유형 더 풀어보기