길이 6의 0·1 문자열은 앞뒤를 거꾸로 읽어도 같아야 하고 이웃한 1,1이 없어야 한다. 맨 앞의 0도 허용한다. 가능한 문자열을 모두 쓰고 개수를 구하라. 앞 절반만 이웃 규칙에 맞으면 충분한지 확인한다.
앞뒤가 같으므로 문자열은 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. 위 문항의 조건·수치·풀이와 교사 질문은 새로 작성했다.