주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국8. 핑순이의 단어 놀이 (삐용삐용) 디듀우, 빌 힉스, 수돌이님 연락주세요!

2017.07.28

같이 풀어볼까?

네이버밴드 구글플러스

ⒸGettyImagesBank

강아지 핑순이는 a부터 z까지 알파벳 26개 가운데 일부를 써서 새로운 단어를 만들 수 있음을 알았다. 글자 a와 글자 b로 단어 ‘ab’를 만들 수 있다. 이 단어를 두 번 반복하면 또 다른 단어 ‘abab’를 만들 수 있다. 이때 핑순이는 단어를 이루는 글자 가운데 알파벳 순서 상 먼저 오는 글자가 언제나 단어의 첫 글자가 되게 하기로 결심했다. 예를 들어, 글자 a와 글자 b로 단어 ‘ba’, ‘baba’는 만들 수 없다.

재미가 붙은 핑순이는 26가지 글자 중 두 글자를 뽑는 모든 조합을 생각하고, 두 글자를 조합해 단어를 몇 개 만들었다. 그리고 이 단어들을 연결하는 세 가지 작업을 통해 또 하나의 단어를 만들기로 했다. 세 가지 작업은 다음과 같다. 

 

➊ 단어 합치기

두 가지 단어를 풀로 붙이듯이 붙일 수 있다. 이를테면, 단어 ‘abab’와 단어 ‘bcbc’를 붙여서 새로운 단어 ‘ababbcbc’를 만들 수 있다. 이렇게 하면, 원래 있던 두 가지 단어 ‘abab’와 ‘bcbc’는 하나로 합쳐졌기 때문에 다시 따로 떼어놓을 수 없다.

ⒸGettyImagesBank

 

➋ 단어 돌리기

한 단어에서 맨 앞에 있는 글자를 맨 뒤로 가져오거나, 맨 뒤에 있는 글자를 맨 앞으로 가져올 수 있다. 이를테면, 단어 ‘ababbcbc’의 첫 글자 ‘a’를 단어 맨 뒤로 보내 ‘babbcbca’로 만들 수 있다. 또는 마지막 글자 ‘c’를 단어 맨 앞으로 보내 ‘cababbcb’로 만들 수 있다.

ⒸGettyImagesBank

 

➌중복인 두 글자 없애기

같은 글자 두 개가 붙어있으면 두 글자를 모두 없앨 수 있다. 이를테면, 단어 ‘ababbcbc’의 가운데에 중복한 ‘bb’를 없애서 새로운 단어 ‘abacbc’를 만들 수 있다.

ⒸGettyImagesBank

 

본격적인 핑순이의 단어 놀이

작업에 익숙하지 않은 핑순이는 세 가지 단어 ‘abab’, ‘acac’, ‘bcbc’로 놀이를 시작했다. 위의 세 가지 작업을 하는 횟수나 순서는 모두 자유다. 세 가지 중 일부 작업만 해도 된다.

 

핑순이는 먼저 단어 ‘abab’의 앞 글자를 맨 뒤로 보내 ‘baba’를 만들었다.

이 단어 ‘baba’와 ‘acac’를 합쳐 하나의 큰 단어 ‘babaacac’를 만들었다.

가운데에서 중복인 a 두 개를 없애 ‘babcac’를 만든다.

단어 ‘bcbc’의 맨 뒤 글자를 맨 앞으로 보내 ‘cbcb’를 만든다.

단어 ‘babcac’와 ‘cbcb’를 합쳐 ‘babcaccbcb’를 만든다. 이로써 세 단어를 모두 합쳤다.

단어 ‘babcaccbcb’의 가운데에서 중복인 c 두 개를 없애 ‘babcabcb’를 만든다.

맨 뒤 글자를 맨 앞으로 보내 ‘bbabcabc’를 만든다.

맨 앞에서 중복인 b 두 개를 없애 최종적으로 단어 ‘abcabc’를 만든다.

모든 작업을 마치고 단어 ‘abcabc’를 얻은 핑순이는 이 단어의 앞 세 글자와 뒤 세 글자가 같음을 발견했다.

 

<문제>

또 다른 놀이를 시작한 핑순이는 a부터 z까지 모든 알파벳을 써서 만든 단어들을 하나로 합쳐 52개의 글자로 이뤄진 한 단어를 만들었다.

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

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

 

※참고 알파벳에는 총 26개의 글자가 있다.

 

★알립니다★

질문 1의 답은 \frac{26\times 25}{2} 입니다. 최초로 답을 맞힌 '디듀우'님과

그 과정에 도움을 주신 '빌 힉스'님이 함께 답을 맞힌 것으로 하겠습니다!

그리고 질문 2를 '수돌이'님이 풀었습니다.  오랜만에 모든 문제가 완전 해결 됐네요! laugh

이 글을 보신 디듀우, 빌 힉스, 수돌이 님은 수학동아 이메일(math@dongascience.com) 또는 이 게시글의 비밀댓글로 이름과 휴대폰 번호를 남겨주세요. 멘토링 및 인터뷰를 할 예정입니다! 

 

댓글 11

  • NIMS 폴리매스 2017.07.31 16:59:19

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

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

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

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

    좋아요1 댓글수0
  • 디듀우 2017.08.04 21:00:07

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

    [문제 1]

    좋아요0 댓글수2
    • 빌 힉스 2017.08.04 21:35:45

      보여준 모든 예에서 앞 두글자가 한번 더 반복되는 경우 밖에 안보이는데, 앞 뒤가 달라도 되는 걸까요? 

      좋아요0
    • 디듀우 2017.08.05 21:05:24

      그러면 그냥 \frac{26*25}{2*1}인 325가 정답 아닐까요?

      좋아요0
  • 수돌이 2017.08.24 21:05:59

    "국가수리과학연구소 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

    좋아요0 댓글수4
    • 구머 2017.08.25 00:43:47

      respect

      좋아요0
    • 여백 패르마 2017.08.27 20:31:25

      너무너무 천재이시네요

      (과학고도 가셨다니...)

      좋아요0
    • 구머 2017.08.27 23:26:52

      수돌이님 혹시 중2때 서과고 합격한건가요?

      좋아요0
    • 수돌이 2017.08.31 20:12:16

      네!

      좋아요0
  • 빌 힉스 2017.09.02 21:25:29

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

    좋아요0 댓글수1
    • 고은영 2017.09.11 18:15:22 비밀댓글
      비밀댓글 입니다.