AMC 10 · 2002 · #9

학년 7 arithmetic

유형 Branching State Enumeration └ 세부 유형 Ordered Placement Count

permutations-basicfactorialsystematic-enumeration systematic-enumeration ↑ 선수 지식: permutations-basic

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

문제

글자 $A$ , $M$ , $O$ , $S$ , $U$ 를 각각 한 번씩 사용해 다섯 글자 "단어" 를 만든다. 이 "단어" 들을 사전(알파벳) 순서로 나열할 때, "단어" $USAMO$ 는 몇 번째 자리에 오는가?

답을 골라 클릭하세요.

(A)

112

(B)

113

(C)

114

(D)

115

(E)

116

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 다섯 글자 $A$, $M$, $O$, $S$, $U$를 각각 한 번씩 사용해 만들 수 있는 모든 다섯 글자 배열을 만든다. 이 배열들을 모두 사전(알파벳) 순서로 나열했을 때, 배열 $USAMO$가 몇 번째 자리에 오는지 구하여라.

주어진 것: 사용할 수 있는 글자는 $A$, $M$, $O$, $S$, $U$이며, 한 단어에 각 글자를 한 번씩 쓴다; 가능한 배열은 모두 $5!=120$가지이며 모두 유효한 "단어"이다; 단어들은 알파벳 순서로 정렬되어 있다; 선택지: (A) $112$, (B) $113$, (C) $114$, (D) $115$, (E) $116$

구하는 것: 정렬된 목록에서 단어 $USAMO$가 놓이는 자리 번호

이해

계획

주요 도구: #2 빠짐없이 나열하기

보조 도구: #16 관점 바꾸기, #7 작은 문제로 쪼개기

$120$개 단어를 전부 적어도 답은 나오지만 실수가 생기기 쉽다. 그래서 $USAMO$를 직접 찾는 대신(도구 #16, 관점 바꾸기) 그보다 앞에 오는 단어 수를 세고 $1$을 더한다. 도구 #2(빠짐없이 나열하기)는 앞에 오는 단어들을 깔끔한 알파벳 묶음으로 정리해 준다 — 먼저 첫 글자로, 다음에 둘째 글자로 나눈다. 도구 #7(작은 문제로 쪼개기)은 각 자리의 묶음 크기를 하나씩 처리한다. 글자를 하나 고정할 때마다 남은 글자들을 배열하는 경우의 수는 팩토리얼이고, 이 수들을 그냥 더하면 된다. 유의할 점은 마지막 $+1$이다. $USAMO$보다 앞에 오는 단어 수는 $114$인데, 이것이 함정 선택지 (C)이며 실제 자리는 그보다 하나 더 크다.

실행 — 정답: D

#2 빠짐없이 나열하기 7.SP.C.8 단계 1

U보다 앞선 첫 글자로 시작하는 단어 세기

글자를 크기순으로 놓으면 $A<M<O<S<U$이다.
첫 글자가 $A$, $M$, $O$, $S$인 단어는 $U$로 시작하는 어떤 단어보다도 앞에 오므로 모두 $USAMO$보다 앞에 있다.
이 $4$개의 첫 글자 각각에 대해 남은 $4$개 글자를 배열하는 방법은 $4! = 24$가지이다.
따라서 $U$ 묶음에 이르기도 전에 $4\times 24 = 96$개의 단어가 앞에 온다.

$$4\times 4! = 4\times 24 = 96$$

💡 첫 글자를 $U$보다 작은 글자로 고정하면 그 단어는 반드시 앞에 오고, 남은 글자들은 $4!$가지로 펼쳐진다.

#2 빠짐없이 나열하기 7.SP.C.8 단계 2

U 묶음 안에서 둘째 글자로 세기

이제 $U$로 시작하는 단어만 본다.
목표는 $U\,S\,A\,M\,O$이므로 둘째 글자는 $S$이다.
$U$ 다음에 남은 글자는 $\{A, M, O, S\}$이고, 알파벳 순서로 $A$, $M$, $O$는 모두 $S$보다 앞선다.
이 셋 중 하나를 둘째 글자로 고르면 앞 두 글자가 고정되고 남은 $3$개 글자를 $3! = 6$가지로 배열할 수 있다.
따라서 $3\times 6 = 18$개의 단어가 $USAMO$보다 더 앞에 온다.

$$3\times 3! = 3\times 6 = 18$$

💡 $U$ 묶음 안에서도 둘째 글자가 더 작으면 단어가 앞에 오므로, 그런 경우를 세고 남은 글자의 배열 수를 곱한다.

#7 작은 문제로 쪼개기 7.SP.C.8 단계 3

남은 글자들은 더 세지 않아도 됨을 확인

앞을 $U\,S$로 고정한다.
남은 글자는 $\{A, M, O\}$이고 목표는 $A$, 그다음 $M$, 그다음 $O$로 이어진다.
셋째 자리에서 $A$는 이미 남은 것 중 가장 작아 앞설 단어가 없고, 넷째 자리에서 $M$은 $\{M, O\}$ 중 더 작으며, 마지막 글자 $O$는 자동으로 정해진다.
따라서 이미 센 $18$개 외에 $USAMO$보다 앞에 오는 단어는 더 없다.

셋째·넷째·다섯째 글자가 모두 남은 것 중 최소 $\Rightarrow$ 추가 단어 $0$개

💡 고르는 남은 글자마다 항상 가장 작은 것이라면, 알파벳으로 더 앞선 단어는 없다.

#16 관점 바꾸기 4.OA.A.3 단계 4

개수를 더하고 하나 올리기

$USAMO$보다 앞에 오는 단어의 총 개수는 $96 + 18 = 114$이다.
$USAMO$ 자신의 자리는 앞에 있는 단어 수보다 하나 더 크므로 $114 + 1 = 115$번째이다.
이것이 선택지 (D)이다.
함정을 주의하자.
$114$는 앞에 오는 단어의 개수일 뿐 자리 번호가 아니며, 이를 그대로 답으로 고르면 함정 선택지 (C)에 걸린다.

$$96 + 18 = 114,\quad 114 + 1 = 115\;\Rightarrow\;\textbf{(D)}$$

💡 내 앞에 $114$명이 줄 서 있다면 나는 $115$번째 자리에 있는 것이다.

[1] #2 7.SP.C.8 글자를 크기순으로 놓으면 $A<M<O<S<U$이다. 첫 글자가 $A$, $M$, $O$, $S$인 단어는 $U$로 시작하는 어떤 단어보다도 앞에

[2] #2 7.SP.C.8 이제 $U$로 시작하는 단어만 본다. 목표는 $U\,S\,A\,M\,O$이므로 둘째 글자는 $S$이다. $U$ 다음에 남은 글자는 ${A, M

[3] #7 7.SP.C.8 앞을 $U\,S$로 고정한다. 남은 글자는 $\{A, M, O\}$이고 목표는 $A$, 그다음 $M$, 그다음 $O$로 이어진다. 셋째 자리에서

[4] #16 4.OA.A.3 $USAMO$보다 앞에 오는 단어의 총 개수는 $96 + 18 = 114$이다. $USAMO$ 자신의 자리는 앞에 있는 단어 수보다 하나 더 크

검토

합리성 확인: $USAMO$는 마지막 글자 $U$로 시작하므로 $120$개 목록에서 뒤쪽 깊숙이 있어야 하고, 실제로 $96$을 훨씬 지난 자리가 나와야 한다. 개수는 $96$($U$ 묶음 앞의 단어) $+ 18$($U$ 묶음 안에서 더 앞선 단어) $+ 1$($USAMO$ 자신) $= 115$로 나뉘며, 최대 자리 $120$보다 넉넉히 작다. 각 조각이 모두 자연수이고 합이 선택지 범위 $112$–$116$ 안에 정확히 들어오므로 $115$는 타당하다.

대안 접근: 끝에서부터 세어도 된다. 알파벳 순서로 가장 마지막 단어는 $U\,S\,O\,M\,A$로 $120$번째이다. $U\,S$로 시작하는 단어는 마지막 $3! = 6$자리, 즉 $115$–$120$번째를 차지한다. 이 여섯 개를 순서대로 적으면 $USAMO, USAOM, USMAO, USMOA, USOAM, USOMA$이고, $USAMO$가 그중 첫 번째이므로 $115$번째 자리이다. (D)가 확인된다.

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

7.SP.C.8 체계적인 목록·표·나뭇가지 그림으로 표본공간을 나타내고 경우의 수 세기 (글자를 하나씩 고정하고 남은 글자의 배열 수(팩토리얼)를 곱해 단어를 알파벳 묶음별로 세기($4\times 4!$, $3\times 3!$).)
4.OA.A.3 사칙연산을 이용해 여러 단계 문장제 해결하기 (묶음 개수 $96+18=114$를 더하고 하나를 올려 자리 $115$를 구하기.)

⭐ 정렬된 목록에서 한 단어의 자리를 찾으려면, 글자를 왼쪽부터 하나씩 고정해 앞에 오는 단어 수를 센 뒤 그 단어 자신을 위해 $1$을 더하면 된다.