글자 A로 시작하는 길이 101의 문자열을 만든다. 이웃 글자는 표시한 화살표만 따를 수 있고 마지막 글자도 A여야 한다. 가능한 문자열 수를 구하라. 길이가 100이면 결과가 어떻게 바뀌는가?
어느 단계에서 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. 위 문항의 조건·수치·풀이와 교사 질문은 새로 작성했다.