AMC 10 · 2024 · #20
학년 6 countingnumber-theory문제
Let S be a subset of {1,2,3,…,2024} such that the following two conditions hold:
If x and y are distinct elements of S, then ∣x−y∣>2.
If x and y are distinct odd elements of S, then ∣x−y∣>6.
What is the maximum possible number of elements in S?
답을 골라 클릭하세요.
AMC 10 2024 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.
도구 + CCSS 풀이
이해
문제 재정리: $\{1, 2, 3, \dots, 2024\}$ 에서 다음 두 조건을 만족하도록 가능한 많은 수를 골라 부분집합 $S$ 를 만들 때, $|S|$ 의 최댓값을 구하세요. (i) $S$ 의 서로 다른 두 원소 $x, y$ 는 $|x - y| > 2$. (ii) $S$ 의 서로 다른 두 홀수 $x, y$ 는 $|x - y| > 6$.
주어진 것: $S \subseteq \{1, 2, 3, \dots, 2024\}$; $S$ 의 서로 다른 두 원소 $x, y$: $|x - y| > 2$, 즉 $|x - y| \ge 3$; $S$ 의 서로 다른 두 홀수 $x, y$: $|x - y| > 6$, 즉 $|x - y| \ge 8$ (두 홀수의 차는 항상 짝수); 선택지: (A) $436$, (B) $506$, (C) $608$, (D) $654$, (E) $675$
구하는 것: $|S|$ 의 최댓값
이해
문제 재정리: $\{1, 2, 3, \dots, 2024\}$ 에서 다음 두 조건을 만족하도록 가능한 많은 수를 골라 부분집합 $S$ 를 만들 때, $|S|$ 의 최댓값을 구하세요. (i) $S$ 의 서로 다른 두 원소 $x, y$ 는 $|x - y| > 2$. (ii) $S$ 의 서로 다른 두 홀수 $x, y$ 는 $|x - y| > 6$.
주어진 것: $S \subseteq \{1, 2, 3, \dots, 2024\}$; $S$ 의 서로 다른 두 원소 $x, y$: $|x - y| > 2$, 즉 $|x - y| \ge 3$; $S$ 의 서로 다른 두 홀수 $x, y$: $|x - y| > 6$, 즉 $|x - y| \ge 8$ (두 홀수의 차는 항상 짝수); 선택지: (A) $436$, (B) $506$, (C) $608$, (D) $654$, (E) $675$
계획
주요 도구: #9 더 쉬운 문제로 줄이기
보조 도구: #5 패턴 찾기
$2024$ 는 정면돌파하기엔 너무 큽니다. 도구 #9(더 쉬운 문제로 줄이기)에 따라, $1$ 부터 시작해 "규칙을 어기지 않는 가장 작은 다음 정수" 를 골라 작은 구간에서 빽빽하게 쌓아봅니다. $1, 4, 8, 11, 14, 18, \dots$ 이 나오는 순간 도구 #5(패턴 찾기)가 이어받습니다 — 연속 간격이 $+3, +4, +3, +3, +4, +3, \dots$ 으로 반복되고, 이는 "정수 $10$ 개마다 $3$ 개를 고른다" 와 같습니다. 한 번 이 길이-$10$ 블록을 확인하고 나면 $[1, 2024]$ 전체 개수는 세 등차수열의 짧은 셈 세 번으로 끝납니다. 그리디 구성 자체가 최적성의 증거가 되므로 더 무거운 대수는 필요 없습니다 (더 빽빽하게 만들려는 어떤 배치도 두 간격 규칙 중 하나를 깨게 됩니다).
실행 — 정답: C
6.EE.B.8 단계 1 - 두 간격 규칙을 쓰기 좋은 꼴로 다시 적습니다.
- 규칙 1은 "서로 다른 두 원소의 차는 적어도 $3$".
- 규칙 2는 "서로 다른 두 홀수의 차는 적어도 $8$" — 두 홀수의 차는 항상 짝수이므로 "$6$ 초과" 는 "$\ge 8$" 과 같습니다.
- 두 부등식이 그리디 구성을 이끕니다.
💡 "$|x-y| > 2$" 를 "$|x-y| \ge 3$" 으로 옮기는 것은 정수 위에서 강한 부등식을 다음 정수로 끌어올리는 6학년 부등식 읽기입니다.
5.OA.B.3 단계 2 - $1$ 부터 시작해 그리디로 가장 빽빽한 합법 집합을 만듭니다.
- 매 단계마다 두 규칙을 모두 만족하는 가장 작은 다음 정수를 고릅니다.
- 처음 몇 항: $1$ (홀수).
- 다음은 $\ge 4$ 이므로 $4$.
- 다음은 $4$-규칙에서 $\ge 7$; $7$ 은 홀수이고 $|7 - 1| = 6$ 이라 홀수 규칙을 깨므로 건너뛰고 $8$.
- 다음은 $\ge 11$; $11$ 은 홀수, $|11 - 1| = 10 \ge 8$ 이므로 $11$.
- 이어서 $14, 18, 21, 24, 28, 31, \dots$.
💡 작은 구간에서 그리디로 만들어 보는 것은 5학년의 "규칙으로 다음 항 만들기" — "합법인 가장 작은 다음 수" 가 곧 가장 빽빽한 배치입니다.
5.OA.B.3 단계 3 - 간격 수열에서 규칙을 읽습니다.
- 연속 차는 $3, 4, 3, 3, 4, 3, 3, 4, 3, \dots$ 로, $(+3, +4, +3)$ 인 길이 $3 + 4 + 3 = 10$ 의 블록이 반복됩니다.
- 즉 연속한 정수 $10$ 개마다 $3$ 개를 고르고, 한 블록이 지나면 패턴은 $10$ 만큼 평행이동: $a_{n+3} = a_n + 10$.
💡 반복되는 간격 블록은 공차 $10$ 의 등차수열 세 개가 엇갈려 있다는 뜻 — 5학년의 "규칙을 파악해 $k$ 번째 항으로 점프" 그대로입니다.
6.EE.A.2 단계 4 - $S$ 를 세 등차수열로 나눕니다.
- 시작 삼항 $(1, 4, 8)$ 과 $a_{n+3} = a_n + 10$ 으로부터 $\{1, \dots, 2024\}$ 안에는 세 가족이 들어 있습니다.
- 가족 I (유일한 홀수 가족): $1 + 10k$.
- 가족 II: $4 + 10k$.
- 가족 III: $8 + 10k$, 모두 $k \ge 0$.
💡 세 가족을 같은 지표 $k$ 로 묶어 부르는 것은 6학년의 "변수가 들어간 식 쓰기" — 세는 문제를 부등식 푸는 문제로 바꿔줍니다.
6.EE.B.8 단계 5 - 각 가족에서 합법인 $k$ 개수를 부등식으로 셉니다.
- 가족 I: $1 + 10k \le 2024$ 에서 $k \le 202.3$, 따라서 $k \in \{0, \dots, 202\}$ — $203$ 개.
- 가족 II: $4 + 10k \le 2024$ 에서 $k \le 202$, 또한 $203$ 개.
- 가족 III: $8 + 10k \le 2024$ 에서 $k \le 201.6$, 따라서 $k \in \{0, \dots, 201\}$ — $202$ 개.
💡 가족별 개수는 같은 6학년 부등식 셈입니다: $A + 10k \le 2024$ 를 만족하는 음 아닌 정수 $k$ 가 몇 개인가?
5.OA.B.3 단계 6 - 세 개수를 더합니다.
- 세 가족은 $\pmod{10}$ 잔여가 $1, 4, 8$ 로 서로 달라서 자동으로 겹치지 않으므로 합 $= 203 + 203 + 202$.
- 마지막으로 규칙을 확인: 가족 I 두 원소의 차는 $10$ 의 양의 배수이므로 $\ge 8$ (홀수 규칙 OK); 가족 II·III 는 모두 짝수라 홀수 규칙은 적용 대상이 없고; $S$ 전체의 최소 간격은 $\min(3, 4, 3) = 3$ (일반 규칙 OK).
- 구성은 합법이고, 매 단계 "합법인 가장 작은 다음 정수" 를 골랐으므로 더 빽빽한 합법 집합은 존재하지 않습니다.
💡 서로 겹치지 않는 가족들의 개수는 그대로 더하면 끝 — 5학년의 "묶음별로 세고 합치기" 구조.
6.EE.B.8 두 간격 규칙을 쓰기 좋은 꼴로 다시 적습니다. 규칙 1은 "서로 다른 두 원소의 차는 적어도 $3$". 규칙 2는 "서로 다른 두 홀수의 차는 5.OA.B.3 $1$ 부터 시작해 그리디로 가장 빽빽한 합법 집합을 만듭니다. 매 단계마다 두 규칙을 모두 만족하는 가장 작은 다음 정수를 고릅니다. 처음 몇 5.OA.B.3 간격 수열에서 규칙을 읽습니다. 연속 차는 $3, 4, 3, 3, 4, 3, 3, 4, 3, \dots$ 로, $(+3, +4, +3)$ 인 길 6.EE.A.2 $S$ 를 세 등차수열로 나눕니다. 시작 삼항 $(1, 4, 8)$ 과 $a_{n+3} = a_n + 10$ 으로부터 ${1, \dots, 2 6.EE.B.8 각 가족에서 합법인 $k$ 개수를 부등식으로 셉니다. 가족 I: $1 + 10k \le 2024$ 에서 $k \le 202.3$, 따라서 $k 5.OA.B.3 세 개수를 더합니다. 세 가족은 $\pmod{10}$ 잔여가 $1, 4, 8$ 로 서로 달라서 자동으로 겹치지 않으므로 합 $= 203 + 20 검토
합리성 확인: 밀도로 확인합시다. 정수 $10$ 개마다 $3$ 개를 뽑으니 $|S| \approx \tfrac{3}{10} \cdot 2024 = 607.2$. 정확한 셈 $608$ 이 바로 그 상한선에 붙어 있어 자연스럽습니다. 거친 비교도 됩니다: 홀수 규칙을 잊고 간격 $\ge 3$ 만 보면 약 $2024/3 \approx 674$ 개까지 가능해서 선택지 A/D/E 가 그 구간에 있고, 홀수 규칙이 그 수를 줄여야 합니다. 그 줄임이 약 $675$ 에서 $608$ 까지 — 길이-$10$ 블록마다 홀수 한 개씩 빠지는 셈으로 딱 맞아떨어집니다. 구성으로도, 선택지 (C) 와도 일치합니다.
대안 접근: 도구 #3(가능성 좁히기)을 선택지에 직접 적용합니다. 상한 $|S| \le \lfloor 2024/3 \rfloor + 1 = 675$ 만으로는 새로 지워지는 답이 없지만, 홀수 규칙으로 얻는 "연속 정수 $8$ 개마다 홀수는 최대 한 개" 부터 시작해 짝수가 그 주위에서 간격 $\ge 3$ 을 지키며 채워지는 방식 — 결국 길이-$10$ 창마다 $3$ 개꼴 — 을 따라가면 답은 $600$ 대로 빠르게 좁혀집니다. 선택지 중 $\tfrac{3}{10}$ 밀도와 일치하는 것은 (C) $608$ 뿐입니다.
사용된 CCSS 표준 (최저 학년 6)
6.EE.B.8$x > c$ 또는 $x < c$ 꼴 부등식으로 제약을 표현하고 해집합 파악하기 (두 강한 간격 규칙을 작업하기 좋은 $|x - y| \ge 3$ 과 (홀수에 대해) $|x - y| \ge 8$ 로 옮기고, 세 가족 각각에서 $A + 10k \le 2024$ 를 만족하는 음 아닌 정수 $k$ 개수를 세는 데 사용.)5.OA.B.3두 규칙으로 수 패턴을 만들고, 순서쌍을 만들어 관계 파악하기 (그리디 집합 $1, 4, 8, 11, 14, 18, \dots$ 을 항 단위로 만들고, 총 길이 $10$ 의 간격 블록 $(+3, +4, +3)$ 이 반복됨을 읽어내는 데 사용.)6.EE.A.2문자가 수를 대신하는 식을 쓰고, 읽고, 계산하기 ($S$ 안의 세 등차수열을 같은 지표 $k$ 로 $1 + 10k$, $4 + 10k$, $8 + 10k$ 라 부르는 데 사용 — 세는 문제를 세 개의 일차 부등식 풀이로 바꿔줍니다.)
⭐ 패킹 문제는 작은 구간에서 그리디로 만들어 보고 반복되는 간격 블록을 찾는 것이 첫 수입니다. 여기서는 "$10$ 개마다 $3$ 개" 블록이 보이고, 답은 본질적으로 $2024$ 의 $\tfrac{3}{10}$ 을 가족별로 정확히 센 값입니다.
⭐ 패킹 문제는 작은 구간에서 그리디로 만들어 보고 반복되는 간격 블록을 찾는 것이 첫 수입니다. 여기서는 "$10$ 개마다 $3$ 개" 블록이 보이고, 답은 본질적으로 $2024$ 의 $\tfrac{3}{10}$ 을 가족별로 정확히 센 값입니다.
비슷한 유형 더 풀어보기
같은 archetype · 비슷한 학년부터.
