AMC 10 · 2014 · #4

학년 2 logiccounting

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

permutations-basiclogical-deduction systematic-enumerationcasework ↑ 선수 지식: permutations-basic

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

문제

네 채의 집이 한 줄로 서 있고 각각 주황, 빨강, 파랑, 노랑이다. 주황 집은 빨강 집보다 앞에 오고, 파랑 집은 노랑 집보다 앞에 오며, 파랑 집과 노랑 집은 서로 바로 옆에 있지 않다. 세 규칙을 모두 만족하는 왼쪽에서 오른쪽 색 배열이 몇 개인지 세어라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 빠짐없이 나열하기

배열은 4!=24가지뿐인 작고 유한한 세계이므로, 도구 #2(빠짐없이 나열하기)로 빠뜨리거나 중복하지 않고 모두 훑을 수 있다. 규칙을 기계적으로 만들기 위해 도구 #4(변수 도입하기)로 네 자리를 1,2,3,4로 번호 매기면 "앞에"는 "자리 번호가 더 작다"가 되고 "서로 바로 옆이 아니다"는 "자리 번호 차이가 적어도 2"가 된다. 목록을 짧게 유지하는 요령은 파랑과 노랑을 먼저 놓는 것인데, 이 두 색이 세 규칙 중 둘을 지고 있기 때문이다. 그다음 도구 #3(가능성 지우기)이 붙어 있는 파랑-노랑 배치를 모두 버려서 마무리할 경우만 몇 개 남긴다.

1STEP 1

네 자리에 번호 매기기

왼쪽부터 자리를 1,2,3,4로 번호 매기면 "앞에"는 번호가 더 작다는 뜻, "바로 옆 아님"은 번호 차이 2 이상이다.

자리 1,2,3,4; O ＜ R, B ＜ Y, |B-Y| ≥ 2

2STEP 2

파랑과 노랑을 먼저 놓기

파랑·노랑이 규칙 둘을 지므로 먼저 놓으면, 여섯 자리 쌍 중 붙은 셋이 빠지고 세 가지가 남는다.

남김 (B,Y)∈{(1,3),(1,4),(2,4)}; 버림 (1,2),(2,3),(3,4)

3STEP 3

주황과 빨강 채우기

남은 두 자리는 주황·빨강 순이므로 (1,3)은 BOYR, (1,4)는 BORY, (2,4)는 OBRY.

(1,3)→ BOYR, (1,4)→ BORY, (2,4)→ OBRY

4STEP 4

완성된 배열 세기

합법 배치마다 마무리가 한 가지뿐이니 살아남는 배열은 3개, 답은 (B)이다.

3개의 올바른 배열 → (B)

정답

살아남은 세 배열을 손으로 확인하자: BOYR(파랑 자리 1, 노랑 자리 3, 차이 2), BORY(파랑 1, 노랑 4, 차이 3), OBRY(파랑 2, 노랑 4, 차이 2) — 모두 파랑이 노랑보다 앞이고 차이가 적어도 2이며, 각각 주황이 빨강보다 앞이다. 그래서 3은 실현 가능하니 (A) 2는 너무 작다. 또한 6만큼 클 수도 없다: 바로 옆 금지 규칙을 빼더라도 24개 배열 중 주황이 빨강보다 앞이면서 파랑이 노랑보다 앞인 것은 6개뿐이고, 여기서 옆 금지 규칙이 몇 개를 더 지우므로 (E) 6은 불가능하다.

💡핵심 정리

네 자리에 번호를 매기고 파랑과 노랑을 사이를 벌려 먼저 놓으면 "주황이 빨강보다 앞"이 나머지를 채워 주니, 살아남는 줄은 단 셋뿐이다.

네 자리에 번호 매기기
파랑과 노랑을 먼저 놓기
주황과 빨강 채우기
완성된 배열 세기

네 자리에 번호 매기기

파랑과 노랑을 먼저 놓기

주황과 빨강 채우기

완성된 배열 세기

비슷한 유형 더 풀어보기