연속한 세 글자가 모두 다르면, A·B·C는 결국 반복될까요?

A·B·C만 쓴 무한 문자열에서 연속한 세 글자는 늘 서로 달라야 해요. 겹치는 두 구간을 비교해 다음 글자가 정해지는 이유를 살펴보고, 가능한 문자열과 가장 짧은 반복 주기를 찾아요.

여러 색의 글자가 적힌 나무 블록 기둥

사진: Bobjgalindo · CC BY 4.0 · 원본 출처

A,B,C만 사용하여 한쪽으로 무한히 이어지는 문자열을 만들어요. 연속한 세 글자는 언제나 서로 달라야 해요. 이 조건을 만족하면서 주기가 없는 문자열도 만들 수 있을까요?

sn,sn+1,sn+2 는 서로 다르다(n≥1).s_n,s_{n+1},s_{n+2}\ \text{는 서로 다르다}\quad(n\ge1).

처음 세 칸에는 A,B,C가 한 번씩 들어가요. 둘째·셋째·넷째 칸도 서로 달라야 하므로 넷째 칸에는 둘째와 셋째에 없는 문자가 들어가요. 세 문자 중 남은 것은 첫째 문자 하나뿐이에요.

같은 비교를 어느 위치에서나 반복하면 다음 관계가 돼요.

sn+3=sn,N=3!=6.s_{n+3}=s_n,\qquad N=3!=6.

따라서 ABCABC…, ACBACB…처럼 처음 세 글자를 되풀이하는 여섯 문자열이 전부예요. 세 글자가 서로 다르므로 주기 1은 안 되고, 주기 2라면 첫째와 셋째가 같아져 역시 안 돼요. 최소 주기는 3이에요.

한 위치의 예만 반복해 보인 것이 아니라 겹치는 두 개의 길이 3 창을 비교해 다음 글자가 유일하다는 것을 보였어요. 문자 종류를 네 개로 늘렸을 때 이 유일성 증명 어느 줄이 깨지는지도 확인해 볼 수 있어요. 모든 비주기 문자열이 불가능하다는 현재 결론을 그 새 규칙에 옮기지는 않아요.

착안 원문: NZMO 2025 Round 1, Problem 4. 위 조건·문항과 해설은 새로 구성했어요. 원문의 문항이나 그림을 번역·재사용한 것이 아니에요.

이 글 공유하기

개인정보 및 방문 통계 안내