도착지는 두 곳뿐, 같은 곳으로 온 길도 따로 세어야 해요

A에서 시작해 정확히 100번 화살표를 따라요. 도착할 수 있는 상태는 몇 개이며, 서로 다른 상태 순서의 경로는 몇 개일까요? B를 거친 길과 C를 거친 길은 서로 다른 경로로 세어요.

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

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

A→B 또는 C,B→D,C→D,D→AA\to B\text{ 또는 }C,\quad B\to D,\quad C\to D,\quad D\to A

A에서 시작해 정확히 100번 화살표를 따라요. 도착할 수 있는 상태는 몇 개이며, 서로 다른 상태 순서의 경로는 몇 개일까요? B를 거친 길과 C를 거친 길은 서로 다른 경로로 세어요.

도착 상태 {B,C}의 수=2,경로 수=234\text{도착 상태 }\{B,C\}\text{의 수}=2,\qquad\text{경로 수}=2^{34}

세 번 이동하면 A→B 또는 C→D→A라 항상 A로 돌아와요. 길이 세 묶음마다 두 선택지가 있고 서로 다른 선택은 서로 다른 경로예요. 100=3·33+1이므로 99번까지 33묶음에서 2³³개 경로를 만들고 마지막 한 번에 B 또는 C를 골라 전체 경로는 2³⁴개예요. 하지만 도착 상태는 B,C 두 개뿐이에요. 서로 다른 과거의 경로가 같은 D나 A로 합쳐져도 경로 기록이 같아지는 것은 아니에요. 큰 길이에 대한 계산은 전수 나열 대신 세 단계 복귀라는 주기를 사용해요. 도착 상태의 개수와 경로의 경우의 수를 서로 다른 대상으로 정의했어요.

99번과 101번에서는 도착 상태 수와 경로 수가 각각 어떻게 달라지는지 묶음의 나머지로 확인해 볼까요?

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

이 글 공유하기

개인정보 및 방문 통계 안내