세 자리 0·1의 모양은 000,001,010,011,100,101,110,111의 8개예요. 자체 문항으로 모든 모양을 적어도 한 번씩 읽을 수 있는 짧은 기록을 설계하자. 각 시작 칸에서 같은 방향으로 연속 3칸을 읽고, 모양끼리 칸을 겹쳐 써도 돼요.
먼저 끝을 처음에 잇는 원형 기록이에요. m칸이면 시작 위치도 m개이며 한 시작에서 한 모양만 읽힌다. 따라서 8모양을 담으려면 m≥8입니다. 다음 8칸 기록으로 그 하한을 달성해요.
순서대로 각 칸에서 읽으면 000,001,011,111,110,101,010,100입니다. 마지막 두 시작은 끝을 넘어 처음의 칸을 사용해요. 8개가 모두 다르므로 모든 모양을 정확히 한 번씩 읽어요. 최소 길이는 8입니다.
이제 직선 기록으로 바꾸고 끝을 처음에 잇지 말아요. m칸에서 완전한 3칸을 읽을 수 있는 시작은 m−2개뿐이에요. 8개 모양을 읽으려면 m≥10이어야 해요. 원형 예의 앞 두 칸 00을 맨 뒤에 붙이면 다음 기록을 얻어요.
이 10칸 기록의 8개 시작에서 위와 같은 모양을 읽어요. 직선의 최소 길이는 10입니다. 8개 모양을 각각 따로 적어 24칸을 쓰는 설계와 비교하면, 칸을 겹쳐 읽는 조건이 필요한 길이를 줄였음을 확인할 수 있어요.
De Bruijn 연구 사이트의 짧은 모양을 원형 기록에 담는 정의에서 착안했어요. 이 글은 전문 그래프 이론 대신 시작 위치의 개수로 하한을 잡고 자체8칸 기록으로 가능성을 확인해요. 교사는 “예가 있다”와 “더 짧게는 불가능하다”를 두 근거로 받아요.
원형에서 세는 m개 시작을 직선에도 그대로 쓰면 마지막 두 시작을 잘못 포함해요. 경계를 통과해 읽을 수 있는지 문항 조건이 먼저예요.
착안: De Bruijn Sequence and Universal Cycle Constructions, Graph model. 문항·예·최소길이 논증은 새로 작성했어요.