AMC 10 · 2015 · #10

학년 2 arithmetic
유형 Branching State Enumeration └ 세부 유형 Constrained Sequence or Path Count
systematic-enumerationpermutations-basic casework ↑ 선수 지식: permutations-basic
📏 중간 풀이 💡 2 개 인사이트
📘 쉬운 버전 보기 →
문제
네 글자 a, b, c, d를 한 줄로 늘어놓을 때, 서로 붙어 있는 두 글자가 알파벳에서도 이웃인 경우가 하나도 없는 배열이 몇 개인지 세어라 (즉 ab, ba, bc, cb, cd, dc 같은 이웃 쌍은 금지된다).

답을 골라 클릭하세요.

(A)
0
(B)
1
(C)
2
(D)
3
(E)
4

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

풀이 과정
전략 빠짐없이 나열하기

배열은 4!=24가지뿐인 작고 유한한 세계이므로, 첫 글자를 기준으로 정리하는 도구 #2(빠짐없이 나열하기)를 쓰면 빠뜨리거나 중복하지 않고 모두 셀 수 있다. 알파벳 이웃 검사를 기계적으로 만들기 위해 도구 #4(변수 도입하기)로 a,b,c,d를 위치 번호 1,2,3,4로 바꾸면 "알파벳 이웃"이 "차이가 정확히 1"이라는 깔끔한 수 검사가 된다. 그다음 도구 #3(가능성 지우기)이 금지된 쌍이 강제되는 순간 가지 전체를 쳐내므로, 24가지 중 대부분이 일일이 적기도 전에 사라진다.

1STEP 1

글자를 숫자로 바꾸기

글자를 a=1,b=2,c=3,d=4로 바꾸면, 알파벳 이웃은 숫자 차이가 1인 것과 같습니다.

a=1, b=2, c=3, d=4; 금지된 이웃 ⇔ |차이|=1
2STEP 2

첫 글자로 나누어 정리하기

각 첫 글자를 시도하며 금지 규칙이 나머지를 어떻게 강제하는지 봅니다.

첫 글자 ∈ {a,b,c,d}, 이후 "차이 1 금지" 아래에서 나머지를 채움
3STEP 3

A나 D로 시작하면 둘 다 무너짐

a나 d로 시작하면 항상 막다른 길입니다: 모든 가지가 금지된 이웃 쌍으로 강제됩니다.

a c ?→{b,d} 둘 다 c에 닿음; a d b c는 bc로 끝남 — 모두 실패
4STEP 4

B나 C로 시작하면 각각 딱 하나

b나 c로 시작하면 각각 bdac, cadb 하나씩만 성립해 총 2개 — 선택지 (C).

b d a c와 c a d b가 성립 → 총 =2 → (C)
정답
2
살아남은 두 배열 bdac와 cadb는 서로 뒤집은 것으로, 이는 문제의 대칭성과 맞아떨어진다: 올바른 줄을 좌우로 뒤집어도 모든 이웃 쌍은 그대로이므로 올바른 배열은 거울 쌍으로 나온다. 그래서 개수가 짝수일 것이 예상되고, 2는 가장 작은 0이 아닌 짝수다 — 홀수인 (B) 1과 (D) 3이 배제된다. bdac의 이웃 간격은 2,3,2, cadb도 2,3,2로 모두 깨끗하고, a나 d로 시작하는 경우는 모두 ab/bc/cd 쌍에 강제로 빠졌다. 따라서 (A) 0은 너무 적고 (E) 4는 너무 많다.
💡핵심 정리

글자를 1-2-3-4 숫자로 바꾼 뒤 이웃끼리 차이가 1이 되지 않게 늘어놓으면, 살아남는 줄은 단 두 개다.

  • 글자를 숫자로 바꾸기
  • 첫 글자로 나누어 정리하기
  • A나 D로 시작하면 둘 다 무너짐
  • B나 C로 시작하면 각각 딱 하나

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.