앞 절반에는 11이 없는데, 거꾸로 붙이니 가운데에 11이 생겼어요

길이 6의 0·1 문자열은 앞뒤를 거꾸로 읽어도 같아야 하고 이웃한 1,1이 없어야 해요. 맨 앞의 0도 허용해요. 가능한 문자열을 모두 쓰고 개수를 구해 볼까요? 앞 절반만 이웃 규칙에 맞으면 충분한지 확인해요.

회색 무늬 천과 노란 격자 무늬 천의 겹친 부분

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

b1b2b3b4b5b6=b6b5b4b3b2b1,bi∈{0,1},11은 금지b_1b_2b_3b_4b_5b_6=b_6b_5b_4b_3b_2b_1,\quad b_i\in\{0,1\},\quad11\text{은 금지}

길이 6의 0·1 문자열은 앞뒤를 거꾸로 읽어도 같아야 하고 이웃한 1,1이 없어야 해요. 맨 앞의 0도 허용해요. 가능한 문자열을 모두 쓰고 개수를 구해 볼까요? 앞 절반만 이웃 규칙에 맞으면 충분한지 확인해요.

000000,010010,100001,N=3000000,\quad010010,\quad100001,\qquad N=3

앞뒤가 같으므로 문자열은 a,b,c,c,b,a 꼴이에요. 가운데 두 글자가 c,c로 같아서 11을 금지하려면 c=0이어야 해요. a,b에는 11이 올 수 없고 가능한 두 글자는 00,01,10입니다. c=0을 붙이고 거꾸로 이어 쓰면 표시한 세 문자열을 얻어요. 각 문자열의 모든 이웃을 직접 보면 11이 없어요. 앞 절반 001은 자체로 금지 규칙에 맞지만 전체 001100으로 만들면 가운데 11이 생겨 제외돼요. 부분 문자열의 조건과 두 부분을 이어 붙인 경계의 조건을 모두 점검해야 해요. 역순 대칭을 먼저 적용한 뒤 접합부 조건까지 점검해야 경우의 수를 빠짐없이 셀 수 있어요.

교사 질문: 길이 5에서는 가운데 글자가 두 번 이어지지 않으므로 같은 c=0 결론이 필요한지 비교해 봐요.

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

이 글 공유하기

개인정보 및 방문 통계 안내