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

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-연속수로 나올 수 있는 수 중에 10의 거듭제곱꼴의 수(10^{m}형태의 수)는

             단 두 개 뿐임을 증명하라.

 

 

 

☆★ 알립니다 ★☆

tommy 친구가 소문제 1, 3번을 해결했어요!

 

 

댓글 27

  • 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 친구의 소문제 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개를 반복하면 됩니다.

      좋아요0
    • 리프 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 친구의 소문제 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 댓글수4
    • 김우현 기자 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.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