안녕하세요, 문제 출제자 국가수라과학연구소 연구원 백진언입니다.

혹시 핑순이가 구체적으로 어떤 단어를 만드는 걸가 궁금해하시는 분들이 계실 수 있는데,

핑순이가 만드는 단어들은 'ab', 'ac' 'bc', ... 같이 길이 2의 단어들이 아니라,

'abab', 'acac', 'bcbc', 'adad', ... 처럼 길이 4의 단어들입니다.

처음에 개 만큼의 두 글자 단어를 만들고 , 이 중 다시 2개를 선택해 네 글자 단어를 만드므로 만큼의 단어가, 52650개네요.

[문제 1]

"국가수리과학연구소 8번 클리어"

[서울과학고등학교 1학년 김홍녕]

질문1: 핑순이는 처음에 몇 개의 단어를 가지고 있었을까?

26개의 알파벳 중 두 개를 고르는 가짓수가 26*25개, 그 중 사전순으로 늦게 오는 글자를 뒤에 골라야 하므로 26*25/2가지이다.

두 알파벳 ㄱ과 ㄴ을 골랐다면 ㄱㄴㄱㄴ형태로 "최초의 단어"를 만들 수 있으므로 325개의 "최초의 단어"가 존재한다.

질문2: 핑순이가 최종적으로 만든 단어의 앞 26글자는 뒤 26글자와 같을까?

답: 같다.

증명: 우선, 할 수 있는 시행의 종류를 변형하자.
시행1) 한 단어에서 맨 앞에 있는 글자를 맨 뒤로 가져오거나, 맨 뒤에 있는 글자를 맨 앞으로 가져올 수 있다
는 것은, 단어를 모두 다음과 같이 원 형태로 나열하는 것으로 대체할 수 있다.

그러면, 시행2)는 다음과 같이 변형 가능하다. 
두 원형 단어가 있을 때, 각각 한 지점을 잡고, 그 지점을 기준으로 단어를 합쳐 하나의 큰 원형 단어를 만들 수 있다.

마지막으로, 시행 3)는 그대로 같은 글자 두 개가 붙어있으면 두 글자를 모두 없앨 수 있다. 로 한다.

본문제 풀이: 다음과 같이 각 알파벳에 "이름표"를 붙이고 옮기는 규칙을 정의하자.

[규칙 1] 최초의 단어에서, 각각의 알파벳은 그 단어 내에 있는 다른 알파벳이 쓰여 있는 이름표를 가진다.
예를 들어, 단어 soso에서 두 개의 s에는 o가 쓰여있는 이름표를 붙이고, 두 개의 o에는 s가 쓰여있는 이름표를 가진다.

쌍 조건: 임의의 알파벳(예시: a)을 골랐을 때, 그 알파벳과 같은 단어 안에 있는 동일한 알파벳(a) 중 붙어있는 이름표의 집합이 같은 알파벳(즉, 짝꿍)이 존재한다.
처음의 이름표 배치는 자명하게 "쌍 조건"을 만족한다.

[규칙 2] 시행 3)을 하였을 때, 예를 들어 a 두 개가 없어졌다고 가정하자. 그리고 첫 번째 a가 이름표 b,f,z를 가지고, 두 번째 a가 이름표 c,g,y를 가지면, 그 둘이 사라지면서 각자의 짝꿍 알파벳들은 이름표 b,c,f,g,y,z를 가지며, 그 둘이 새로운 짝꿍이 된다.

그러면 임의의 순간에서도 쌍 조건은 항상 성립하며, 이름표의 총 개수는 변함이 없다. 최초의 단어들에서 a를 기준으로 보았을 때, a라는 알파벳들이 가지고 있는 총 이름표는
b 2개, c 2개, d 2개,..., z 2개이고, 이는 다른 알파벳들에 대해서도 마찬가지이다. ★

보조정리: 짝꿍 알파벳 한 쌍이 가지고 있는 이름표의 집합에서, 그 집합에 속하는 알파벳만 두 짝꿍 알파벳 사이에 홀수 개 존재한다.
예를 들어, 두 짝꿍인 e가 각각 이름표를 r,t,j를 가지고 있다면, r,t,j만 그 두 개의 e 사이에 홀수 개씩 존재한다.

증명) 귀납적으로 접근하자, "최초의 단어" abab에서 a는 각각 b가 쓰여진 이름표를 가지고, b는 a 사이사이에 하나(홀수)씩 존재한다.
시행 2)를 했을 때를 생각하자. 각각의 단어에는 각 알파벳이 짝수개 있다. 합쳐질 때랑 사라질 때 모두 짝수개씩 더하고 빼지기 때문이다.
그러므로 원형 단어의 임의의 위치에 새로운 단어가 추가되어도, 두 짝꿍 알파벳 사이 다른 알파벳 개수의 홀짝성과, 두 짝꿍 알파벳의 이름표 집합은 변하지 않는다.
시행 3)을 했을 때를 생각하자.

위 그림과 같이 여전히 두 짝꿍 알파벳 사이에는 알파벳이 가지고 있는 이름표에 해당하는 알파벳만 홀수 개 존재하게 된다. 위 그림에서 이름표 C를 가지는 알파벳 A가 이름표 B,D를 가지는 알파벳 사이에 있는 경우에서 마찬가지로 증명된다. 보조정리 증명 끝

그리고, 삭제되는 두 알파벳이 가지고 있는 이름표가 겹칠 수 없다. 그러니까, 두 A가 삭제될 때, 두 A 모두 이름표 B를 가지고 있는 상황은 일어나지 않는다는 것이다. 왜냐하면 ★에 의해서, 각각의 이름표 개수는 2개씩으로 유지되는데, 두 A 모두 이름표 B를 가지고 있었다면 그 두 A는 서로 짝꿍이다. 따라서 A와 A 사이에 B가 홀수 개 있어야 하지만, 삭제되는 상황에서 A는 서로 붙어 있으므로 모순이다.
만약에, 모든 단어상에서 A가 완전히 사라지는 경우를 생각하자. 그러려면 완전히 사라지는 순간에 마지막 남은 두 알파벳은 서로 짝꿍이어야 하므로 인접해 있다는 것에 모순.
그러므로 마지막 순간까지 각각의 알파벳은 총 두 개 이상 존재한다. (한 쌍 이상)
시행이 끝나는 순간, 총 알파벳이 52자이므로, 각 알파벳은 정확히 두 개(짝꿍 한 쌍) 존재하며, 이름표 개수 보존의 법칙 ★에 의해, 두 짝꿍 A는 자신을 제외한 다른 알파벳이 적힌 모든 이름표(B,C,D,...,Z)를 가지고 있고, 보조정리에 의해 두 A 사이에는 B부터 Z까지가 홀수 개 존재하며, 각 알파벳은 단어 내에 2개 존재하므로,
두 A 사이에는 B부터 Z까지가 하나씩 존재한다. 따라서 두 A는 원형 단어상에서 26칸 거리, 정반대편에 위치하게 되며, 이는 다른 알파벳에 대해서도 마찬가지이다.
따라서 원형 알파벳의 시작점을 어디로 정하든지 간에, 처음 26자와 마지막 26자는 서로 같다.

Q.E.D

??? 전 풀이에 기여한게 딱히 없는 것 같은데요...?