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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대15.수열의 약한 주기성 관찰

2018.03.01

같이 풀어볼까?

네이버밴드 구글플러스

각각의 항이 0 또는 1인 수열 \LARGE a_1,\, a_2, \,a_3,\, a_4\cdots을 생각해 보자. 이러한 수열 중 가장 간단한 형태로 아래 예처럼 같은 모양이 반복적으로 나타나는 수열이 있다. 편의상 수열을 표기할 때  수들을 \LARGE a_1a_2a_3 a_4\cdots처럼 붙여서 나열하기로 하자.

 

(a) 모든 자연수 \LARGE i에 대해 \LARGE a_i=1 : 이때 수열은 111111111···

(b) 모든 자연수 \LARGE i에 대해 \LARGE a_3_i = 1,\, a_3_i_+_1 = a_3_i_+_2 = 0: 이때 수열은 001001001001···.

 

이런 수열을 강한 주기수열이라고 부르자. 엄밀하게 이야기하면, 다음 조건을 만족하는 수열 \LARGE a_1,\, a_2, \,a_3,\, a_4\cdots을 강한 주기수열이라고 정의할 수 있다.

 

“모든 자연수 \LARGE i 에 대해 \LARGE a_i_+_p=a_i를 만족하는 자연수 \LARGE p가 존재한다.”

 

위의 예 (a)에서 \LARGE p = 1, (b)에서 \LARGE p = 3이면 이 조건을 만족함을 쉽게 확인할 수 있다. 한편, 강한 주기수열에서는 \LARGE a_i = a_i_+_p = a_i_+_2_p = a_i_+_3_p = \cdots임을 알 수 있다. 즉 어떤 자연수 \LARGE i를 골라도, 모든 자연수 \LARGE n에 대해 \LARGE a_i = a_i_+_n_p가 성립한다.
 

위의 강한 주기수열의 정의를 조금 수정해, 다음 조건을 만족하는 수열 \LARGE a_1,\, a_2, \,a_3,\, a_4\cdots약한 주기수열이라고 정의하자.

 

“각각의 자연수 \LARGE i에 대해, \LARGE a_i = a_i_+_p = a_i_+_2_p = a_i_+_3_p = \cdots를 만족하는 자연수 \LARGE p가 존재한다.”

 

이는 다음과 같이 표현할 수도 있다. 어떤 자연수 \LARGE i를 고르고 나면 (\LARGE i에 따라 값이 다를 수 있는) 자연수 \LARGE p가 있어서, 모든 자연수 \LARGE n에 대해 \LARGE a_i = a_i_+_n_p가 성립한다.


강한 주기수열이 아닌 약한 주기수열의 쉬운 예를 하나 만들기 위해서, 아래와 같이 수열을 단계별로 정의해 보자.

0단계: ********************************

1단계: 1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*

2단계: 101*101*101*101*101*101*101*101*

3단계: 1011101*1011101*1011101*1011101*

4단계: 101110101011101*101110101011101* 

 

첫 번째 단계에서는 \LARGE b_1 = b_3 = b_5 = \cdots = 1로 정의하고, \LARGE b_2,\,b_4,\,b_6,\cdots는 아직 정하지 않았다 . 홀수 자연수 \LARGE i에서는 \LARGE p = 2로 정의하면 약한 주기수열의 정의를 만족한다. 두 번째 단계에서는 \LARGE b_2 = b_6 = b_1_0 = b_1_4 = \cdots = 0으로 정의하고, 나머지 부분은 아직 값을 정하지 않았다고 하자. 이때, 4로 나눈 나머지가 2인 자연수 \LARGE i에 대해서는 \LARGE p = 4로 정의하면 역시 약한 주기수열의 정의를 만족하게 된다. 이와 같이 세 번째 단계에서는\LARGE b_4 = b_1_2 = b_2_0 = b_2_8 = \cdots = 1로, 네 번째 단계에서는 \LARGE b_8 = b_2_4 = b_4_0 = b_5_6 = \cdots = 0으로 정의해 보자. 각각의 단계에서 아직까지 정의되지 않은 부분의 홀수 번째만 같은 수로 놓은 것임을 알 수 있다.

 

이렇게 반복해서 정의하면 각각의 자연\LARGE i에 대해 \LARGE i단계 안에 \LARGE b_i값이 정해지므로 수열이 잘 정의되고, 이 수열은 약한 주기수열임을 확인할 수 있다.

 

 

질문 0. 모든 강한 주기수열은 약한 주기수열임을 보여라. 또한 위의 마지막 예제에서 정의한 수열은 강한 주기수열이 아님을 보여라.

 


질문 1. 위의 예제에서 정의한 수열 \LARGE b_1,\,b_2,\,b_3,\cdots ···은 약한 주기수열임을 보이고, 임의의 자연수 \LARGE n에 대해 \LARGE b_i = b_i_+_{2^n}= b_i_+_2\cdot _{2^n} = b_i_+_3\cdot _{2^n} = \cdots을 만족하는 자연수 \LARGE i가 무한히 많음을 보여라.

 


질문 2. 0과 1로 이뤄진 자연수에서  수 0을 11로, 1을 10으로 바꾸는 규칙을 생각하자. 이 규칙을 0 에 반복적으로 적용하면 수열 11,1010,10111011,··· 을 얻는다. 이렇게 이 규칙을 0에 \LARGE n번 적용하여 나온 숫자의 \LARGE n번째 자릿수를 \LARGE c_n이라 하면, 이 수열 역시 약한 주기수열임을 보여라.

 


질문 3. 질문 2에서의 수열 \LARGE c_n과 예제의 수열 \LARGE b_n이 같은지 다른지 판별하라.

 


질문 4. 예제에서 정의한 수열 \LARGE b_1,\,b_2,\,b_3,\cdots ···을 생각하자. 자연수 \LARGE k에 대해, 집합 {\LARGE b_ib_i_+_1b_i_+_2\cdots b_i_+_k_-_1 : i는 자연수}의 크기를 \LARGE N_k라 하자. 따라서 \LARGE N_1 =\left \{ 0,1 \right \}의 크기=2 이고, \LARGE N_2=\left \{ 00,01,11 \right \}의 크기=3이다. 이때 충분히 큰 모든 자연수 \LARGE k에 대해 다음을 만족함을 보여라.

\LARGE \LARGE N_k< 2^{\tfrac{k}{2}}
 


질문 5. 다음 조건을 만족하는 약한 주기수열 \LARGE c_1,\,c_2,\,c_3,\cdots를 찾아라. 자연수 \LARGE k에 대해, 집합 {\LARGE c_ic_i_+_1c_i_+_2\cdots c_i_+_k_-_1 : i는 자연수}의 크기를 \LARGE N_k라 하면 충분히 큰 모든 \LARGE k에 대해 다음을 만족한다.

 \LARGE N_k> 2^{\tfrac{k}{2}}

 

 

 

*알립니다!

정의진 교수님의 코멘트가 도착했어요~laugh

 

①해결된 문제!

문제를 낸 정의진 교수님에 따르면 (0), (1), (2), (4)번 문제는 해결됐고, (3)번 문제 역시 친구들이 엄밀하게 쓰지는 않았지만, 아이디어만 보면 거의 해결됐다고 합니다! (엄밀하게 정리해 줄 친구 손!!)

 

②출제자의 한 마디!

-(5)번 문제는 친구들이 괜찮은 아이디어를 많이 내줬는데, 완벽한 증명하려면 아직 시간이 걸릴 거라고 해요.

-수학자 친구가 이야기한 것처럼, (4)번 문제에서 N_k는 문제에서 나온 값보다 훨씬 작아집니다. 따라서 이렇게 접근하면 (5)번 문제를 풀기가 어렵긴 해요!

댓글 57

  • muse 2018.03.01 10:42:48

    일단 거저 주는 0번 문제부터...

    수열 a가 강한 주기수열이면 모든 자연수 i에 대해 a_{i+p}=a_i를 만족하는 자연수 p가 존재할 겁니다.

    그런데 이 수열이 약한 주기수열이라면 정의와 같이 각각의 자연수 i에 대해 a_i = a_{i+p} = a_{i+2p} + a_{1+3p} = \cdots를 만족하는 자연수 p가 존재합니다.

    이 식에서의 p를 강한 주기수열의 정의에서의 p라고 하면, 식이 성립하게 됨은 자명합니다.

    그래서 강한 주기수열은 약한 주기수열입니다.

     

    다음, 마지막 예제에서 정의한 수열은 강한 주기수열이 아님을 보이죠.

    이 수열을 점화식 형태로 나타내면, 프랙탈(fractal) 형태를 띔을 알 수 있습니다.

    즉 n을 2로 나눈 나머지를 k라고 하면,

    f(0) = (빈 수열), f(1) = f(n-1) k f(n-1)입니다.

     

    이제, 이 수열이 강한 주기수열이라고 가정합시다.

    자연수 p가 있어서, 모든 자연수 n에 대해 a_{i+p}=a_i가 성립할 겁니다.

    하지만, 이러한 p가 존재한다는 것은 수열이 p의 길이씩 순환한다는 의미입니다.

    그런데 이 수열은, 같은 마디가 순환할 수 없습니다. f(n-1) 사이에 k가 있기 때문인데, 이 k는 n에 따라 달라지기 때문입니다.

    그래서 무한히 순환하는 마디는 이 수열에 존재할 수 없습니다.

    따라서, 모순이 발생하게 되고, 이에 따라 이 수열은 강한 주기수열이 아님을 보일 수 있습니다.

    처음 해본 증명이라 조금 미숙한데 이해해 주세요...

    좋아요0 댓글수0
  • ssamtkwon 2018.03.01 14:08:57

    1번 문제도 풀만하네요.

    질문 1. 위의 예제에서 정의한 수열 b_1,\,b_2,\,b_3,\cdots ···은 약한 주기수열임을 보이고, 임의의 자연수 \LARGE n에 대해 b_i = b_i_+_{2^n}= b_i_+_2\cdot _{2^n} = b_i_+_3\cdot _{2^n} = \cdots을 만족하는 자연수 \LARGE i가 무한히 많음을 보여라.

    저 조건을 만족하는 i를 하나라도 찾으면 i+2^{n}, i+2*2^{n}...도 모두 이 조건을 만족하죠. 그리고 i가 1이면 n의 값에 상관없이 만족하니까 풀었네요.

    좋아요0 댓글수0
  • 수학장 2018.03.01 17:50:42

    2번 문제도 풀었습니다. 정의에서, 0은 11로, 1은 10으로 바뀌므로 홀수 번째 항은 항상 1이 됨을 알 수 있다.(11과 10의 시작이 모두 1이기 때문)

    c_{2n}=\begin{Bmatrix} 1 (c_{n}=0)\\ 0(c_{n}=1) \end{matrix}인 것도 알 수 있다.

    c_{2n}에서 n이 홀수면, 즉 c_{2}, c_{6}, c_{10},...=0이다. 홀수 k에 대해, c_{4k}꼴인 수들은 1이 된다.

    c_{2^{n}\cdot k}=\begin{Bmatrix}1(n\equiv 0(mod \2)) \\ 0(n\equiv 1(mod \2)) \end{matrix}이다. 즉, c_{n}은 약한 주기수열이다.

     

    그리고, 이로 인해 b_{n}=c_{n}임을 알 수 있습니다. 제가 정의한 c_{n}과 문제에서 정의한 b_{n}의 정의가 같기 때문입니다.

    3번도 풀었습니다.

    좋아요0 댓글수2
    • ssamtkwon 2018.03.03 21:44:08

      이상한데요. c_{2n}은 2n번째 수열의 2n번째 항인데, 그걸 n+1번째 수열의 2n번째 항처럼 사용한 것 같아요.

      좋아요0
    • 수학장 2018.03.04 17:20:30

      2n-1번 한 거의 n번째 항은

      c_n과 같습니다

      좋아요0
  • 수학장 2018.03.01 18:02:18

    기자님 5번 문제의 c_{n}은 2번 문제와는 별개인 거죠?

    좋아요0 댓글수1
    • 수학동아 2018.03.01 19:02:37

      네~ 5번의 c_n은 2번 문제 c_n과는 별개입니다.^^

      좋아요0
  • 수학장 2018.03.01 18:40:36

    4번 문제 접근 :k가 충분히 크지 않으면 N_{k}>2^{\frac{k}{2}}가 됩니다. 

    우리는 N_{k}의 개수의 함수의 그래프가 2^{\frac{k}{2}}의 그래프와 만나는 점이 있다는 걸 증명하면 됩니다. N_{k}의 조건만 알면 계산하면 되겠네요.

    좋아요0 댓글수0
  • The 1975 2018.03.01 19:15:43

    5번 풀이로 이런 접근방식을 하면 어떨까 생각이 들어 댓글 남깁니다.

    먼저 모든 수열들이 0부터 시작한다고 합시다. 이렇게 해도 문제 조건은 안 바뀌니 괜찮습니다.
    어떤 자연수로 이루어진 증가수열 d_0 < d_1 < \cdots를 상정합시다. 이 수열은 나중에 정할 겁니다.
    음이 아닌 정수로 이루어진 수열 x_0, x_1, x_2, \cdots을 다음과 같이 잡읍시다:

    처음엔 모든 x_i들의 값이 정해지지 않았다는 의미로 *이라는 임시의 값을 답시다. 이는 나중에 수정되고 모든 x_i들이 자연수값을 가지게 될 것입니다.
    i=0부터 귀납적으로 x_i들의 값을 정의합시다. 그리고 각 단계가 끝날 때마다 변할 수 있는 변수 x를 잡읍시다. 첫 번째 단계(i=0)에선 이 변수의 값이 0입니다.
    x_i의 값을 정하는 단계를 i번째 단계라고 합시다. 만약 x_i의 값이 *이 아니라면, 값을 그대로 둡니다.
    만약 x_i의 값이 *이라면, 모든 j \geq 0에 대해 x_{i+j2^{d_x}}의 값을 x로 설정하고, x에 1을 더합니다.
    이렇게 하면 2의 자승의 증가하는 간격으로 값을 설정하는 것이기에 모순이 생기지 않습니다 (이미 정해진 값에 다른 값을 설정하지 않습니다).

    이렇게 하면 수열 x_i은 약한 주기수열입니다. 물론 x_i는 0이나 1이 아닌 다른 (모든 자연수)값을 가집니다.
    하지만 증가수열 d_i를 매우 빠르게 증가하게 하면 x_i들에서 등장하는 수들의 값이 거의 '다르게' 할 수 있습니다.
    그 말인 즉슨, 대충 K개의 연속한 x_i들의 값을 잡으면 개중 서로 다른 수들의 개수가 대략

    K - \frac{K}{2^{d_0}} - \frac{K}{2^{d_1}} - \frac{K}{2^{d_2}} \cdots

    정도가 되서, 거의 K랑 같아지길 바란다는 것입니다. 여기서 K/2^{d_i}}항은 대략 숫자 i가 얼마나 중복되는가를 나타내는가입니다.

    아이디어는 d_i랑 '색칠 함수' c : \mathbb{N} \rightarrow \{0, 1\}을 잘 잡아 c_i = c(x_i)가 문제에서 요구하는 수열이 되게 하는 것입니다.
    위의 코멘트에서 볼 수 있듯이 충분히 큰 K에 대해 K개 수의 의 많은 fraction들의 색을 동시에 조정할 수 있습니다.
    그래서 문제에서 요구하는 집합도 충분히 '랜덤하게' 가능한 모든 길이 k의 수열들을 다 지날 수 있게 설정할 수 있을 거 같은데, 아직은 방법이 요원하네요.

    디테일을 채우는 게 문제일 것 같은데, 같이 한번 생각해봅시다. 혹시 궁금하신 점이나 이해가 안 가시는 부분 있으시면 댓글 달아주세요. 언제나 환영입니다.

     

    좋아요0 댓글수0
  • 여백 패르마 2018.03.02 08:18:19

    좋아요0 댓글수3
    • 여백 패르마 2018.03.02 08:18:43

      4번 풀이입니다.

      좋아요0
    • 티민thymine 2018.03.05 21:06:35

      N의 집합은 어떻게 정의되나요?

      좋아요0
    • 여백 패르마 2018.03.06 15:47:12

      자연수+0입니다.

      좋아요0
  • 여백 패르마 2018.03.02 15:34:17

    제 사진 풀이가 너무 않 보여서 씁니다. 사진풀이 보충(?)2^{\frac{3}{8}k}

    수학장 님의 의견과 같게 k가 홀수일때 b_{k}=1가 성립합니다.

    N_{k}의  k가 짝수이라면 홀수는 \frac{k}{2}개 있습니다. 또, 4의 배수의 개수는 k/8개입니다. 즉, 남은 것은 3/8k개의 자리입니다. 

    또, 모든 곳에는 0,1만 들어갈 수 있기 때문에 경우는 2^{\frac{3}{8}k}< 2^\frac{k}{2}이고, 그래서 \frac{k}{2}\in \mathbb{N}이면 맞습니다.

    맨 처음이 b_{k} (\frac{k}{2}\notin \mathbb{N})이라면 홀수는 \frac{k+1}{2}개가 있고, 즉, 경우는 2^{\frac{k-1}{2}}<2^{\frac{k}{2}}입니다. 그래서 맨 처음이 홀수이면 맞습니다. 

    2번째가 홀수인 경우가 있는데, 그때는 홀수가 \frac{k-1}{2}개 있습니다. 또,  4의 배수의 개수는  \frac{k}{8}개입니다.

    즉, 경우는2^{\frac{3}{8}k-\frac{1}{2}}<2^{\frac{k}{2}}입니다. 아래는 그의 증명입니다. 

    2^{\frac{3}{8}k-\frac{1}{2}}<2^{\frac{k}{2}} 임을 수학적 귀납법을 이용해서 증명해봅시다.

    16을 집어넣어 보면  맞습니다.

    또,2^{\frac{3}{8}k-\frac{1}{2}}가 k=k+1 가 될때 2^{\frac{3}{8}k} 가 곱해지는데, 반면

    2^{\frac{k}{2}}는 k=k+1가 될때 2^{\frac{1}{2}}가 곱해집니다. 즉, 2^{\frac{3}{8}k-\frac{1}{2}}<2^{\frac{k}{2}}입니다.

    Q.E.D​​​​​​​

    좋아요0 댓글수4
    • 여백 패르마 2018.03.02 15:36:32

      그리고 k가 적당한 크기의 수인 이유는 3번째 경우에서 가끔 아니기 때문입니다.(작으면 말이지요.)

      좋아요0
    • 여백 패르마 2018.03.03 09:55:10

      갑자기 수정하는데 수식기가 ....

      양해 부탁들입니다.

      좋아요0
    • 여백 패르마 2018.03.04 19:30:33

      이거 풀이 확인 부탁들입니다.

      좋아요0
    • 여백 패르마 2018.03.11 11:51:05

      처음 경우는 2^{\frac{k}{3}}가지, 두번째는 2^{\frac{k}{3}-\frac{1}{2}} 세번째는 2^{\frac{k}{3}+\frac{1}{2}}이고, 세번째 경우의 부등식 증명은 쉽습니다.

       

      좋아요0
  • 수학장 2018.03.02 22:54:46

    일단 N_{k}의 조건입니다.

    1. N_{k}는 0과 1을 k개 배열할 수 있는 경우의 집합이다.

    2. N_{k}의 원소에는 0이 2번 연속으로 나올 수 없다.

    3. N_{k}의 원소에는 1이 짝수 번 나오거나 4번 이상 연속해서 나올 수 없다.

    4. N_{k}에는 01110111011101110같은 배열(111이 4번 이상 연속한 배열)은 나올 수 없다.

    이 조건을 만족하는 개수의 함수를 f(k)로 정하고, g(k)2^{\frac{k}{2}}로 놨을 때,  충분히 큰 실수 a와 모든 양의 실수 n에 대해 f(a+n)>g(a+n) 를 만족하면 된다.

    이걸 증명하기 위해서는, f(k)g(k)보다 완만하게 변한다는 것을 증명하면 된다.

    좋아요0 댓글수2
    • 여백 패르마 2018.03.03 08:21:52

      2번 연속은 가능합니다.(1의 연속 말이죠.) b3,b4가 있습니다.

      좋아요0
    • 수학장 2018.03.03 11:47:58

      아 처음이랑 끝에서는 가능하겠군요! 조건이 좀 까다롭네요 개수를 어떻게 구하죠=_=

      좋아요1
  • 티민thymine 2018.03.03 22:40:30

    N2={01,10,11}로 3 아닌가요?

    제가 이해를 못한 건가요 ㅠㅠ

    좋아요0 댓글수2
    • 수학장 2018.03.04 00:44:31

      맞아요 문제가 잘못 나와 있는 거임

      좋아요0
    • 여백 패르마 2018.03.04 20:37:48

      수정해주세요!!

      좋아요0
  • 수학자 2018.03.04 10:14:04

    사실 질문 4에서 k가 충분히 크다면, N_k가 2^{k/2}와는 비교할 수 없을 정도로 작을 듯 합니다. 2k 이하라는 것도 보일 수 있을 것 같습니다.

    좋아요0 댓글수1
    • 여백 패르마 2018.03.04 19:54:47

      맞는 것 같습니다. 제 풀이는 꽤 높은 상한이기 때문에 2k는 나오지 않았습니다.

      좋아요0
  • 티민thymine 2018.03.05 21:48:10

    질문 5에 대한 생각입니다.

    소수의 성질을 이용하면 될 것 같습니다. 에라토스테네스의 체와 비슷한 방법으로 수열을 만들어 보겠습니다.

    수열 an을 다음과 같이 정의하겠습니다. (50번째 항까지 표기)

    1. a1=1이다.

    1*************************************************

    2. a2n=0이다. (n\inN,N은 자연수의 집합)

    10*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0*0

    3. a3n=1이다. (3n번째 항이 정해진 경우 무시하고 이 규칙을 따른다.)

    1010*1*010*1*010*1*010*1*010*1*010*1*010*1*010*1*0

    4. a5n=0이다. (5n번째 항이 정해진 경우 무시하고 이 규칙을 따른다.)

    101001*010*1*000*1*010*10010*0*01001*010*1*000*1*0

    5. a7n=1이다. (7n번째 항이 정해진 경우 무시하고 이 규칙을 따른다.)

    1010011010*1*100*1*010*10011*0*01011*010*1*000*110

    6. a11n=0이다. (11n번째 항이 정해진 경우 무시하고 이 규칙을 따른다.)

    101001101001*100*1*010*10011*0*00011*010*1*000*110

    7. a13n=1이다. (13n번째 항이 정해진 경우 무시하고 이 규칙을 따른다.)

    1010011010011100*1*010*10111*0*00011*010*1*000*110

    계속하면 수열 an

    10100110100111000110100101111000001110100110000110

    을 얻는다.

    이를 바탕으로 집합 Nk를 생각하면

    N_{1}=2> 2^\frac{1}{2}

    N_{2}=4> 2^\frac{2}{2}

    N_{3}=8> 2^\frac{3}{2}

    N_{4}=16> 2^\frac{4}{2}

    이렇게 되기는 한데... 약한 주기수열이 아니라서... 정답은 아니네요.

    좋아요0 댓글수4
    • 티민thymine 2018.03.05 21:54:18

      주기수열을 만들려고 하면 

      자연수n으로 나눴을 때 나머지가 k인 항은 1 또는 0 이런식으로 정하는 방법밖에 떠오르지 않아서 무작위성을 만들려고 소수를 택했는데

      그렇게만 하면 2의 배수로 도배가 되니까 숫자가 겹칠 때는 앞의 규칙을 무시하는 방법으로 했습니다. 그렇게 하다 보니까 약한 주기수열에서 벗어나게 되더군요.

      좋아요0
    • 티민thymine 2018.03.05 21:57:25

      수열 an을 짧게 설명하면

      1. a1=1

      2. n번째 항은 n의 가장 큰 소인수가 소수의 수열 2,3,5,7,...에서 2k(k는 자연수)번째 항이면 1, 아니면 0입니다.

      좋아요0
    • 수학장 2018.03.06 21:21:16

      그리고 N1, N2, N3, N4에서만 맞아서는 안 됩니다. 어떤 수 k가 존재 하여 k이상의 수이면 N_k에서 k가 아무리 커도 N_k가 2^(k/2)보다 커야 합니다. 보통 수열은 그렇지 않을 것으로 생각됩니다.

      좋아요0
    • 티민thymine 2018.03.07 15:40:38

      알고 있습니다. 하지만 시간이 부족해서 N4까지 보여드린 것입니다. 소수의 특성을 이요한 것이라 모든 Nk에 대하여 성립할 것으로 보입니다.

      좋아요0
  • 여백 패르마 2018.03.11 12:12:03

    피드백은 언제이지요??

    좋아요0 댓글수2
    • 여백 패르마 2018.03.11 12:12:35

      10일 됬는데 아직도 피드백이 없던데..

      좋아요0
    • 김우현 기자 2018.03.11 20:09:59

      주정훈 멘토의 피드백은 주말이 지나고 올라갈 예정입니다. 조금만 더 기다려 주세요~ ^.<

      좋아요0
  • 쌀밥공기 2018.03.12 23:15:03

    맞을지 모르겠네요;;

    좋아요0 댓글수3
    • 쌀밥공기 2018.03.12 23:23:09

      질문 1은 N이 무한대로 발산할 때 C_N이 C_1, C_2, C_3, C_4, ... 의 문자열을 포함하고 있으므로 임의의 n에대해, n번째 정의된 수열이라면, 문제 0처럼 C_N을 C_n들의 연결로 전개하면 만족하는 i가 무한이 많음을 보일 수 있습니다.

      좋아요0
    • 여백 패르마 2018.03.13 07:53:42

      0,1 번은 이미 풀렸는데...

      좋아요0
    • 쌀밥공기 2018.03.13 20:26:12

      muse님의 풀이에서, "k는 n에 따라 달라지기 때문"이라 명시되어있지만 이 문장만으로 강한주기 수열의 주기 P의 존재성을 부정 할 수 없습니다.

      좋아요0
  • 김우현 기자 2018.03.16 17:07:00

    주정훈 멘토의 피드백이 도착했으니, 다들 확인해 보세요 :)

    좋아요0 댓글수0
  • 수학장 2018.03.16 23:20:50

    제가 전에 했던 3번 풀이의 부족한 점이 아마 c의 n번째 수열의 n번째 항, 즉 c_n과 c의 n+k번째 수열의 n번째 항이 같다는 것을 증명하지 않았기 때문인 것 같습니다. 일단, 쉽게 증명하기 위해, c의 n번째 수열의 k번째 항을 c_{n,k}로 표현하겠습니다; c_{n,n}=c_n입니다. c_1=1이고, c_{k,1}c_{k-1,1}이 1이므로 역시 1입니다. c_{2}=0이고, c_{k,2}c_{k-1,1}=1이므로 0입니다.

    그러면, k와 그보다 큰 n에 대해, c_{n,k}=c_{k}임을 증명하면 됩니다. 일단, 뒤의 수보다 큰 k에 대해, c_{k,1}=1이고, c_{k,2}=0이 됩니다. 그러면 다시 돌아가서 c_{n,k}에 대해 일정하려면, c_{n-1,\frac{k}{2}}가 일정해야 되는데, n은 고정된 수가 아닌, k보다 큰 모든 수이므로 그냥 n-1이라고 복잡하게 쓰지 않고, n이라고 쓰셔도 됩니다. k가 2h의 꼴일 때 : h에 대해 c_{n,h}가 일정하면 c_{n,k}가 일정합니다. k가 2h+1의 꼴일 때 : 이 역시도, h에 따라 결정되므로, c_{n,h}가 일정하면 c_{n,k}가 일정합니다.

     

    뭔가 증명하면서 횡설수설함이 있었는데, 정리해드릴게요 :

    1. c_{k,1}은 일정하다.

    2. c_{k,h}가 일정하면, c_{k,2h}가 일정하다.(수열 c의 정의에 의해)

    3. c_{k,h}가 일정하면, c_{k,2h+1}가 일정하다.(수열 c의 정의에 의해)

    이렇게 정리됩니다.

     

    그리고, 어떤 자연수 n이 있을 때 이 시행을 반복합시다.

    1. n이 홀수면, n에서 1을 빼고 2로 나눈다.

    2. n이 짝수면, n을 2로 나눈다.

    3. 1번, 2번 시행을 반복한다.

    이렇게 하면, 결국 n은 1이 됨을 알 수 있습니다. 이 시행은, 'h가 성립함에 대해 2h가 성립하고, h가 성립함에 대해 2h+1이 성립하며, h가 1일 때 성립한다면, 모든 자연수 h에 대해 성립한다'는 것의 대우 명제를 시행으로 나타낸 것입니다. 대우 명제가 성립하면 원래 명제가 성립합니다. 따라서, 모든 자연수 n에 대해, c_{n}=c_{k,n}(k>n)이게 성립합니다.

     

    여전히 횡설수설이군요.......... 어쨌든 이해는 가시면 좋겠습니다.

    좋아요0 댓글수2
    • 수학자 2018.03.17 11:10:45

      아마 b_n 역시 소인수 2의 개수의 홀짝성임을 보이면 완벽할 것 같습니다.

      좋아요0
    • 여백 패르마 2018.03.17 19:31:36

      문제에서 b_1=b_3=b_5=...=1  이고, b_2=b_6=b_{10}=...=0 이며, b_4=b_{12}=b_{20}=...=0 이고, 등등 입니다. 

      즉,\frac{k}{2}\notin \mathbb{N}, k\in \mathbb{N}일떄b_{2^{n}\times k}=1 (n\equiv 0(mod 2))=0(n\equiv 1(mod2)) 입니다. 이것은 수학장님의 풀이의 c_n과 같습니다.

      좋아요0
  • 수학자 2018.03.17 11:58:55

    4번 풀이입니다.

    예제의 수열 b_n은 n=2^p \times A(A는 홀수) 에 대해, p가 짝수면 1, 홀수면 0입니다.

    그렇다면, 임의의 자연수 t에 대해, x를 2^t으로 나눈 나머지가 r(\neq 0)이라면, b_x = b_r입니다. 왜냐하면 r의 소인수분해의 2의 개수는 t보다 작아서, 2^t의 배수를 더한다고 해도 달라지지 않기 때문입니다. 이는 곧, 2^t으로 나눈 나머지가 1부터 2^t-1인 부분이 고정된다는 것입니다. 이제 t를 2^t \le k < 2^{t+1}를 만족하는 t로 놓고(유일하게 존재합니다), b_i b_{i+1} \cdots b_{i+k-1}을 생각해보면, i를 2^t로 나눈 나머지 r에 따라 이 수열의 상당 부분이 정해집니다. 정확히는, r = 0일 때 b_i ,b_{i+2^t}를 제외한 모든 부분이 정해지며, 1 \le r \le 2^{t+1} - k일 때 b_{i+2^t - r}를 제외한 모든 부분이, 나머지 경우 b_{i+2^t -r}, b_{i+2^{t+1}-r}을 제외한 모든 부분이 정해집니다. 정해지지 않은 부분은 0 또는 1이 오므로, 정해지지 않은 부분이 1개인 경우 가능한 경우의 수는 2, 2개인 경우 가능한 경우의 수는 4입니다. 이 중에 중복이 있을 수도 있지만, 누락은 없습니다. 그러므로 총 경우의 수는 많아야 (2^{t+1} - k) \times 2 + (k-2^t) \times 4 = 2k입니다. k가 충분히 크면, 2^{(k+1)/2}는 2^{k/2}의 \sqrt2배가 되는 데 비해, 2(k+1)은 2k의 1+1/k (< \sqrt2~ for~ k>3 )배가 됩니다. 또한 k=16일 때 2k = 32 < 2^{16/2} = 256입니다. 그러므로 k가 충분히 크면, 증가폭이 더 큰 2^{k/2}가 2k보다 큽니다. N_k \le 2k < 2^{k/2}

    좋아요0 댓글수1
    • 여백 패르마 2018.03.17 20:23:40

      이렇게 풀어도 가능합니다.  \frac{k}{2}\notin \mathbb{N}, k\in \mathbb{N}일때 b_{2^{n}\times k}=1(n\equiv 0(mod2))=0(n\equiv 1(mod2))입니다.

      이제 본격적으로 N_k을 계산합시다. 

      <Lemma (1)> 첫 항이 a이고, 공비가 n인 무한등비수열의 합은 \frac{a}{1-n}입니다.

      pf(1)) 합 S=a+an+an^{2}+...이 있습니다. 

      nS=an+an^{2}+an^{3}+...    S=a+an+an^{2}+...이 둘의 차를 구하면

       (1-n)S=a이 되고, 즉 S=\frac{a}{1-n}입니다.

      <본 증명> 'i,i+1,i+3,i+4,...,i+k-1'은 k개이고, b_k로 바뀌어도 k개 이다.

      그래서 k번째 의 자리는 b_k값이 있어야 하는 곳이다. 

      홀수번째 자리는 1이다. 약 \frac{k}{2}개의 홀수번째의 자리가 있다.

      4\times(홀수)번째 자리도 1입니다. 약 \frac{k}{8}개의 자리가 있다. 이것을 반복하면 \frac{k}{2}(1+\frac{1}4+\frac{1}{16}+...)개의 1인 자리수가 있다.

       a=1, n=\frac{1}{4}이기 때문에 S=\frac{1}{\frac{3}{4}}=\frac{4}{3}   즉, \frac{1}{2} k\times \frac{4}{3}=\frac{2}{3}k개의 자리가 1입니다. 

      나머지 자리는 아무리 적어도 2^{\frac{1}{3}k}개 입니다. 2^{\frac{1}{3}k}<2^{\frac{1}{2}k}

                                                                                                                                                                                                                            Q.E.D

       

      좋아요0
  • 여백 패르마 2018.03.18 19:22:27

    어 그런데 약한 주기수열의 정의에서의 i가 문제의 k이면 5번 문제의 답이 되지 않나요?

    좋아요0 댓글수0
  • 여백 패르마 2018.03.28 15:40:08

    좋아요0 댓글수1
    • 여백 패르마 2018.03.28 15:40:34

      아시겠지만 순서는...

      좋아요0
  • 수학장 2018.03.29 21:43:53

    4번 문제 좋은 아이디어를 찾았습니다. 일단 b_i에서 i가 홀수이면 무조건 1입니다. 즉, 1이 계속 번갈아가면서 나옵니다. 그러므로, 결정 가능한 칸은 k/2개이고, 경우의 수는 2^{k/2}보다 작게 됩니다. 다만, 문제는 N_k의 시작이 뭐일지 모르기 때문에 2^{\frac{k}{2}+1}개의 경우의 수가 나옵니다. 이걸 더 줄여나가면 될 것 같은데, 어렵지 않을 듯합니다.

    b수열 정의의 2단계를 봅시다. b_k는 항상 101*101*101*101*......가 반복됩니다. 따라서 별칸을 채웠을 때 임의의 k개의 연속한 수를 골랐을 때 나오는 경우의 수는 2^{\frac{k}{4}+2}이하입니다.

    b수열 정의의 n단계에서, 결정 가능한 칸은 대략 \frac{k}{2^n}개가 되고, 시작 가능한 경우는 2^{n}가 됩니다.

    즉, N_k=\lim_{n\rightarrow \infty }2^{\frac{k}{2^n}+n-1}입니다. 이게 k가 충분히 클 때, 2^\frac{k}{2}보다 작다는 것만 증명하면 됩니다.

     

    제가 설명을 잘 못해서 그러는데..... 이해 되시나요?

    좋아요0 댓글수1
    • 수학장 2018.03.29 22:57:59

      n이 무한으로 가면 안 될 것 같네요. 어쨌든 n에 값과 상관 없이 성립하는 n만 찾으면 될 것 같습니다.

      제가 해결하지 못하지라도, 이건 결정적 아이디어가 될 것 같습니다.(뜻 : 제가 풀 자신 없어요.)

      좋아요0