본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[슬기로운 수학생활] 슬5. 문자열 갖고 놀아보자!
수학동아 2020.09.01 11:13

a, b, c로만 이루어진 임의의 유한한 길이의 문자열 s가 있다.

예를 들어 aabaac, ccaabbcc 등이 있을 수 있다.

 

다음 3가지 규칙을 반복 적용해서 s의 일부를 바꿀 수 있다.

 

 

R_1 : aa\rightarrow bc

R_2 : bb\rightarrow ac

R_3 : cc\rightarrow ab

 

 

예를 들어, aabaac에는

aabaac-(R_1)\rightarrow aabbcc-(R_1)\rightarrow bcbbcc-(R_2)\rightarrow bcaccc-(R_3)\rightarrow bcaabc-(R_1)\rightarrow bcbcbc

으로 규칙을 적용할 수 있다.

 

 

다른 방법으로는

aabaac-(R_1)\rightarrow bcbaac-(R_1)\rightarrow bcbbcc-(R_3)\rightarrow bcbbab-(R_2)\rightarrow bcacab

도 있을 수 있다.

 

 

두 방법 모두 최종적으로 얻은 문자열에는 어떤 규칙도 적용할 수가 없다.

 

 

문제는 다음과 같다.

 

 

어떤 유한한 문자열 s로 시작해도, 3가지 규칙을 반복해서 적용하면 언젠가는 규칙을 적용할 수 없는 순간이 올까?

 

아니면, 어떤 문자열 s와 위 3가지 규칙을 적용하는 특정한 방법이 있어서, 규칙을 무한히 적용할 수 있을까?

 

 
  •  
    인간의 이중성 Lv.6 2020.09.01 11:22

    규칙이라는 게 어떤 걸 의미하나요? 어떤 문자열들이 반복돼서 나타나는 형태인가요?

    댓글 작성하기 좋아요0 댓글수2
    •  
      유클리드 Lv.6 2020.09.01 11:22

      R1,R2,R3의 방법을 말하는 것 같습니다.

      좋아요0
    •  
      인간의 이중성 Lv.6 2020.09.01 11:23

      아 R1 R2 R3가 규칙인 거군요 감사합니다!

      좋아요0
  •  
    mathwizard Lv.7 2020.09.01 14:26

    abcabc처럼 R1, R2, R3규칙을 적용할 수 없는 문자열은 어떻게 하나요? 그냥 제외시키는 건가요?

    댓글 작성하기 좋아요0 댓글수2
    •  
      유클리드 Lv.6 2020.09.01 15:33

      뭐 이경우는 그 자신이 최종 문자열이겠죠

      좋아요0
    •  
      mathwizard Lv.7 2020.09.01 16:19

      아, 그렇겠네요.

      좋아요0
  •  
    유클리드 Lv.6 2020.09.01 16:23

    전, 무한히 적용은 안된다고 생각해서 다음과 같이 생각합니다.

    귀류법으로 무한하다고 가정했을 때

    (1) 사이클이 필연적으로 생긴다. (증명해야 함)

    (2) 사이클이 생기면 안된다.

    이 2가지를 증명하면 될 꺼 같아요

    댓글 작성하기 좋아요1 댓글수1
    •  
      mathwizard Lv.7 2020.09.01 16:25

      저도 무한히 적용되는 것은 불가능하다고 생각합니다.

      좋아요0
  •  
    MathlabJ Lv.8 2020.09.02 09:12

    저는 a,b,c를 각각 0,1,2로 생각해서 3진수로 생각해보려고 했는데..

    혹시 이렇게 3진수로 생각했을때 더이상 규칙을 적용할수 없는 수들의 공통적인 수학적 특징이 있나요?

    (지금 그거 생각하는 중입니다)

    댓글 작성하기 좋아요1 댓글수2
    •  
      MathlabJ Lv.8 2020.09.02 09:13

      아니면 규칙을 적용할수 있는 수들의 공통적인 수학적 특징도 괜찮고요..

      좋아요0
    •  
      최기자 Lv.4 2020.09.02 09:17 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    리프 Lv.6 2020.09.02 17:58

    현재까지 알아낸 정보입니다. (폴매 디코 서버에서 같이 알아낸 내용입니다.)

     

    사용 중인 문제 접근 방법: 어떤 문자열이 존재하여 자기 자신으로 돌아오게 하는 적당한 시행이 존재한다고 가정하자. 이를 사이클이라 할 때, 사이클이 존재하는 문자열의 최소 길이를 n으로 정의하자. 이때, 길이가 n이면서 사이클이 존재하는 문자열이 존재하면 모순이 발생함을 보이자.

     

    위 접근 방법으로 알아낸 사실

    1. 사이클 내에서 R1, R2, R3의 시행 횟수는 동일하다. (a, b, c 개수 생각)

    2. n보다 작은 임의의 자연수 k에 대하여 (k, k+1) 문자에 대해 규칙을 적용한 경우가 사이클 내에 반드시 존재한다. (n이 최소 길이임을 사용하면 증명 가능)

    2-1. 사이클에서 자기 자신으로 다시 돌아오기 위한 최소 시행 횟수는 n+1 이상이다.

     

    대충 이 정도네요. 더 알아내면 추가하겠습니다.

    댓글 작성하기 좋아요1 댓글수0
  •  
    31⇒P Lv.11 2020.09.02 20:40

    다른 방법으로는

    aabaac-(R_1)\rightarrow bcbaac-(R_1)\rightarrow bcbbcc-(R_2)\rightarrow bcbbab-(R_3)\rightarrow bcacab

    도 있을 수 있다.

     

    이 문장에서 R2랑 R3이랑 바뀐 느낌이 나네요

     

    댓글 작성하기 좋아요0 댓글수0
  •  
    31⇒P Lv.11 2020.09.02 21:22

    이 문제의 답은 '어떤 문자열로 시작해도 언젠가는 적용할 수 없는 순간이 온다'입니다.

    무한히 반복한다면, 아무리 길어도, 유한한 문자열에서는 중복해서 등장하는 문자열이 존재할 것이고, 우리는 문자열이 여러번 나타날 수 없다는 것을 증명하면 됩니다.

    'aa'가 있을 때, 그 다음에 무언가르 해보려면 앞에 b가 있거나 뒤에 c가 있어야합니다.

    하지만 b를 선택하나,c를 선택하나 앞뒤의 차이밖에는 되지 않습니다.

    그러므로 우리는 모든 경우의 수를 해 볼 필요가 없습니다.

    각각의 분점에서 다른 경우도 이 경우와 결론이 같다라는 것만 확인하면 됩니다.

     

    오늘은 이까지 하고 가겠습니다.

    기초적인 것들이지만 혹시라도 필요하시다면 대댓글 달아주시고 마음껏 써가시기 바랍니다.

    전 증명같은건 잘 못해서 ...ㅠ

     

    1줄요약:무한히 돌아가는거 같은거 없다. 찾으려는 생각 하지 마라.(뭐 본인 마음이지만)

    댓글 작성하기 좋아요0 댓글수0
  •  
    스리니바사 라마누잔 Lv.1 2020.09.03 23:56 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수6
    •  
      Sin X Lv.5 2020.09.04 00:08 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      스리니바사 라마누잔 Lv.1 2020.09.04 00:15
      1. R1, R2, R3를 무한히 시행하기 위해서는 유한한 수열에서는 a, b, c로 만들 수 있는 수열의 종류가 유한하므로 비둘기집의 원리에 의해 어떤 수열 s’이 적어도 2번 나타나야 한다.
      2. S’에서 다시 s’이 되기까지 R1, R2, R3에 한 번도 참여하지 않은 자리가 있을 때 그 자리를 기준으로 왼쪽의 수열과 오른쪽 수열이 R1, R2, R3에 ‘함께’ 참여하지 못 하므로 여기서 왼쪽 수열과 오른쪽 수열 역시 다시 자기 자신으로 되돌아올 수 있는 수열이어야 한다. 따라서 자기 자신으로 다시 되돌아올 수 있는 어떤 수열의 모든 자리들은 적어도 한 번 R1, R2, R3에 참여해야 한다. 그리고 이 다시 돌아올 수 있는 최소 길이의 수열을 k라하자
      3. k의 가장 왼쪽 부분이 c가오면 안된다 왜냐하면 R1:aaàbc, R2:bbàac, R3: ccàab이니 ccàab로 될 때 그 자리가 a가 되는데 각 변환의 왼쪽 자리만 볼 때 c로 되돌아 오는 것은 없기 때문이다.
      4. 맨 외쪽이 b라면 이 b 또한 변환을 통하여 다시 b가 되어야 한다. 그래서 이 b가 변환에 참여하기 위해서는 그 옆에 b가 와야 할 수 있다. (만약 ba, bc이어도 c 와 a가 변형돼서 b가 돼야 그 b가 변환될 수 있다. 따라서 결국엔 bb가 형성되고 k가 최소의 길이이기 때문에 자기자신으로 되돌아올 수 있는 방법이 많다고 하여도 모든 자리를 사용하여야 ‘최소 길이’라는 것을 만족한다 따라서 bb도 적어도 2번이상 나타나게 된다.) 따라서 bbàac가 되고 여기서 반응을 이어 나가기 위해서는 acàaccàaabàbcb하지만 여기서 c가 앞으로 오는 변환은 없으므로 다시 bb가 될 수 없으므로 b로 시작할 수 없다.
      5. 그렇다면 a로 시작하면 어떻게 될까 a도 b와 같은 논리로 aa로 시작해야 하며 이도 2번이상 나타난다. aaàbc가 되는데 이 또한 반응을 이어 나가야 하지만 a 또는 b를 붙이면 c가 앞으로 오는 변환은 없으므로 모순이고 그 뒤에 c를 붙이면 bccàbab가 되고 계속 이어 나가려면 babàbabb까지 보면 처음의 형태인 aacb로 다시 되돌아와야 한다. 여기서 거꾸로 가보면 aacbßabbb(c가 앞에 오는 변환은 없으므로 (c b)나 (c a)는 되돌아 갈 수 없으므로 여기서는 ac만 되돌아갈 수 있다.) abbbßccbb (마찬가지로 abbba는 돌아 가지 못하고 abbbc는 abbaa가 되므로 돌아갈 수는 있어도 한 번 더 돌아갈 수는 없다.) 따라서 어떤 경우에서도 ccbb를 만드는 것은 불가능 하므로 만들 수 없다.라고 했는데 오류 검토해 주실 수 있나요?   
      좋아요0
    •  
      수돌이 Lv.3 2020.09.04 04:43

      bbccb->acccb->aabcb->aaacb->abccb->ababb->abaac->abbcc->aaccc->bcccc와 같이 다시 b로 돌아올 수 있습니다.

      좋아요0
    •  
      스리니바사 라마누잔 Lv.1 2020.09.04 10:16

      aabcb-->aaacb가 어떻게 가능하죠?

      좋아요0
    •  
      Sin X Lv.5 2020.09.04 10:20

      bbccb->acccb->aabcb->aaacb->abccb->ababb->abaac->abbcc->aaccc->bcccc  수돌이님 3번째에서 4번째로 가는 과정이 이해되지 않습니다.

      aabcb->aaacb 이것좀 설명 부탁드립니다.

      좋아요0
    •  
      수돌이 Lv.3 2020.09.04 10:36

      bb->ac->acc->aab->aabb->aaac->abcc->abab->ababb->abaac->abbcc->aaccc->bcccc입니다 예시를 잘못 달았네요ㅠㅠ

      좋아요0
  •  
    퍼즐-Scratch Lv.4 2020.09.14 23:20

    (오류가 있거나, 제가 잘못된 용어를 사용하고 있다면 언제든지 지적해주시기 바랍니다.)

     

    저는 각 문자열의 '연결 상태'를 나타내는 그래프를 만들면 좋을 것이라고 생각했습니다. 즉, R1 ~ R3을 통해 각 문자열이 어떤 다른 문자열이 되면, 화살표로 두 문자열을 연결하는 것입니다. 그래서 파이썬과 엔트리를 이용하여 이 작업을 했고, 코드는 마무리되는 대로 올리려고 합니다. 

     

    뜻밖의 결과가 나와서 서둘러 글을 씁니다. 아래 그림들은 문자열의 길이가 1, 2, 3, 4일 때 연결 상태가 어떻게 되는지 나타냅니다. (편의를 위해 길이가 i일 때의 그래프를 'i-그래프'라고 부르겠습니다.)

     

    1-그래프

    2-그래프

    3-그래프

    4-그래프

     

    문자열의 길이가 1, 2, 3일 때는 별다른 특징을 찾기 어려웠습니다. 그러나 문자열의 길이가 4일 때는, 다음의 특징이 뚜렷하게 보였습니다. 

     

    "모든 그래프는 (화살표의 방향까지 고려하여) 대칭이거나, 화살표의 방향까지 고려한 연결 상태가 같은 그래프가 쌍으로 존재한다." 

     

    놀랍게도, 4-그래프의 가장 왼쪽 위에 있는 그래프는 대칭형이었던 것입니다. 오른쪽 아래에 있는 두 그래프는 화살표의 연결 상태가 동일했습니다. 이 '특징'은 길이가 1, 2, 3일 때도 성립했습니다. 

     

    이것은 어떤 "문자열간의 대응(f-대응이라고 하겠습니다.)"의 존재성을 뒷받침하는 결과라고 생각됩니다. 문자열 간의 연결 상태를 보존하는 대응이 존재하는 것이 거의 확실해 보입니다. f를 알아내기 위해 길이가 4인 경우 오른쪽 아래의 두 그래프를 대조해보았습니다. 그 결과, f에 의해 서로 대응되는 문자열은 원처럼 동그랗게 말았을 때 '형'이 동일한 것으로 보입니다. 예를 들어, 서로 대응되는 ccab와 bcaa를 각각 동그랗게 말면 동일한 문자가 연속해서 나타나는 개수가 각각 2-1-1입니다. ccab의 경우, 동그랗게 말아서 c부터 시작하면 'ccab'가 그대로 되고 '동일한 문자가 연속해서 나타나는 개수'는 c 2개, a 1개, b 1개이므로 형은 2-1-1입니다. bcaa의 경우, 동그랗게 만다면 결국 aabc와 동일하므로 역시 형이 2-1-1인 것입니다. 즉, 'f'는 어떠한 규칙에 따라 a, b, c를 치환하고, 원처럼 동그랗게 말아 다른 지점을 기준으로 다시 펴는 종류의 대응일 것으로 보입니다. 그 규칙이 무엇일지는 아직 미지수입니다. 

     

    또, '특징'이 사실이라고 가정하면 처음에서 다시 처음으로 돌아오는 사이클이 짝수 개 존재해야 합니다. 사이클 자체는 대칭이 아니기 때문입니다. 

     

    지금까지 알아낸 내용을 정리해보았습니다. 어쩌면 문자열의 길이가 5 이상일 때에는 아예 성립하지 않을 수도 있습니다. (사실 지금 제가 짠 프로그램으로, 문자열의 길이가 5 이상일 때의 그래프를 그리지 못해서 고민하고 있습니다.) 또는, 이것이 너무나도 자명한 성질인데 제가 눈치채지 못하고 있는 것일 수도 있습니다. 이 '특징'이 정말로 성립하더라도 문제 해결에는 도움이 안 될 수도 있습니다. 하지만 저는 이것이 정말 신기했고, 이런 성질이 있을 줄 전혀 예상하지 못했습니다. 여러분들의 생각은 어떤가요? 

    댓글 작성하기 좋아요0 댓글수6
    •  
      퍼즐-Scratch Lv.4 2020.09.15 10:25

      어제 쓴 글을 다시 읽어보았는데, R1, R2, R3의 색을 구분하면 또 다른 특징이 보일 수도 있겠다는 생각이 드네요. 시간 되는 대로 코드에 적용시켜보겠습니다. 

       

      + 또 하나, 어제는 f가 '원으로 말았을 때 형을 보존하는' 변환이라고 생각했습니다. 그런데 다시 보니 f는 '문자열을 반대로 읽어서 c와 a를 서로 치환하는 대응'임이 거의 확실해 보입니다. 예를 들어, 서로 대응되는 bbbc와 abbb를 보면, bbbc를 거꾸로 읽어서 c에 a를 대입하면 abbb가 됩니다. 문자열의 길이가 작았기 때문에 '문자열을 거꾸로 읽는' 것을 '원으로 마는' 것으로 오해할 수 있었던 것으로 보입니다. 실제로 f를 통해 연결 상태가 변하지 않는다는 것도 증명할 수 있었습니다. 단순히, R1, R2, R3의 좌변(?)과 우변에 각각 f를 취하면 R3, R2, R1이 되는 것이었네요. 

       

      아직 엄밀하게 증명하지 않았지만, f대응의 존재로부터 '모든 그래프는 대칭적이거나 동일한 연결 상태의 그래프가 쌍으로 존재한다.'는 것을 보일 수 있을 것입니다. 그러면 사이클이 항상 짝수 개(0포함)임을 증명하게 되는 것입니다. 

      좋아요0
    •  
      구머 Lv.5 2020.09.16 21:32

      진짜 큰 도움이 될 것 같습니다. 감사합니다.

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2020.09.16 23:22

      도움이 될 것 같다니 저로서는 다행이군요! 사실 손으로 찾은 것이 아니라, 컴퓨터를 이용한 거라서 조금 찔리긴(?) 합니다 ㅋㅋㅋ

      대응 관계로부터 또 새로운 성질이나 증명을 찾아봅시다! 

      좋아요0
    •  
      파스칼 Lv.5 2020.09.19 19:43

      먼저 이렇게 좋은 정보를 공유해주심에 감사드립니다.

      말씀하신 것처럼 f를 전체 순서를 뒤집고 a와 c를 교환하는 대응으로 정하면 이것을 이용하여 n-그래프의 모든 연결성분이 대칭이거나 쌍으로 존재함을 증명할 수 있습니다.

      (그래프 G가 연결된 몇 개의 성분으로 나눠질 때, 각 성분을 그래프 G의 연결성분이라 부르겠습니다.)

      n-그래프의 임의의 연결성분 A에 대하여, A의 모든 문자열에 대응 f를 적용한 그래프 A'을 생각합니다. A'의 모든 선분, 즉 모든 변환은 A의 변환에서 양쪽의 문자열에 대응 f를 적용한 것이므로 R1,R2,R3중 하나의 변환이 됩니다. R1,R2,R3모두 변환 양쪽의 문자열에 f를 적용하면 다시 셋 중 하나가 되기 때문입니다. 즉 A'의 모든 변환이 R1,R2,R3로 이루어졌으므로 A'는 A이거나, 다른 연결성분 B의 일부분이 됩니다. 그 경우 B의 모든 문자열에 대응 f를 적용한 그래프 B'를 생각하면 f를 두 번 적용한 문자열은 원래대로 돌아가므로 B'이 A를 포함하고, B'와 A가 모두 연결성분이므로 A=B'입니다. 그러므로 n-그래프의 모든 연결성분은 대칭이거나 쌍으로 존재합니다.

      이것으로 만약 R1,R2,R3를 서로 다른 색으로 표시하셨을 때 대칭된 부분에서는 R3,R2,R1으로 바뀌어 존재할 것이라는 것도 알 수 있습니다.

      그리고 그래프를 그린 프로그램은 스크래치인 듯한데.. 혹시 코드를 공유해 주실 수 있을까요?

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2020.09.19 23:47

      파스칼 님이 말씀하신 것이 맞다고 생각이 됩니다. 우연한 발견이었는데 많은 분들이 유용하게 생각해주시니 저도 기분이 정말 좋네요! 

       

      그래프를 그린 방식을 정리해보았습니다. 먼저 각 문자열 간의 연결 상태는 파이썬으로 계산했습니다. 그 다음, 그 정보를 엔트리(스크래치와 비슷한 프로그램입니다.)로 옮겨서 시각화 작업을 한 것입니다. 계산은 엔트리보다 파이썬이 빠르고, 시각화는 제가 파이썬보다 엔트리에 익숙해서 두 프로그램을 같이 사용했습니다.

       

      다만 현재의 코드는 문자열의 길이가 5 이상일 때 그래프를 제대로 그리기 어려운 상태입니다. 몇 가지 문제점이 있어서 아직 올리지 못했습니다. 문제점들을 해결하는 대로 공유하겠습니다! 

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2020.09.25 16:46

      프로그램을 완성해서 올립니다. 첨부파일의 '프로그램 사용 방법.hwp'를 참고하여 실행하면 될 것 같습니다. 파이썬과 엔트리를 모두 사용하여 사용 방법이 조금 복잡한 점 양해 부탁드립니다. 사용 방법에 애매모호한 부분이 있다면 언제든지 말씀해주세요. 

       

      계산 프로그램_최종.py: 

      /resources/comment/2020/09/57cb7e3db96f7801c497645d11256bc4.py

       

      시각화 프로그램_최종.ent: 

      /resources/comment/2020/09/0bbe202fcce24a34484358b83fb79ec2.ent(파일)

      또는 http://naver.me/xMxyKpiz(인터넷상)

       

      프로그램 사용 방법.hwp: 

      /resources/comment/2020/09/25d7ac4d78399d0d6f7cc8b2ee1edab5.hwp

       

      (수정) 계산 프로그램과 시각화 프로그램의 경우, 링크대로 들어간 다음 '우클릭 → 다른 이름으로 저장'을 해줘야 합니다! 

       

      (추가) 그래프의 각 꼭짓점을 2차원 평면 상에 배열한다면, 어떠한 선을 기준으로 대칭인 위치에 있는 꼭짓점이 서로 f-대응 되도록 할 수 있습니다. 그러면 그래프의 전체적인 모양은 대칭이 됩니다. 지난번에 이 사실로부터 사이클이 항상 짝수 개임을 증명할 수 있다고 했는데, 조금 더 생각해보니 아래 그림과 같은 사이클도 있을 수 있네요. 사이클 자체가 대칭이 될 수 없다고 너무 성급하게 생각한 것 같습니다. 

      좋아요0
  •  
    퍼즐-Scratch Lv.4 2020.09.15 10:43

    이미 생각하고 있었던 분들도 많겠지만, 이 문제에서는 '계속 증가하거나 감소하는 양'을 찾는 것도 도움이 될 것 같습니다. 문자열의 개수는 (길이가 고정되었을 때) 유한하기 때문에, 각 문자열에 대응되는 이러한 양을 찾는다면 사실상 증명이 끝납니다. 사이클을 한 번 돌때 그 양이 다시 처음의 값으로 돌아올 수 없기 때문에 모순이 생깁니다. 

     

    R1, R2, R3의 우변(?)을 보면 각각 ab, ac, bc입니다. 상대적으로 a, b, c 순으로 문자열의 앞쪽에 치우쳐 있습니다. 즉, a는 문자열의 앞쪽에 있을 때 가중치를 두고, c는 문자열의 뒤쪽에 있을 때 가중치를 두어서 어떠한 양을 정의한다면, 항상 증가할 가능성이 있습니다. 그런 양을 찾을 수 있을까요? 

    댓글 작성하기 좋아요0 댓글수2
    •  
      수학꿀잼 Lv.2 2020.09.15 12:16

      이는 각 자리의 문자에 관한 일반적인 함수로는 불가능하다는 것이 조금 해보면 느낌이 옵니다. 차수?같은 것에 관계된 단조량이 필요할 것 같습니다

      좋아요0
    •  
      퍼즐-Scratch Lv.4 2020.09.16 23:26

      저도 아직 단조량을 발견하지는 못했습니다! 어쩌면, 수학꿀잼님 말처럼 일반적인 함수로는 불가능할 수도 있을 것 같네요. 이번 문제의 경우는 조금 다른 접근법이 필요한 것일까요 ㅎㅎ

      좋아요0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911