A로 돌아와야 한다면, C로 가는 선택은 처음부터 버려야 해요

글자 A로 시작하는 길이 101의 문자열을 만들어요. 이웃 글자는 표시한 화살표만 따를 수 있고 마지막 글자도 A여야 해요. 가능한 문자열 수를 구해 볼까요? 길이가 100이면 결과가 어떻게 바뀌나요?

여러 방향으로 갈라지고 이어지는 흰 배관

사진: KaiKemmann · CC BY-SA 4.0 · 원본 출처

A→B 또는 C,B→A,C→CA\to B\text{ 또는 }C,\qquad B\to A,\qquad C\to C

글자 A로 시작하는 길이 101의 문자열을 만들어요. 이웃 글자는 표시한 화살표만 따를 수 있고 마지막 글자도 A여야 해요. 가능한 문자열 수를 구해 볼까요? 길이가 100이면 결과가 어떻게 바뀌나요?

N101=1,N100=0,허용 문자열은 ABAB⋯AN_{101}=1,\qquad N_{100}=0,\qquad\text{허용 문자열은 }ABAB\cdots A

어느 단계에서 C를 고르면 그 뒤에는 C만 이어져 마지막 A 조건을 만족할 수 없어요. 따라서 마지막이 A인 문자열은 A 다음에 항상 B를 골라야 해요. B 다음은 A로 정해져 전체 문자열은 A,B를 번갈아 쓰는 한 형태뿐이에요. 홀수 번째 자리가 A이므로 길이 101에서는 한 개, 길이 100에서는 마지막이 B라 0개예요. 매번 A에서 두 선택지가 보인다고 2의 거듭제곱으로 세면 마지막 조건에 도달할 수 없는 가지까지 포함해요. 경로 수를 세기 전에 목적지로 돌아올 수 있는 상태를 남기는 판단이 도움이 돼요. 경우의 수를 구할 때 끝점 조건을 만족할 수 없는 가지를 먼저 제외했어요.

교사 질문: C에서 A로 돌아오는 화살표 하나를 추가하면 앞의 배제 논증 중 어느 문장이 성립하지 않는지 짚어 볼까요?

출처·착안: Senior Mathematical Challenge 2025 — Question 18. 위 문항의 조건·수치·풀이와 교사 질문은 새로 작성했다.

이 글 공유하기

개인정보 및 방문 통계 안내