세 숫자카드를 작은 수부터 놓는 종이 활동이에요. 미리 정한 비교 하나를 깜빡해도 끝에서 정렬되게 할 수 있을까요?
세 값의 모음 x의 성분 x₁·x₂·x₃은 단위 없는 임의의 실수이며 같아도 돼요. 번호 i<j의 두 값을 비교해 작은 값은 i번, 큰 값은 j번에 넣어요. 다른 칸은 유지해요. 비교 하나가 생략되면 그 단계는 세 값을 그대로 통과시켜요. 생략은 없거나 한 번이며 자리는 몰라요. 입력을 보고 다음 비교를 고르거나 다시 시도할 수 없어요.
문자열은 왼쪽부터 실행해요. ACAC와 ACACA 중 모든 입력·생략을 견디는 계획을 고르고, 최소 횟수도 살펴봐요. ACAC의 두 번째 비교 C를 빼고 (1,1,0)을 넣으면 AAC 뒤 (1,0,1)이 남아 실패해요.
ACACA는 어느 자리를 빼도 같은 비교의 연속 반복을 한 번으로 줄이면 ACA 또는 CAC 뒤에 비교가 더 붙은 형태예요. ACA와 CAC는 세 값을 정렬하고, 이미 정렬된 값은 더 비교해도 바뀌지 않아요. 따라서 다섯 단계는 충분해요.
최소성도 볼까요? (1,0,1)은 A만이 처음 값을 움직이고, (0,1,0)은 C만이 움직여요. 한 번 생략을 견디려면 A·C가 각각 두 번 이상 필요해요. 네 단계라면 두 문자만 두 번씩 써요. 여섯 배열은 한 비교를 빼면 실패하는 입력이 있어 모두 탈락해요. 비교 횟수 m의 최솟값과 모든 최소 순서 N₅는 다음과 같아요.
위 열 순서가 최소 계획 전부예요. 여덟 가지 0·1 입력을 생략 위치마다 확인하면 실수 전체도 보장돼요. 역전된 두 실수 사이에 경계를 놓아 0·1로 바꿔도 비교와 생략이 같은 순서로 작동하기 때문이에요. 이는 앞 단계의 출력을 다음 입력으로 쓰는 합성함수예요.
착안: Liverpool COMP308 정렬망의 비교교환·0/1 원리. 생략 규칙·최소 계획·증명은 자체 구성이에요.