텍스트 에디터 문제

윈도우 메모장 같은 텍스트 에디터에서 빈 문서에서 ab←cd←←e←←f라고 치면 faecdb가 표시된다. (여기서 ←는 왼쪽 화살표이며, insert 키를 누르지 않은 삽입 모드를 상정한다) 이렇게 한 문자열 A(ex:abcdef)를 치는 도중 왼쪽을 쳐서 다른 문자열 B(ex:faecdb)를 얻을 수 있다면, 반대로 B에서도 A를 마찬가지 방법으로 얻을 수 있다.

2014년 미국 IMO TSTST(IMO 선발을 위한 시험을 치르기 위한 선발시험) 1번 문제. 재미있는 세팅의 문제라 인상적이었다. 실제로 위와 같은 시행을 하다보면 모든 순열을 다 얻을 수 있지는 못한다. 예컨대, abc에서 아무리 왼쪽 화살표를 추가하더라도 bac는 얻을 수가 없다. 한 문자열에서 다른 문자열을 얻을 수 있더라도 그 역도 성립하는지 역시 단언할 수 없는데 이 문제는 그것이 참임을 알려주고 있다. 여기서는 그림을 그려 푸는 풀이를 소개하고자 한다.

도중에 커서 위치가 맨 처음으로 갔음에도 ←를 누르는 것은 결과에 영향을 주지 않으므로 이런 상황에서 추가적으로 ←를 누르는 것은 무시하도록 한다. 또한, 마지막에 ←를 몇 번 눌러 커서 위치를 맨 처음으로 움직이는 것도 결과에 영향을 주지 않으므로 마지막 상황에서 ←를 눌러 커서 위치를 맨 앞에 위치하도록 한다, 이 때, 문자를 칠 때마다 ↗를 그려 그 위에 그 문자를 넣고, ←를 누를 때마다 ↘를 그려 그림과 같이 정확하게 n개의 ↗과 n개의 ↘를 쓴 그림을 얻을 수 있다. (여기서 n은 문자열 길이)

ab←cd←←e←←f (에다가 끝에 ←를 덧붙임)

그러면 위 그림처럼 내부에 평행선을 그으면, 각각의 ↘마다 그에 해당되는 ↗을 찾을 수 있게 된다. 이 때 ↘에 대응되는 문자를 그에 해당하는 ↗에 빨갛게 써두도록 한다. 그러면 모니터에 뜨는 최종 결과물은 빨간 문자열을 거꾸로 읽은 것임을 n에 대한 귀납법으로 보일 수 있다. (위 그림의 경우 빨간 문자열을 거꾸로 읽으면 faecdb가 된다) n=1인 경우는 자명하고, 길이가 n보다 작을 때 성립함을 가정한다. 그러면 두 가지 경우를 생각할 수 있다.

  • 만약 위 그림처럼 사선들을 그리다가 도중에 x축에 닿은 적이 있었다면, 처음부터 그 지점까지 친 결과로 남는 문자열 A 앞으로 그 지점에서 마지막까지 친 결과로 남는 문자열 B가 오는, 즉 BA꼴의 문자열이 나타나게 된다. 귀납 가설에 의해 A는 빨간 문자열 앞부분, B는 빨간 문자열 뒷부분을 거꾸로 읽은 것이므로 이들을 합치면 성립함을 확인할 수 있다.
  • 만약 도중 한 번도 x축에 닿은 적이 없었다면, 맨 처음에 쳤던 문자열 앞으로는 커서가 한 번도 움직이지 않았다는 뜻이므로 그 문자열은 계속 맨 앞 위치에 고정된다. 이 맨 처음 문자와 맨 마지막 ←을 제외한 중간 부분은 귀납 가정에 의해 빨간 문자열들을 거꾸로 읽은 것이 되므로 맨 마지막 ←에 해당하는 문자(=맨 처음 문자) 뒤로 나머지 빨간 문자열들을 읽는 것이 되어 역시 성립함을 확인할 수 있다.

이제 원래 문제로 돌아와 문자열 A에서 문자열 B를 얻었다고 가정한다. 그러면 위에서처럼 검은 문자열을 왼쪽에서 오른쪽으로 읽으면 A, 빨간 문자열을 오른쪽에서 왼쪽으로 읽으면 B가 되는 그림을 그릴 수 있는데, 이 그림을 좌우 반전시킨다.

이 그림은 B를 써내려나가는 도중 ←들을 덧넣은 것을 표현한 것이 되는데, (위 그림의 경우 f←ae←cd←←b←←) 그 결과물이 ↘에 대응되는 문자를 거꾸로 읽은 A가 됨을 얻을 수 있어 증명이 끝난다.

위 그림처럼 ↗과 ↘를 같은 개수만큼 쓰되 수평선 아래로 넘어가지 않는 그림을 Dyck path라고 부르며, 위에서처럼 두 화살표를 짝지어 일대일대응을 찾거나 다른 map을 찾는 것은 조합론에서 곧잘 볼 수 있는 방법론이다.

참고로, 원래 문자열을 1에서 n까지 쓴 수열이라 생각하면 마지막에 얻는 결과물은 한 순열이라고 볼 수 있게 되는데, 이렇게 항등순열에서 시작해 얻을 수 있는 순열이 213-avoiding이란 것과 동치가 된다. 213-avoiding이란 순열을 나열했을 때 연속한 세 항의 상대적 크기 순서가 2-1-3과 같은 경우를 배제하는 순열, 즉 w(i+1)<w(i)<w(i+2)i가 존재하지 않는 순열을 뜻한다. 이를 보일 수 있게 되면 213-avoiding 순열의 inverse 역시 213-avoiding이란 사실을 보임으로써 증명을 끝낼 수 있다.

트윗 타래를 정리. (2016/08/02)

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중