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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대29. 수열과 부분수

2019.04.30

같이 풀어볼까?

네이버밴드 구글플러스

각 항이 0 또는 1로 이뤄진 수열 a_{1}, a_{2}, \cdots을 생각하자. 연속한 자연수 i, i+1, \cdots , i+k-1이 있을 때, 이들을 일렬로 붙여 나열한 수 a_{i}a_{i+1}\cdots a_{i+k-1}을 수열 a_{n}k-연속수라고 부르자.


자연수 k에 대해, 집합 {a_{i}a_{i+1}a_{i+2}\cdots a_{i+k-1} : i는 자연수}은 k-연속수들을 모아놓은 집합이다. 이 집합의 크기를 N_{k} 라고 하자.

 

예를 들어, n이 짝수일 때 a_{n}=1이고 홀수일 때 a_{n}=0인 수열이 있으면, 3-연속수는 010(=10), 101뿐이므로 N_{3}=2이다. 일반적으로 임의의 자연수 k에 대해서 k-연속수는 0으로 끝나거나 1로 끝나면 나머지 자릿수가 모두 결정되므로 N_{k}=2임을 확인할 수 있다.


주어진 수열 a_{n}에 대해 N_{k}가 만족하는 세 가지 성질은 다음과 같다.

1. 항상 N_{1}=2이다.

2. 어떤 수열 a_{n}에 대해서도 k-연속수의 개수는 많아야 2^{k}이므로, N_{k}\leq 2^{k}이다.

3. 임의의 자연수 k에 대해서, k-연속수는 어떤 k+1-연속수의 첫 숫자를 제외하면 얻을 수 있으므로, N_{k}\leq N_{k+1}이다.

 

문제 1 주어진 자연수 k에 대해, N_{k}=2^{k}가 되게 하는 수열 a_{n}(n=1, 2, \cdots )을 찾아라.

 

문제 2 어떤 자연수 k에 대해, N_{k}< k라 하자. 이때 모든 자연수 m에 대해, N_{m}=M을 만족하는 자연수 M이 존재함을 보여라.

 

문제 3 주어진 자연수 k에 대해, N_{k}=k+1이 되게 하는 수열 a_{n}(n=1, 2, \cdots )을 찾아라.

 

문제 4 주어진 자연수 k와 1보다 큰 자연수 c에 대해, N_{k}=k+c를 만족하는 수열 a_{n}(n=1, 2, \cdots )이 존재할까?

 

문제 5 다음 두 조건을 만족하는 수열 a_{n}을 하나 생각하자.

         (a) 모든 자연수 k에 대해, N_{k}=k+1이다.

         (b) 모든 자연수 n에 대해, a_{n}=1이면 a_{n+1}\neq 1이다.

             이때, 수열 a_{n}에서 k-연속수로 나올 수 있는 수의 1과 1사이에 있는 숫자열이 단 2개 뿐임을 증명하라.

 

보너스 문제 소문제 5번을 만족하는 수열은 다음을 만족함을 보여라.

                임의의 길이가 같은 두 연속수 a, b에 대해 \left | (a의 1의 갯수)-(b의 1의 갯수) \left |\leq 1이다.

 

 

 

 

☆★ 알립니다 ★☆

29번 문제 최종 해결

tommy 친구: 1, 3번 / 구머 친구: 2, 4번 / 수돌이 친구: 5번

 

소문제 5번의 문제를 일부 수정

10의 거듭제곱꼴의 수(10^{m}형태의 수)는 단 2개 → 1과 1사이에 있는 숫자열은 단 2개

 

보너스 문제 추가

문제 해결과는 별개입니다!

 

댓글 57

  • math 2019.05.01 09:53:14

    문제1. 랜덤으로 각 항마다 1또는 0을 배치하는 난수 수열이 아닐까 조심스럽게 생각합니다.

    좋아요0 댓글수2
    • tommy 2019.05.03 23:45:13

      제 생각엔 이렇게 하면 1번 문제의 답으로 충분할 것 같습니다. 0부터 2^k-1까지의 정수를 이진수로 바꿔 펼쳐놓고, 그 뒤는 무작위로 하는 겁니다.

      예를 들어, k=3이라면, 0~7을 이진수로 바꾼 뒤

      000, 001, 010, 011, 100, 101, 110, 111

      펼칩니다.

      0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1

      그리고 그 뒤는 어떤 수열이 와도 상관없습니다. 증명은 간단합니다. 우선 k-연속수로 가능한 모든 조합을 한 번씩 만들었으니 N_k\geq 2^k이 되고, 또한 N_k\leq 2^k이므로 N_k=2^k입니다.

      좋아요0
    • 김우현 기자 2019.05.19 15:26:37

      [최종 검토 완료] #tommy #정답

      tommy 친구의 소문제 1번 풀이가 최종 정답으로 확인됐습니다. 축하해요! yes

      좋아요0
  • math 2019.05.01 10:11:34

    문제2. a_{n}의 규칙이 n을 k-1로 나눴을 때, 같은 나머지를 가진 n번째 항들의 1 또는 0의 여부는 같다고 설정을 하면, 오른쪽부터 차례대로 갈때, 맨 첫번째 배열이 k번째 배열과 동일하게 되므로, 나올 수 있는 최대의 배열의 수는 k-1개가 되므로 N_{k}<k라는 조건을 만족하게 되고, 이때, 자연수 m이 어떤 수이든, 맨 첫번째 배열과 k번째 배열이 동일하게 될 수 밖에 없으므로 N_{m}=k-1이 되어서 k-1이라는 동일한 자연수 M값을 같게 됩니다.

    좋아요0 댓글수1
    • 리프 2019.05.15 23:53:13

      math님의 풀이는 'N_k< k를 만족하는 어떤 수열이 존재해서 이 때 M의 값이 일정하다'를 보인 것 같네요. 그런데 문제는 N_k< k를 만족하는 모든 수열에 대해 M의 값이 일정함을 보여야 하는 것이 아닌가요?

      제 생각에는 math님의 풀이에서 N_k< k를 만족하는 모든 수열에 대해서 주기를 가진다는 것만 추가로 증명하면 될 것 같습니다.

      좋아요0
  • tommy 2019.05.04 00:11:40

    일단 문제 3번의 경우에는 간단하네요. 0 k개, 1 1개를 반복하면 됩니다. 예를 들어 k=5라면

    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, ...

    과 같이 됩니다. 4번의 경우에도 비슷할 것 같은데, 일단 만약 c\leq k이면 위와 동일한 방법으로 가능합니다.(0 k개, 1 c개 반복) 그러나 c>k부터는 이 방식이 먹히지 않네요. 하지만 제 생각에는 수열이 k+c를 주기로 가진다면, 한 주기 안의 k-연속수들이 서로 겹치게만 하지 않으면 간단히 수열을 만들어낼 수 있을 것 같습니다.(사실 주기 수열을 이용한다면 k+c라는 식에 관련 없이 어떤 k, n에 대해서도 N_k=n이 되는 수열을 만들어낼 수 있을 듯합니다.)

    좋아요0 댓글수7
    • 파스칼 2019.05.08 21:44:50

      N_{k}\leq 2^{k} 이므로 c\leq 2^{^{k}}-k만 가능합니다. 이중 c\leq 2k-2 일경우 0 k개, 1 k개, 0 1개, 1 c-k+1개를 반복하면 됩니다.

      좋아요1
    • 리프 2019.05.14 20:41:22

      문제 3번에서 1을 반복하지 않아도 문제 조건을 만족하네요. 0 k개 1 1개를 반복할 필요는 없을 것 같습니다.

      좋아요0
    • 파스칼 2019.05.14 23:02:22

      1을 반복하지 않으면 겹치는 경우가 생겨서 안됩니다.

      좋아요0
    • 리프 2019.05.15 22:24:36

      겹치는 경우가 정확히 무엇인지 설명해주실수 있나요? 계속 생각해도 잘 모르겠네요

      좋아요0
    • tommy 2019.05.15 22:42:41

      아, 굳이 반복할 필요는 없네요ㅋㅋ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...처럼 해도 괜찮겠군요! ㅎㅎ

      다만 주기를 띠게 하는 기법은 다른 N_k 값을 원할 때도 유용할 것 같네요ㅎㅎ

      좋아요0
    • 리프 2019.05.15 23:45:56

      제 생각에는 주기를 가질 경우 어차피 이미 앞에서 나온 k-연속수가 나오기 때문에 주기를 가지는 것은 N_k의 값에 크게 영향을 주지는 않을 것 같네요.

      좋아요0
    • 김우현 기자 2019.05.19 15:26:55

      [최종 검토 완료] #tommy #정답

      tommy 친구의 소문제 3번 풀이가 최종 정답으로 확인됐습니다. 축하해요! yes

      좋아요0
  • Simon 2019.05.05 12:54:20

    N_1은 k연속수로 가능한 경우가 0과 1인데 0은 자연수가 아니므로 N_1=1입니다. 이를 이용하면 문제 1과 2가 모두 모순이 됩니다.

     

    좋아요0 댓글수3
    • tommy 2019.05.05 15:24:11

      0이 자연수가 아니라는 사실이 왜 N_1=1이라는 명제를 증명하나요?

      좋아요0
    • Simon 2019.05.06 15:53:27

      k-연속수로 가능한 수가 1과 0인데 0이 빠지면 1만 남아서 1개가 되잖아요 N_1의 정의가 k-연속수의 개수인데 그렇게 되면 사실 1이 있는경우는 1, 없는 경우는 0이 되겠네요. 다만, 문제 조건처럼 2가 될 수 있는 경우는 없다는 뜻이지요.

      좋아요0
    • tommy 2019.05.06 23:00:17

      문제에 k-연속수가 자연수여야 한다는 조건은 없습니다. 즉, 0이 자연수가 아니라고 해서 0이 k-연속수가 될 수 없지는 않습니다.

      좋아요0
  • 리프 2019.05.14 16:26:20

    4번 풀이입니다. 풀이 검토해주시고 틀린 부분이 있다면 지적해주시길 바랍니다.

    좋아요0 댓글수7
    • 김우현 기자 2019.05.14 18:41:55

      좋아요0
    • 리프 2019.05.14 20:38:35

      분명 똑같이 했는데 왜 url로 뜨는거죠? 원래 그런가요?

      좋아요0
    • 김우현 기자 2019.05.15 08:20:47

      혹시 1번에서 사진 첨부 아이콘이 아닌 파일 첨부 아이콘을 누르지 않았나요??cheeky

       

      좋아요0
    • 리프 2019.05.15 23:40:15

      아 그런 것 같네요. 알려주셔서 감사합니다.

      좋아요0
    • 리프 2019.06.11 19:29:00

      풀이 검토 언제쯤 되나요?

       

      (+제 풀이 추가 설명입니다.)

      예시로 한번 N_5=20인 수열을 만들어보겠습니다.

      20=(5+1)+(1*4+1*3+1*2+1*1)+(2*2)로 나타낼 수 있습니다.(첫번째 괄호는 5-연속수 중 1이 0또는 1개인 수의 개수, 두번째는 1이 2개인 수의 개수, 세번째는 1이 3개인 수의 개수로 생각할 수 있습니다.)

      여기서 다음과 같은 수열을 얻을 수 있습니다.

      00000/10000/00000/11000/00000/10100/00000/10010/00000/10001/00000/11010/00000/10110/00000(여기서부턴 계속 0, 편의상 숫자 5개씩 구간을 나눴습니다.)

      2번째 구간에서는 1이 0개또는 1개인 5-연속수를 모두 얻을 수 있고, 4~10번째 구간에서는 1이 2개인 5-연속수를 모두 얻을 수 있습니다.

      12번째 구간과 14번째 구간은 1이 3개인 5-연속수를 각각 2개씩 얻을 수 있습니다.

      이러면 1이 0개, 1개, 2개인 5-연속수가 모두 나오고(총 16개) 1이 3개인 5-연속수가 4개 나오면서 조건을 만족합니다.

       

      이러한 방식으로 조건을 만족하는 수열을 항상 만들 수 있다는 것은 제 풀이에서 증명했습니다.

      좋아요0
    • 김우현 기자 2019.06.12 09:30:21

      현재 멘토님이 1차 검토 중!!

      좋아요0
    • 김우현 기자 2019.06.16 12:32:43

      멘토 확인 결과 잘 풀었다는 의견을 주셨어요!

      교수님께 최종 검토를 요청하겠습니다.smiley

      좋아요0
  • 모두다같이 2019.05.25 16:00:35

    일반적으로 임의의 자연수k에 대해서 k연속수는 0으로 끝나거나 1로 끝나면 나머지 자릿수가 결정되므로 Nk = 2 임을 확인할 수 있다.

    이 대목이 잘 이해안되요..

    좋아요0 댓글수0
  • 모두다같이 2019.05.25 16:04:51

    문제2에서

    1010101010101...

    0 ,1 하나씩 자꾸 반복해 만든 무한수열을 놓고

    Nk를 생각해보면 N1일때나 N2일때나...Nk(k는 다른 모든 자연수)일때나 항상 값이 2 이지 않나요?

    그럼 k가 2보다 큰 수라면 위 수열과 모든 자연수 m에 대하여 Nm = M을 만족하는 자연수M이 바로 2인 것 같습니다..

    좋아요0 댓글수1
    • 리프 2019.05.25 20:13:59

      문제의 조건을 만족하는 경우 1가지에서 성립한다고 해서 모든 경우에서 다 성립하는 것은 아닙니다.

      특수한 경우에서 성립한다는 것을 증명하는 것이 아니라 모든 경우에서 성립한다는 것을 증명해야 합니다.

      좋아요0
  • 모두다같이 2019.05.25 16:17:29

    문제4에서

    N3 = 5 를 만족하는 수열이 있을까 생각했어요.

    k = 3 , c = 2 이니까 문제의 Nk = k + c ( k는 주어진 자연수, c는 1보다 큰 자연수) 형식을 만족해요

    01100111111... (뒤로는 1만 쭉 있어요) 를 놓고보면..

    N3의 원소는 011, 110, 100, 001, 111 이에요.

    N3 = 5를 보이는 수열을 찾았으니

    문제4를 풀었다고 봐도 될까요?

     

    좋아요0 댓글수0
  • 모두다같이 2019.05.25 16:26:25

    문제5의 b에서

    1~n까지 an = 1 이면

    an+1 은 0이란걸 뜻하는 건가요..?

    좋아요0 댓글수0
  • 모두다같이 2019.05.26 17:35:22

    문제2에서

    모든 자연수m에서 Nm = M 인 M을 찾고 있습니다.

    m이 1 일 때 Nm = 2 이니 

    M은 2입니다.

    모든 자연수 m 에 대해 Nm = 2 인 수열을 찾아야할것 같아요.

    좋아요0 댓글수0
  • Undefined 2019.05.31 19:32:42

    N_1 =1인 경우도 있지 않나요?

    \forall i \in \mathbb{N},a_i=k(k는 상수)

    좋아요0 댓글수0
  • 수학잘하고싶다 2019.06.01 20:59:28

    문제 2번이 잘못된거같아요

     

    001001001001001001001001.... 이라는 수열을 보면 N4=3인데 N1=2 에요. m이 모든 자연수가 아니라 1을 제외한 모든 자연수 라고 해야지 맞는 문제인거같아요

    좋아요0 댓글수1
    • 김우현 기자 2019.06.12 09:28:40

      멘토님 검토 결과 오류가 있는 것 같아요!

      출제자의 최종 검토가 남았지만, 우선 충분히 큰 m에 대해서 M을 구해주세요!!crying

      좋아요0
  • 수학잘하고싶다 2019.06.01 21:12:35

    문제 2번 자체가 좀 잘못된거같아요 

    0000100000000000.... 같은 수열을 보면

    N8=6 인데 N3=4 에요

    좋아요0 댓글수0
  • 수학잘하고싶다 2019.06.04 20:17:04

    5번 여기까지 했는데 이 상태에서 제외 가능한 경우의 수 하나하나 다 해보면서 모순을 찾아내면 뭔가 될것같아요

    좋아요1 댓글수0
  • 구머 2019.06.10 00:59:01

    4번 생각보다 엄청 간단해요 ㅇㅅㅇ 그냥 1111..을 일단 갖다놓고 N_k가 k+c가 될때까지 수열의 앞쪽에 계속 수를 추가해주면 되용.

    좋아요0 댓글수3
    • 구머 2019.06.10 01:04:12

      예를 들어 N_6=13이 되고 싶게 하고 싶으면,

      1111111..

      01111111..

      001111111..

      0001111111..

      00001111111..

      000001111111..

      0000001111111..

      10000001111111..

      010000001111111..

      (쓰기 귀찮.. 어쨋든 이런 어이디어로..)

       

      좋아요0
    • 리프 2019.06.22 08:34:10

      이렇게 간단한 문제였다니 약간 충격적이네요. (저는 왜 이렇게 복잡하게 푼 걸까요 ㅋㅋ)

      좋아요0
    • 김우현 기자 2019.07.13 14:40:50

      [최종 검토 완료] #구머 #정답

      주어진 성질을 만족하는 수열을 잘 발견했네요! 교수님의 코멘트를 인용할테니 또다른 수열도 찾아보세요!

       

      "두 종류의 수열이 나올 수 있어요. 구머 친구처럼 어느 순간부터 a_{n}이 모두 같은 수열 그리고 그렇지 않은 수열이에요. 첫 번째 수열은 구머 친구의 풀이처럼 관찰해서 확인할 수 있고, 두 번째 수열은 좀 더 생각을 해야하죠. 참고로 두 번째 수열이 소문제 5번의 힌트가 됩니다!"

      좋아요0
  • 구머 2019.06.20 00:34:54

    2번을 해결했어요☆☆ 이번주 금요일에 답을 올리겠습니다><

    좋아요1 댓글수0
  • 구머 2019.06.21 20:44:34

    편의상 b_i = a_ia_{i+1}....a_{i+k-1}_{\left ( {2} \right )}이라고 정의하자. 이때, Nk<k이므로 비둘기집의 원리에 의해 b_1,~b_2~...~b_{k+1} 중 같은 것이 존재하므로, 같은 것들의 쌍들 중 가장 인접한 것을 b_x,~b_y라고 하자.(WLOG x<y) 또, d=y-x라고 하자.

    성질 1: [x,x+k-1] 범위 내의 임의의 정수 i에 대해, a_i=a_{i+d}가 성립함.

    성질 1-pf) bx=by이므로 자명.

    성질 2: 수열 a_xa_{x+1}...a_{x+d-1}은 같은 n개의 수열로 나눠지지 않는다.(예를 들어, 수열 110110110은 110 3개로 나눠지지만, 110111111은 나눠지지 않는다)

    성질 2-pf) (귀류법) 만약 저렇게 나눠진다면, b_x=b_{x+\frac{d}{n}}이 성립하게 되고, 이는 bx와 by가 같은 수열들의 순서쌍들 중 가장 인접한 것이라는 가정에 모순이다.

     

    이 성질들을 이용해, x이상의 임의의 정수 i에 대해 a_i=a_{i+d}가 성립함을 귀납적으로 증명하자.

    (1) i=x+k일 때 성질이 성립함.

    (1)-pf) 만약 a_{x+k}\neq a_{x+k+d}이면, 임의의 정수 x\leq n<m\leq x+k에 대해 b_n != b_m이 성립함(by 성질2, 필요시 부연설명 하겠음) 따라서 N_k>k가 되어 모순.

    (2) x<= i < p 일때 성립한다 가정. 이때 (1)과 마찬가지 방법으로 i=p일때도 성립함.

    (1),(2)에 의해 x이상의 임의의 정수 i에 대해 a_i=a_{i+d}가 성립함이 증명되었고, 따라서 x이후로 수열은 주기를 가진다. 따라서 충분히 큰 m에 대해 N_m이 일정함

    좋아요0 댓글수9
    • 리프 2019.06.21 23:52:09

      b_n !=b_m에서 !는 오타인가요? 아니면 같지 않다는 뜻인가요?

      좋아요0
    • 구머 2019.06.22 10:19:42

      ㄱㅏㅌㅈㅣㅇㅏㄴㅎㄷㅏ

      좋아요0
    • cube120 2019.06.22 20:43:31

      죄송한데, 별거 아니지만 d=y-x가 되어야 하지 않나 생각합니다...

      좋아요0
    • 구머 2019.06.22 21:19:38

      아앗..쓰다보니 헷갈렸네요 수정했슴니다

      좋아요0
    • 수학잘하고싶다 2019.06.23 17:41:04

      혹시 성질2 부분에 a_d-1 가 a_x+d-1 인가요?

      좋아요0
    • 구머 2019.06.23 19:18:55

      에구야 왤캐 정신이 없냥ㅜㅜ수정했어요 지적 감사합니다

      좋아요0
    • 김우현 기자 2019.06.24 09:25:33

      yesyesyes

      멘토님이 1차 검토중!!

      좋아요0
    • 김우현 기자 2019.07.02 16:49:03

      1차 검토 완료!

      교수님께 최종 검토를 요청할게요~laugh

      좋아요0
    • 김우현 기자 2019.07.13 14:38:01

      [최종 검토 완료] #구머 #정답

      주어진 성질을 만족하는 수열을 잘 찾아줬어요! 축하합니다!

      좋아요0
  • 수돌이 2019.06.22 02:49:42

    오랜만에 해결 딱지가 붙겠네요!

    총정리 하도록 하겠습니다.

    부분문제 1,3: tommy 친구가 해결!

     

    부분문제 2: 구머 친구가 해결한거 같아요 빠른 확인 부탁드립니다.

    (2019.06.21 20:44:34의 댓글 참고)

     

    부분문제 4: 리프 친구와 구머 친구가 해결한거 같아요

    단, c는 2^k-k이하여야 합니다. k+c\leq 2^k이어야 하니까!

    요약하자면, 1이 반복되는 수열 111111111....의 앞에다가 tommy 친구의 1번 풀이에서 쓰인 "k-연속수로 가능한 모든 경우를 나열한 수열"을 뒤에서부터 붙이기 시작할 겁니다. 예를 들어, k=2라면, "2-연속수로 가능한 모든 경우를 나열한 수열"은 11100100이므로, 1111...., 01111...., 001111....,1001111...., ..., 111001001111....이렇게 되는거죠! 붙이기 전에는 수열에 1밖에 없으므로 N_k=1입니다. 모두 붙인 뒤에는 N_k=2^k가 되겠죠.

    그런데 숫자를 하나 붙일 때마다 새로운 k-연속수는 최대 하나 등장하므로, N_k은 최대 1 증가합니다. 즉, 1\leq a\leq 2^k인 임의의 a에 대해, N_k=a가 되는 시점에서 붙이기를 멈출 수 있습니다.

     

    "부분문제 5"

    일단 결론부터 말하면 문제의 서술이 잘못되었습니다. 반례가 존재해요.

    그러니까 수열에 1000이 포함되면 k-연속수로 나올 수 있는 수 중 10의 거듭제곱꼴의 수가 10,100,1000로 세 가지가 있게 되겠죠.

    지금부터 반례를 제시하도록 하겠습니다.

    1000를 포함하면서 a,b를 모두 만족하는 수열을 잡을 것입니다.

    수열 S_0=1T_0=0으로 잡습니다. 그리고 귀납적으로 S_{i+1}=S_iT_iT_iT_iT_{i+1}=S_iT_iT_i라고 정의합니다.

    직접 계산해 보면, S_1=1000, T_1=100이고, S_2=1000100100100, T_2=1000100100 이렇게 되겠죠. S_{i+1}은 S_{i}뒤로 새로운 항이 붙으면서 계속 길어진다는 것을 확인할 수 있습니다. 우리가 원하는 수열은 이를 계속 반복해서 만드는 수열 S_{\inf}가 될 것입니다. 이 수열은 모든 자연수 k에 대해 N_k=k+1를 만족합니다.

    사실 모든 자연수 k에 대해 N_k=k+1를 만족하는 수열은 이런 방식으로밖에 만들 수 없어요. 이런 발상이 어디서 나왔냐면 k가 1 증가하면, N_k도 1 증가한다는 점에서 착안한 것입니다. k=i에서 k=i+1이 될 때, (i+1)-연속수들은 각각 어떤 i-연속수의 맨 뒤에 0 또는 1이 추가됩니다. 그래서 N_{i+1}=N_i+1이므로, 가능한 i-연속수들 중 정확히 하나만 뒤에 0과 1이 모두 붙을 수 있고, 나머지는 모두 뒤에 붙을 숫자들이 결정되어야 합니다.

     

    "S_{\inf}가 모든 자연수 k에 대해 N_k=k+1를 만족한다"에 대한 증명

    N_1=2를 만족하므로, 모든 자연수 i에 대해 N_{i+1}=N_i+1가 성립함을 보이겠습니다. 즉, 가능한 i-연속수들 중 정확히 하나만 뒤에 0과 1이 모두 붙을 수 있다는 걸 증명하면 충분합니다. 이게 서술하기 까다로워서 논리적 흐름만 설명하도록 하겠습니다.

    i=2까지는 i-연속수들 중에 1을 포함하고 있으면 1 뒤에는 무조건 2개 이상의 0이 이어지므로, 뒤에 붙을 숫자는 0으로 한정됩니다. 따라서 (00)과 같이 0만으로 이루어진 i-연속수일 때만, 뒤에 0이 붙을 수도 (000), 1이 붙을 수도 있습니다.(001)

    뒤에 0과 1이 모두 붙을 수 있는 i-연속수를 앞으로 좋은 연속수라고 하겠습니다.

    i=3일 때는, 3-연속수 중에 000의 경우, 0은 최대 3개까지 연속하고 있으므로, 뒤에 붙은 숫자는 1으로 한정됩니다. 따라서 오직 (100)만, 좋은 연속수입니다. 지금까지의 과정을 정리하면, i가 3 이상일 때, 좋은 i-연속수는 100으로 끝나야 합니다. 즉, T_1로 끝나야 한다는 것이죠.

    i=13일 때까지는, 어떤 i-연속수가 T_1로 끝나는데, 그 뒤에 0이 붙으면 1000이 되어 S_1이 되죠, 따라서 어떤 연속수가 S_1T_1로 끝나거나, S_1T_1T_1로 끝나면 뒤에 0이 붙었을 때 S_1S_1이나 S_1T_1S_1가 되어버려 모순입니다. S_1 다음에는 T_1이 2개나 3개 연속하여 와야 하기 때문입니다. 그래서 T_1T_1T_1T_1로 끝나서도 안됩니다. 따라서 좋은 연속수는 무조건 S_1T_1T_1T_1=T_2T_1으로 끝나야 합니다.

    이 과정을 반복하면 좋은 연속수는 ...T_4T_3T_2T_1로 끝나야 합니다. 따라서 임의의 i에 대해서 좋은 연속수는 정확히 하나씩 존재합니다.

     

    그럼 문제의 원래 의도는 무엇이었을까요?

    다음 두 개가 동치이긴 하지만 분명 이 둘 중 하나였을 것 같습니다.

    i) 1들 사이의 간격의 종류의 수가 정확히 두 가지라는 것을 증명하라는 것입니다. 위에서 제시한 S_{\inf}은 1들 사이에 연속한 0의 수가 3개이거나, 2개입니다. 따라서 k-연속수로 가능한 10의 거듭제곱수가 1000 또는 100이겠구나! 하고 착각한 것이죠. 사실 10도 가능한데 말입니다.

    ii) k-연속수로 가능한 수들 중 (10의 거듭제곱+1)꼴의 수 (1000001같은거)가 정확히 두 가지라는 것을 증명하라는 것입니다.

     

    마지막으로, 원래 의도의 부분문제 5를 해결함으로서 대한수학회 29번 문제에 완전한 마침표를 찍도록 하겠습니다.

    서로 동치이기 때문에, ii)를 증명하겠습니다.

    k-연속수로 가능한 수 중 10의 거듭제곱+1꼴의 수들의 집합을 X라고 하겠습니다.

    X의 원소가 하나일 때: 0000...000100010001000..과 같이 맨 앞에 0이 몇 개 붙은 뒤, 100...00꼴이 반복되는 형태여야 합니다. 맨 앞에 붙은 0의 수가 a개, 반복되는 100...00꼴을 이루는 숫자가 b개라고 하면, i=a+b일 때, N_i=i이므로 모순입니다.

    X의 원소가 세 개 이상일 때: 가장 큰 원소를 (100...001, 0이 t개)라고 하겠습니다.

    t-연속수로 가능한 경우는 모두 0으로 이루어진 경우와, 수열의 중간에 (100...001, 0이 t개)가 등장하므로, 1이 처음으로 등장하는 자리가 1번째 자리~t번째 자리까지 모두 가능하다. 이걸로 벌써 t+1가지이므로, N_t=t+1이기 위해서는, 1이 처음으로 등장하는 위치가 정해졌을 때, t-연속수가 유일하게 결정되어야 한다. (100...00, 0이 t-1개)가 t-연속수이므로, 1이 처음으로 등장하는 자리가 1번째 자리일 때는, t-연속수가 (100...00, 0이 t-1개)로 유일하다. 따라서, 1 다음에는 t-1개 이상의 0이 연속해야 한다. 그런데 X의 원소가 세 개 이상이므로, (100...001, 0이 t-2개 이하)인 원소가 존재한다. 모순입니다.

    \blacksquare

    좋아요0 댓글수3
    • 김우현 기자 2019.06.24 09:31:23

      깔끔한 정리, 고마워요. 수돌이 친구~.

      멘토님이 5번 문제 오류에 관한 내용과 풀이를 검토 중입니다! surprise

      좋아요0
    • 김우현 기자 2019.07.02 16:49:38

      1차 검토 완료!

      교수님께 최종 검토(문제 오류 포함)를 요청할게요~.laugh

      좋아요0
    • 김우현 기자 2019.07.13 14:48:45

      [최종 검토 완료] #수돌이 #해결

      지적한 오류, 풀이 모두 맞습니다. 원래 의도는 i)처럼 1과 1사이에 나올 수 있는 숫자열이 2가지 뿐임을 보이라는 것이었어요.

      교정 중에 오류가 생긴 점 죄송합니다. 문제의 표현을 수정하겠습니다.crying

       

      이로써 대한수학회 29번 문제는 최종 해결입니다!

      좋아요0
  • 김우현 기자 2019.07.09 09:33:57

    교수님이 바쁘셔서 검토가 늦어지고 있어요.

    목요일 전까지는 검토 결과를 알려주도록 힘쓸게요!! crying

    좋아요0 댓글수0
  • 김우현 기자 2019.07.13 14:54:48

    친구들의 뜨거운 열정에 감동해 교수님께서 보너스 문제를 내주셨습니다.

    보너스 문제를 풀어보고, 소문제 4번의 두 번째 종류의 수열도 찾아보세요! (보너스 문제는 문제 해결과는 별개입니다.) 

    좋아요0 댓글수0