못에 감은 끈은 시계방향으로 감은 횟수와 반대로 감은 횟수가 같으면 풀릴까요? 감은 순서를 빼고 숫자만 더한 기록이 어떤 정보를 놓치는지, 액자 걸기의 문자 모형으로 확인해 볼까요? 실제 끈의 마찰이나 매듭, 설치 안전성은 다루지 않아요.
못 a,b,c를 시계방향으로 감는 기호는 a,b,c, 반대 방향은 A,B,C로 써요. 바로 이웃한 aA 또는 Aa처럼 같은 못의 반대 기호 한 쌍만 지울 수 있어요. 기호들을 마음대로 바꾸어 놓을 수는 없어요. 못을 제거하면 그 못의 두 기호를 모두 지워요. 남은 열을 빈 열로 만들 수 있으면 이 모형에서 ‘떨어진다’고 정해요.
다음 기록을 판정해 보세요. 각 못의 소문자 개수에서 대문자 개수를 빼면 모두 0입니다.
그런데 이 열에는 바로 이웃한 역기호가 없어요. 첫 삭제조차 할 수 없으므로 빈 열이 아니에요. 반대 기호들이 서로 다른 위치에 있다는 사실을 감김 수의 합은 남기지 못해요. 떨어짐 판정에서 필요한 것은 합뿐 아니라 허용된 순서예요.
이제 못 하나를 제거하자. a와 A를 지우면 bcBC가 남아요. b와 B를 지운 뒤에는 aA를 없애 caCA가 남아요. c와 C를 지운 뒤에는 끝의 aA가 없어져 abAB가 남아요. 어느 경우에도 다시 지울 이웃 역기호가 없어서 빈 열이 되지 않아요.
못 두 개를 제거하면 상황이 달라져요. 남은 한 못의 두 방향 기호는 같은 개수예요. 그런 열이 비어 있지 않으면 어딘가에서 소문자와 대문자가 이웃해요. 한 쌍을 지우면 두 개수가 함께 줄어 다시 같은 상황이에요. 유한한 열이므로 반복하면 빈 열이 돼요. 세 못을 모두 제거하면 처음부터 아무 기호도 없어요.
‘정확히 두 개를 제거할 때만 떨어지고 세 개를 빼면 다시 버틴다’는 결과표는 가능할까요? 이 모형에서는 불가능해요. 세 못을 모두 지우는 특수 경우만이 아니라, 제거 목록이 커질 때의 일반 조건을 증명할 수 있어요.
어떤 제거 목록 S에서 빈 열까지 한 쌍씩 지우는 과정을 잡아요. 더 큰 제거 목록 T에 들어간 새 못의 기호들을 그 과정에서도 모두 지우자. 원래 삭제하던 두 기호는 같은 못의 반대 기호이므로 둘 다 새로 사라지거나 둘 다 남아요. 남으면 여전히 바로 이웃한 역기호다. 따라서 원래 삭제 과정의 불필요한 단계만 건너뛰어 T에서도 빈 열을 만들어요. 이미 떨어진 뒤 더 많은 못을 제거해서 다시 버티는 경우는 만들 수 없어요.
교사는 순감김 수가 0이라는 한 숫자와, 허용된 삭제 과정이 있다는 판단을 나누게 해요. 그런 뒤 결과표의 한 행만 맞는지 보는 대신 제거 목록 사이의 포함 관계에도 판정이 맞는지 확인하게 해요. 그림이 그럴듯하다는 설명이나 실제 액자 실험의 성공률로 이 증명을 대신하지 않아요.
착안: Erik D. Demaine 외, Picture-Hanging Puzzles, §3.2·§4.1. 원문의 문자 삭제 정의를 명시하고 자체 기록의 모든 제거 목록과 잘못된 결과표를 검사했어요. 원문 그림이나 활동 문항·문장의 번역이 아니에요.