[9월의 퍼즐 해설]

우리는 사다리의 결과값을 ECDAB에서 ABCDE로 바꿔야 한다. 즉 E→A, A→D, D→C, C→B, B→E가 되도록 결과값을 치환해야 한다. 이렇게 5개의 알파벳이 순환하는 구조를 5-퍼뮤테이션이라 하자.

각 알파벳이 사다리를 타는 경로를 그렸을 때, 사다리에 가로줄을 하나 추가하면 다음과 같이 사다리의 결과에서 그 가로줄을 지나치는 2개의 알파벳을 교환하게 된다.

이렇게 사다리에 가로줄을 하나 그려서 결과값에서 2개의 알파벳을 교환하는 행위를 스왑이라 하자. 5-퍼뮤테이션을 만들기 위해서는 최소 4개의 스왑이 필요하다. 따라서 우리는 최소 4개의 가로줄을 그려야 한다. 그런데 문제를 들여다보면 자는 2번까지만 사용할 수 있고 자를 한 번 사용할 때마다 가로줄을 최대 2개까지만 그릴 수 있으므로, 가로줄은 최대 4개까지만 그릴 수 있다. 그렇다면 정확히 4개의 가로줄이 필요하다.

자를 1번 사용해서 가로줄 2개를 그리면 서로 겹치지 않는 알파벳 4개를 사용해 스왑을 두 번 하게 된다. 자를 한 번 대고 가로줄 2개를 그린 사다리의 결과값은 ECDAB에서 스왑이 두 번 일어난 상황일 것이다. 이 상태의 사다리를 중간 상황이라 하자. 중간 상황에서 자를 또 대고 가로줄 2개를 더 그린 사다리의 결과값은 중간 상황에서 다시 스왑이 두 번 일어난 상황일 것이다. 이 상태의 사다리를 최종 상황이라 하자. 최종 상황의 결과값을 ABCDE로 만들기 위한 중간 상황은 총 다섯 가지가 있다. 스왑 두 번을 할 때 알파벳 하나는 건드릴 수 없으므로, 어떤 알파벳을 미리 제자리에 갖다 두는지를 기준으로 가짓수를 나누면 쉽게 분류할 수 있다.

한편 자를 댈 수 있는 위치는 다음과 같이 총 8가지가 있다. 위에서부터 1부터 8이라고 번호를 붙이자. (이미 그려져 있는 가로줄과 같은 직선에 자를 대는 경우의 수도 있으나, 그 경우에는 해당 직선의 바로 위나 바로 아래에 자를 대는 것과 다를 바 없으니 생략했다. 또한, 같은 번호의 위치에 자를 두 번 댈 경우에는 위아래로 위치가 약간 차이나게 댄다고 생각하자.)

특정 자 위치에서 원하는 스왑이 가능하려면 원하는 두 알파벳이 바로 이웃한 세로줄을 지나야만 한다. 이를 고려하여 각각의 스왑을 만들어낼 수 있는 자의 위치를 모두 찾아 적으면 다음과 같다.

자를 2번 대고 가로선들을 그려야 하므로 둘 중 위쪽 위치와 아래쪽 위치가 있을 것이다. 둘 중 아래쪽에 먼저 자를 대서 중간 상황을 만들고, 그 다음 위쪽에 자를 대서 최종 상황을 만든다고 가정하자. 아래에 먼저 자를 댔다고 가정하는 이유는, 자를 한 번 대고 나면 그 위치보다 아래쪽에서는 알파벳들의 경로가 미리 작성해 둔 경로와 달라져 풀이가 복잡해지기 때문이다.

1번째 스왑들이 2번째 스왑들의 위치보다 같거나 아래라는 조건을 만족시키는 자의 위치 조합은 유일하다.

이를 사다리에 나타내면 다음과 같다.