본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[국가수리과학연구소] 국2.5 금칙어 집합에 관한 새 문제(2번째 문제의 추가 문제)
수학동아 2017.05.23

여러분이 열심히 참여해주신 덕분에

가장 효율적인 금칙어 집합에 관한 문제가 거의 풀렸습니다. 

정답으로 제출해주신 메일 또는 댓글도 

현재 문제 출제자인 이석형 연구원이 검토하고 있어요.

그래서 새로운 문제를 추가했으니 열심히 도전해주세요!

blush

(1) 만약 길이 n짜리 단어의 비용이 r에 대해 r^{n}으로 주어진다고 합시다.

어떤 r< 1에 대해서도 비용의 하한이 0이 될까요?

 

(2) 길이 m짜리 단어 l 하나가 금칙어로 지정되었을 때, 길이 n짜리 단어 중 이를 포함하지 않는 것의 개수를 a_{l(n)}이라고 합시다.

m이 고정되어 있을 때, n이 무한대로 갈 때 {(a_{l(n)})}^{\frac{1}{n}}의 극한이 최대/최소가 되는 l은 각각 어떻게 주어질까요?

 

*추가 문제에 나오는 금칙어와 비용, 하한의 정의는 

[국가수리과학연구소 2번 문제] 포스팅을 참고해 주세요!

2번 문제 포스팅 하단에도 추가문제를 덧붙여 놓았습니다. 

 

 

※ 알립니다.

udaque 친구가 소문제 2번을 해결했습니다.

소문제 1번만 풀면 2.5번 문제도 해결이에요!!!

  •  
    수학동아 2017.05.23

    과수원2017.02.16. 10:16

    댓글 작성하기 좋아요0 댓글수1
    •  
      수학동아 2017.05.23

      예쁜치아 건강한치2017.02.16. 16:16

      이제야 놀러왔네요^^ 수학동아님
      항상 행복하시고 하시는 모든일들 잘되시기 바랍니다.
      목요일 오후 마무리 잘 하세용~

      좋아요0
  •  
    수학동아 2017.05.23

    수학자2017.02.20. 22:56

    갑자기 추가 문제에서 문제 난이도가 확 올라간 듯 합니다.

    (1)의 경우는 하한이 0임을 증명하는 데는 아이디어가, 아님을 증명하는 데는 테크닉이 필요할 것 같습니다. 접근 방향을 잡는 것부터가 힘들어서, 저는 (2)를 좀 더 생각해 보았습니다.

    (2)에서는 a_{l(n)}이 이전 m개 항의 선형 결합(일부 경우에 상수항 +c가 있음)으로 나타내어진다는 사실을 알 수 있습니다. 이 때 n이 무한대로 갈 때 극한 {(a_{l(n)})}^{\frac{1}{n}}은 선형점화식의 특성방정식의 근 중 절댓값이 가장 큰 것이 됩니다. 상수항은 무시할 수 있습니다.
    예를 들자면, m=3, l="001"일 때, a_{l(n)}=a_{l(n-1)}+a_{l(n-2)}+1 이라는 식이 성립합니다. 이 때 b(n)=a_{l(n)}+1로 두면 b(n)=b(n-1)+b(n-2)가 되며, 일반항은 Ax_{1}^{n}+Bx_{2}^{n}의 꼴입니다. 여기서 x_{1}, x_{2}x^{2}-x-1=0의 근입니다. 또한 A가 0이 아님을 알 수 있습니다. x_{1}> x_{2}라 하면 x_{1}이 절댓값이 가장 큰 근이고, \frac{a_{l(n)}}{x_{1}^{n}}n이 무한대로 갈 때 어떤 실수로 수렴합니다. 이로부터 {(a_l(n))}^{\frac{1}{n}}의 극한이 x_{1}임을 알 수 있습니다.
    특성방정식의 근 중 실수가 아닌 근이 존재하더라도 상관 없습니다. 그리고 이 근이 1보다 크고, 2보다 작다는 사실을 알 수 있습니다. 즉 이 근은 특성방정식의 최대근입니다.

    그렇다면, 특성방정식의 최대근을 가장 크게/작게 만드는 단어를 찾는 것이 문제의 핵심입니다. 다만 단어가 주어졌을 때 그에 해당하는 특성방정식을 찾는 것이 그렇게 쉬운 일은 아닙니다.

    팁을 드리자면, 001과 110에 대해 a_{l(n)}은 같습니다. 즉, 0으로 시작하는 단어들에 대해서만 생각해도 무방합니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    수학동아 2017.05.23

    수학자2017.02.25. 11:27

    작은 n에 대한 결과는 다음과 같습니다.
    0으로 시작하는 것만 나타냅니다. 1로 시작하는 경우는 그 반전을 생각하면 됩니다.
    n=2: 최대:00(1.618) 최소:01(1)
    n=3: 최대:000(1.839) 최소:001,011(1.618)
    n=4: 최대:0000(1.928) 최소:0001,0011,0111(1.839)
    n=5: 최대:00000(1.966) 최소:00001,00011,00101,00111,01111(1.928)

    댓글 작성하기 좋아요0 댓글수0
  •  
    수학동아 2017.05.23

    거대 수학2017.02.27. 21:04

    댓글 작성하기 좋아요0 댓글수0
  •  
    수학동아 2017.05.23

    수돌이2017.03.01. 10:14

    폴리매스 3월문제 빨리 올려주세요~ ^^

    댓글 작성하기 좋아요0 댓글수0
  •  
    미래탐정 Lv.1 2017.09.23

    <묻힌 문제 살리기 프로젝트 2>

    댓글 작성하기 좋아요0 댓글수0
  •  
    수학자 Lv.1 2018.01.28

    오랜만에 댓글 남기네요. 위의 (2)에 대한 댓글에 대해 좀 더 추가해서 이야기해보겠습니다.

    일단 일부 경우에 상수항이 있을 수 있다고는 썼는데, 이 상수항을 없애는 방법이 일반적으로 존재합니다. l="001"인 경우의 점화식에서도, 1=a_{l(n)} - a_{l(n-1)} - a_{l(n-2)} = a_{l(n-1)} - a_{l(n-2)} - a_{l(n-3)}으로부터 상수항이 없는 점화식을 만들 수 있습니다.

    다음으로, 이러한 점화식을 직접 찾는 방법입니다. 먼저, 길이 m인 단어 l에 대해, f(k,n), g(k,n)을 다음과 같이 정의합니다.

    f(k,n) : 길이 n짜리 단어 중 l을 포함하지 않으면서, l의 앞 k자리 부분으로 시작하는 것의 개수

    g(k,n) : 길이 n짜리 단어 중 l을 포함하지 않으면서, l의 앞 k-1자리 부분으로 시작하고 k번째가 l의 k번째와 반대인 것의 개수

    그리고 이 f(k,n), g(k,n)들에 대한 식을 세워주고, 이를 이용하여 f(0,n) = a_{l(n)}을 f(0,n-t)들에 대한 식으로 나타내면 됩니다. 이렇게만 설명하면 부족하니 예시를 봅시다.

    m=3, l="001"인 경우, 먼저 f(0,n)은, 0으로 시작하는 경우의 수가 f(1,n), 1로 시작하는 경우의 수가 g(1,n)이므로 f(0,n)=f(1,n) + g(1,n)입니다.

    다음으로 f(1,n)은 0으로 시작하는 것들의 개수인데, 이는 00으로 시작하는 경우의 수 f(2,n)와 01로 시작하는 경우의 수 g(2,n)의 합 f(1,n)=f(2,n) + g(2,n)입니다.

    g(1,n)은, 1로 시작하는 것의 개수인데, 1로 시작한다면 나머지 n-1짜리 단어에서 조건을 만족하기만 하면 됩니다. 따라서 g(1,n)=f(0,n-1)입니다.

    f(2,n)은 00으로 시작하는 개수인데, 001로 시작하는 경우의 수는 명백히 0이므로, 000으로 시작하는 개수와 같습니다. f(2,n)=g(3,n)

    g(2,n)은 위 g(1,n)과 비슷하게 하면 g(2,n)=f(0,n-2)입니다. 마지막으로 g(3,n)은 000으로 시작하는 경우의 수인데 앞의 0을 제외한 n-1짜리 단어가 f(2,n-1)과 정확히 같은 상황임을 알 수 있습니다. g(3,n)=f(2,n-1)

    종합하면 \small f(0,n)=f(1,n)+g(1,n)=f(2,n)+g(2,n)+g(1,n)=g(3,n)+g(2,n)+g(1,n)입니다. 또한, f(0,n)=f(1,n) + g(1,n)와 f(1,n)=f(2,n) + g(2,n)로부터 \small f(2,n)=f(1,n)-g(2,n)=f(0,n)-g(1,n)-g(2,n)입니다. 이 식들을 이용하면 \small g(1,n)=f(0,n-1)\small g(2,n)=f(0,n-2)\tiny g(3,n)=f(2,n-1)=f(0,n-1)-g(1,n-1)-g(2,n-1)=f(0,n-1)-f(0,n-2)-f(0,n-3)이 나오고, 최종적으로 \small f(0,n)=f(0,n-1)+f(0,n-2)+f(0,n-1)-f(0,n-2)-f(0,n-3)이라는, 원하는 형태의 점화식이 나옵니다.

    일반적인 단어에 대해서 이런 식으로 점화식을 세우는 것이 가능합니다. 다만, \small m=5 정도에서부터 까다로운 경우들이 많아집니다. \small f(0,n) 꼴이 아닌 다른 형태의 식들이 재귀적으로 나타날 때 이를 어떻게 소거할 수 있는지 등의 복잡한 문제들이 있습니다. 또한, 점화식을 정확하게 세우지 않더라도, 세우는 과정에서 부등식을 이용하여 문제를 풀 수도 있겠다는 생각이 듭니다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      구머 Lv.4 2018.01.28

      오랜만이에요 수학자님~ 폴리매스를 중간에 들어와서 이 문제를 아직 생각해보지 않았는데 혹시 풀어볼만한 난이돈가요?

      좋아요0
    •  
      수학자 Lv.1 2018.01.28

      (1)의 경우는 잘 모르겠지만, (2)에서 최대를 구하는 부분은 간단하게 해결이 될 수도 있지 않을까 싶네요.

      좋아요0
  •  
    수학자 Lv.1 2018.01.29

    단어가 주어졌을 때 점화식을 찾는 일반적인 방법을 찾아냈고, C++을 이용하여 구현하였습니다.

    소스 코드 : /resources/comment/2018/01/2da4dea003b149694fe5b0fa8faaed84.cpp

    실행 파일 : /resources/comment/2018/01/678ac7498fa53dcf5fd336aa55b8c92e.exe

    단어를(ex. 00101) 입력하면 점화식의 각 항(n, n-1, n-2, n-3,...)의 계수를 출력합니다.(ex. 0 2 0 0 0 -1)

    m=5 정도에서부터 최소인 단어의 규칙을 정형화하기 어려웠는데, 길이가 길수록 그 다양성이 큰 듯합니다.

    댓글 작성하기 좋아요0 댓글수3
    •  
      누군가 Lv.1 2018.01.29

      코딩에 대해 잘은 모르지만 실행파일을 실행하면 Vcruntime140D.dll,MSVCP140D.dll,ucrtbased.dll 등등 여러파일이 없어 실행이 불가능 하다고 하는데 찾아보니 배포용이아닌 디버깅용이라 그런 거라고 나옵니다. 배포용도 visualstudio 재배포패키지가 필요하지만 디버깅용을 실행하려면 visualstudio 자체가 필요하니 배포용으로 실행파일을 올려주시면 좀 더 많은 사람이 실행을 할 수 있을 것 같습니다.

      결론만 얘기하면 그냥 다운로드해서 실행하면 실행이 안됩니다.

      좋아요0
    •  
      B.C.I.수학장 Lv.5 2018.01.29

      전 되긴 하는데 주석이 영어로 되어 있어서 어떤 부분이 어떤 걸 작성한 건지 잘 모르겠네요... 설명 좀 부탁드립니다

      좋아요0
    •  
      수학자 Lv.1 2018.01.29

      exe파일은 Visual studio로 컴파일한 파일이라 그런 듯 합니다. 소스 코드가 있으니 소스 코드를 적당한 컴파일러에서 돌려보면 될 것 같습니다.

      점화식에 대한 기본적인 설명이 필요하겠네요.

      먼저, 위의 f,g 정의에 대해, \small f(k,n)=f(k+1,n)+g(k+1,n)입니다.(ex. 0010으로 시작하는 것의 개수는 (00100으로)+(00101로)와 같습니다.) \small n이 \small k에 가까울 때는 약간 애매해지지만, \small n이 충분히 클 때에만 점화식이 성립하면 되기 때문에 큰 문제는 없습니다.

      다음으로 \small g(k,n)은, (단어 \small l의 앞 \small k-1자리 + 단어 \small l의 \small k번째의 반대)로 이루어진 새로운 길이 \small k의 단어에 대해, 이 단어의 뒤 \small t자리가 \small l의 앞 \small t자리와 같게 되는 최대의 \small t에 대해 \small g(k,n)=f(t,n-k+t)입니다. 위의 001에 대한 예시에서 예를 들자면, \small g(3,n)은, 000의 뒤 \small t자리가 001의 앞 \small t자리가 되는 최대의 \small t는 2입니다. 따라서 \small g(3,n)=f(2,n-3+2)입니다. 이것이 성립하는 이유는, 조건을 만족하는 최대의 \small t를 잡았을 때 그 앞의 나머지 부분은 단어 \small l의 존재에 관여하지 않기 때문입니다.

      이 식들을 이용해서 \small f(0,n)을 \small f(0,n-t)들로 나타내기 위해서는, 다른 f,g들을 차례대로 \small f(0,n-t)로 나타내야 합니다. 그 순서는 다음과 같습니다.

      \small f(0,n) \rightarrow g(1,n) \rightarrow f(1,n) \rightarrow g(2,n) \rightarrow \cdots

      \small f(0,n) = f(0,n)에서 시작하며, \small g(k,n)은 이전에 나타낸 \small f로부터 나타낼 수 있습니다. \small f(k,n) = f(k-1,n) - g(k,n)으로부터 \small f(k,n)을 구해낼 수 있습니다. 이렇게 나타난 식들로부터 \small f(0,n) = g(1,n) + g(2,n) + \cdots + g(m,n)에 대입하여 다시 \small f(0,n)을 나타내주면 끝입니다.

      소스 코드는 이를 구현한 것이며, rec라는 새로운 sturct를 정의하였습니다. rec는 f나 g를 \small f(0,n-t)들로 나타낸 결과를 저장하는 자료형이라고 생각하면 됩니다. 이들을 더하고 빼는 것이 각각 add, sub 함수이고, push는 f(2,n)에 대한 식을 f(2,n-t)에 대한 식으로 바꿔주는 등의 일을 합니다.

       

      좋아요0
  •  
    출제자(국) Lv.1 2019.01.31

    수열 a_i를 분석할 때 아래 알고리즘이 도움이 될 수 있을 거 같습니다

    https://bowbowbow.tistory.com/6

    KMP algorithm이라고 하는 것인데요, 어떤 문장에 특정 단어가 존재하는지, 존재한다면 어디에 존재하는지를 빠르게 계산하는 알고리즘입니다. 이 알고리즘에서 쓰이는 상태 변화를 수식으로 표현하면 수학자님이 말씀하신 점화식이 나오는 것 같습니다.

    이 자료도 도움이 되는 것 같습니다. 특정 단어가 나올 확률을 계산하는 방법입니다. 아마 수학자님의 방법과 같은데, 특성방정식에 대한 얘기가 조금 더 있는 것 같기도 합니다.

    https://udaqueness.blog/2019/01/21/%EB%9E%9C%EB%8D%A4-%EC%9B%8C%EB%93%9C%EC%97%90%EC%84%9C-%ED%8A%B9%EC%A0%95-%EC%9B%8C%EB%93%9C%EA%B0%80-%EB%93%B1%EC%9E%A5%ED%95%A0-%ED%99%95%EB%A5%A0/

     

    댓글 작성하기 좋아요0 댓글수0
  •  
    udaque Lv.1 2019.02.03

    안녕하세요. 윗분께서 블로그 글을 링크해주셔서 이런 프로젝트가 있다는 것을 알게 되었습니다. (2)번 문제의 간략한 풀이 스케치를 블로그에 올렸습니다.

    랜덤 워드에서 특정 워드가 등장할 확률

    랜덤 워드에서 특정 워드가 등장할 확률 (2)

    댓글 작성하기 좋아요0 댓글수1
    •  
      김우현 기자 Lv.4 2019.02.19

      udaque 친구의 풀이가 최종 정답으로 확인됐습니다. '부분해결' 딱지를 붙이도록 할게요!laugh

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

  • ☎문의 02-6749-3911