AMC 10 · 2024 · #20

학년 6 countingnumber-theory

유형 Lattice / Grid Pattern from Small Cases └ 세부 유형 Periodic Placement Formula

pattern-recognitionsequences-arithmeticsystematic-enumerationparity easier-related-problempattern-recognitionoptimization-counting ↑ 선수 지식: sequences-arithmeticmultiplesparity

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

문제

{1, 2, 3, …, 2024} 에서 다음 두 조건을 만족하도록 가능한 많은 수를 골라 부분집합 S 를 만들 때, |S| 의 최댓값을 구하세요. (i) S 의 서로 다른 두 원소 x, y 는 |x - y| ＞ 2. (ii) S 의 서로 다른 두 홀수 x, y 는 |x - y| ＞ 6.

답을 골라 클릭하세요.

(A)

436

(B)

506

(C)

608

(D)

654

(E)

675

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

풀이 과정

전략 더 쉬운 문제로 줄이기

2024 는 정면돌파하기엔 너무 큽니다. 도구 #9(더 쉬운 문제로 줄이기)에 따라, 1 부터 시작해 "규칙을 어기지 않는 가장 작은 다음 정수" 를 골라 작은 구간에서 빽빽하게 쌓아봅니다. 1, 4, 8, 11, 14, 18, … 이 나오는 순간 도구 #5(패턴 찾기)가 이어받습니다 — 연속 간격이 +3, +4, +3, +3, +4, +3, … 으로 반복되고, 이는 "정수 10 개마다 3 개를 고른다" 와 같습니다. 한 번 이 길이-10 블록을 확인하고 나면 [1, 2024] 전체 개수는 세 등차수열의 짧은 셈 세 번으로 끝납니다. 그리디 구성 자체가 최적성의 증거가 되므로 더 무거운 대수는 필요 없습니다 (더 빽빽하게 만들려는 어떤 배치도 두 간격 규칙 중 하나를 깨게 됩니다).

1STEP 1

규칙 정리: 두 원소의 차 ≥ 3, 두 홀수의 차 ≥ 8 — 두 홀수의 차는 짝수라 6 초과는 ≥ 8.

|x - y| ≥ 3 (S 의 모든 두 원소); |x - y| ≥ 8 (S 의 두 홀수)

2STEP 2

1 부터 합법인 가장 작은 정수를 그리디로: 7 은 |7-1|=6 이라 홀수 규칙 위반 → 1, 4, 8, 11, 14, 18, 21, …

S ⊇ {1, 4, 8, 11, 14, 18, 21, 24, 28, 31, …}

3STEP 3

연속 차가 +3, +4, +3 (길이 10 블록)로 반복 → 정수 10 개마다 3 개, 즉 a_n+3 = a_n + 10.

(간격) = (+3, +4, +3)= 10, (+3, +4, +3)= 10, …

4STEP 4

시작 삼항 (1, 4, 8) 과 +10 이동으로 S 를 세 등차수열로: 1+10k, 4+10k, 8+10k (k≥0); 홀수는 1+10k 뿐.

S = {1 + 10k} ∪ {4 + 10k} ∪ {8 + 10k}, k = 0, 1, 2, …

5STEP 5

가족별로 A+10k ≤ 2024 를 풀면 개수는 203, 203, 202.

|I| = 203, |II| = 203, |III| = 202

6STEP 6

겹치지 않는 세 개수를 더함: 203 + 203 + 202 = 608 → (C). 그리디라 더 빽빽한 집합은 없음.

|S| = 203 + 203 + 202 = 608 → (C)

정답

608

밀도로 확인합시다. 정수 10 개마다 3 개를 뽑으니 |S| ≈

\frac{3}{10}

· 2024 = 607.2. 정확한 셈 608 이 바로 그 상한선에 붙어 있어 자연스럽습니다. 거친 비교도 됩니다: 홀수 규칙을 잊고 간격 ≥ 3 만 보면 약

\frac{2024}{3}

≈ 674 개까지 가능해서 선택지 A/D/E 가 그 구간에 있고, 홀수 규칙이 그 수를 줄여야 합니다. 그 줄임이 약 675 에서 608 까지 — 길이-10 블록마다 홀수 한 개씩 빠지는 셈으로 딱 맞아떨어집니다. 구성으로도, 선택지 (C) 와도 일치합니다.

💡핵심 정리

패킹 문제는 작은 구간에서 그리디로 만들어 보고 반복되는 간격 블록을 찾는 것이 첫 수입니다. 여기서는 "10 개마다 3 개" 블록이 보이고, 답은 본질적으로 2024 의 $\frac{3}{10}$ 을 가족별로 정확히 센 값입니다.

비슷한 유형 더 풀어보기