수학동아 - 폴리매스

폴리매스 문제

아직 아무도 답을 모르는 문제에 도전하세요!

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

수학동아 2018.03.01 05:54 조회 2079

페이스북 트위터 카카오톡 카카오스토리 네이버블로그 네이버밴드

대한수학회 15번

수열의 약한 주기성 관찰

문제 출제자 : 정의진 아주대학교 수학과 교수

각각의 항이 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^{ frac{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^{ frac{k}{2}}$

*알립니다!

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

①해결된 문제!

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

②출제자의 한 마디!

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

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

이전글 대14. 정육면체 분할해 정육면체 만들기

다음글 대16. 정보의 양 측정하기

문제 찜하기 목록보기

댓글 작성하기

muse Lv.6 2018.03.01 10:42

일단 거저 주는 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 Lv.1 2018.03.01 14:08

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
베네딕트0724 Lv.6 2018.03.01 17:50

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 Lv.1 2018.03.03 21:44
  
  이상한데요. $c_{2n}$ 은 2n번째 수열의 2n번째 항인데, 그걸 n+1번째 수열의 2n번째 항처럼 사용한 것 같아요.
  
  좋아요0
- 베네딕트0724 Lv.6 2018.03.04 17:20
  
  2n-1번 한 거의 n번째 항은
  
  c_n과 같습니다
  
  좋아요0
베네딕트0724 Lv.6 2018.03.01 18:02

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

댓글 작성하기 좋아요0 댓글수1
- 조가현 편집장 Lv.15 2018.03.01 19:02
  
  네~ 5번의 c_n은 2번 문제 c_n과는 별개입니다.^^
  
  좋아요0
베네딕트0724 Lv.6 2018.03.01 18:40

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

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

댓글 작성하기 좋아요0 댓글수0
출제자(슬기) Lv.4 2018.03.01 19:15

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
여백 패르마 Lv.5 2018.03.02 08:18

댓글 작성하기 좋아요0 댓글수3
- 여백 패르마 Lv.5 2018.03.02 08:18
  
  4번 풀이입니다.
  
  좋아요0
- 티민thymine Lv.1 2018.03.05 21:06
  
  N₀의 집합은 어떻게 정의되나요?
  
  좋아요0
- 여백 패르마 Lv.5 2018.03.06 15:47
  
  자연수+0입니다.
  
  좋아요0
여백 패르마 Lv.5 2018.03.02 15:34

제 사진 풀이가 너무 않 보여서 씁니다. 사진풀이 보충(?) $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
- 여백 패르마 Lv.5 2018.03.02 15:36
  
  그리고 $k$ 가 적당한 크기의 수인 이유는 3번째 경우에서 가끔 아니기 때문입니다.(작으면 말이지요.)
  
  좋아요0
- 여백 패르마 Lv.5 2018.03.03 09:55
  
  갑자기 수정하는데 수식기가 ....
  
  양해 부탁들입니다.
  
  좋아요0
- 여백 패르마 Lv.5 2018.03.04 19:30
  
  이거 풀이 확인 부탁들입니다.
  
  좋아요0
- 여백 패르마 Lv.5 2018.03.11 11:51
  
  처음 경우는 $2^{\frac{k}{3}}$ 가지, 두번째는 $2^{\frac{k}{3}-\frac{1}{2}}$ 세번째는 $2^{\frac{k}{3}+\frac{1}{2}}$ 이고, 세번째 경우의 부등식 증명은 쉽습니다.
  
  좋아요0
베네딕트0724 Lv.6 2018.03.02 22:54

일단 $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
- 여백 패르마 Lv.5 2018.03.03 08:21
  
  2번 연속은 가능합니다.(1의 연속 말이죠.) b3,b4가 있습니다.
  
  좋아요0
- 베네딕트0724 Lv.6 2018.03.03 11:47
  
  아 처음이랑 끝에서는 가능하겠군요! 조건이 좀 까다롭네요 개수를 어떻게 구하죠=_=
  
  좋아요1
티민thymine Lv.1 2018.03.03 22:40

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

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

댓글 작성하기 좋아요0 댓글수2
- 베네딕트0724 Lv.6 2018.03.04 00:44
  
  맞아요 문제가 잘못 나와 있는 거임
  
  좋아요0
- 여백 패르마 Lv.5 2018.03.04 20:37
  
  수정해주세요!!
  
  좋아요0
수학자 Lv.2 2018.03.04 10:14

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

댓글 작성하기 좋아요0 댓글수1
- 여백 패르마 Lv.5 2018.03.04 19:54
  
  맞는 것 같습니다. 제 풀이는 꽤 높은 상한이기 때문에 $2k$ 는 나오지 않았습니다.
  
  좋아요0
티민thymine Lv.1 2018.03.05 21:48

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

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

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

1. a₁=1이다.

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

2. a_2n=0이다. (n $\in$ N,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. a_3n=1이다. (3n번째 항이 정해진 경우 무시하고 이 규칙을 따른다.)

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

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

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

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

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

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

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

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

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

계속하면 수열 a_n

10100110100111000110100101111000001110100110000110

을 얻는다.

이를 바탕으로 집합 N_{k를 생각하면}

$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 Lv.1 2018.03.05 21:54
  
  주기수열을 만들려고 하면
  
  자연수n으로 나눴을 때 나머지가 k인 항은 1 또는 0 이런식으로 정하는 방법밖에 떠오르지 않아서 무작위성을 만들려고 소수를 택했는데
  
  그렇게만 하면 2의 배수로 도배가 되니까 숫자가 겹칠 때는 앞의 규칙을 무시하는 방법으로 했습니다. 그렇게 하다 보니까 약한 주기수열에서 벗어나게 되더군요.
  
  좋아요0
- 티민thymine Lv.1 2018.03.05 21:57
  
  수열 a_n을 짧게 설명하면
  
  1. a₁=1
  
  2. n번째 항은 n의 가장 큰 소인수가 소수의 수열 2,3,5,7,...에서 2k(k는 자연수)번째 항이면 1, 아니면 0입니다.
  
  좋아요0
- 베네딕트0724 Lv.6 2018.03.06 21:21
  
  그리고 N1, N2, N3, N4에서만 맞아서는 안 됩니다. 어떤 수 k가 존재 하여 k이상의 수이면 N_k에서 k가 아무리 커도 N_k가 2^(k/2)보다 커야 합니다. 보통 수열은 그렇지 않을 것으로 생각됩니다.
  
  좋아요0
- 티민thymine Lv.1 2018.03.07 15:40
  
  알고 있습니다. 하지만 시간이 부족해서 N₄까지 보여드린 것입니다. 소수의 특성을 이요한 것이라 모든 N_k에 대하여 성립할 것으로 보입니다.
  
  좋아요0
여백 패르마 Lv.5 2018.03.11 12:12

피드백은 언제이지요??

댓글 작성하기 좋아요0 댓글수2
- 여백 패르마 Lv.5 2018.03.11 12:12
  
  10일 됬는데 아직도 피드백이 없던데..
  
  좋아요0
- 김우현 기자 Lv.5 2018.03.11 20:09
  
  주정훈 멘토의 피드백은 주말이 지나고 올라갈 예정입니다. 조금만 더 기다려 주세요~ ^.<
  
  좋아요0
쌀밥공기 Lv.1 2018.03.12 23:15

맞을지 모르겠네요;;

댓글 작성하기 좋아요0 댓글수3
- 쌀밥공기 Lv.1 2018.03.12 23:23
  
  질문 1은 N이 무한대로 발산할 때 C_N이 C_1, C_2, C_3, C_4, ... 의 문자열을 포함하고 있으므로 임의의 n에대해, n번째 정의된 수열이라면, 문제 0처럼 C_N을 C_n들의 연결로 전개하면 만족하는 i가 무한이 많음을 보일 수 있습니다.
  
  좋아요0
- 여백 패르마 Lv.5 2018.03.13 07:53
  
  0,1 번은 이미 풀렸는데...
  
  좋아요0
- 쌀밥공기 Lv.1 2018.03.13 20:26
  
  muse님의 풀이에서, "k는 n에 따라 달라지기 때문"이라 명시되어있지만 이 문장만으로 강한주기 수열의 주기 P의 존재성을 부정 할 수 없습니다.
  
  좋아요0
김우현 기자 Lv.5 2018.03.16 17:07

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

댓글 작성하기 좋아요0 댓글수0
베네딕트0724 Lv.6 2018.03.16 23:20

제가 전에 했던 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
- 수학자 Lv.2 2018.03.17 11:10
  
  아마 $b_n$ 역시 소인수 2의 개수의 홀짝성임을 보이면 완벽할 것 같습니다.
  
  좋아요0
- 여백 패르마 Lv.5 2018.03.17 19:31
  
  문제에서 $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
수학자 Lv.2 2018.03.17 11:58

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
- 여백 패르마 Lv.5 2018.03.17 20:23
  
  이렇게 풀어도 가능합니다. $\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
여백 패르마 Lv.5 2018.03.18 19:22

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

댓글 작성하기 좋아요0 댓글수0
여백 패르마 Lv.5 2018.03.28 15:40

댓글 작성하기 좋아요0 댓글수1
- 여백 패르마 Lv.5 2018.03.28 15:40
  
  아시겠지만 순서는...
  
  좋아요0
베네딕트0724 Lv.6 2018.03.29 21:43

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
- 베네딕트0724 Lv.6 2018.03.29 22:57
  
  n이 무한으로 가면 안 될 것 같네요. 어쨌든 n에 값과 상관 없이 성립하는 n만 찾으면 될 것 같습니다.
  
  제가 해결하지 못하지라도, 이건 결정적 아이디어가 될 것 같습니다.(뜻 : 제가 풀 자신 없어요.)
  
  좋아요0
김우현 기자 Lv.5 2018.03.30 09:13

(4), (5)번 문제는 현재 멘토 확인 중에 있습니다!!!

댓글 작성하기 좋아요0 댓글수0
구머 Lv.5 2018.04.12 15:25

문제 끌올과 함께..개인적으로 폴리매스 앱이 있었으면 좋겠네요. 아무래도 접속시간이 다르다 보니 의견 교환이 되게 느려지는 것 같아요ㅜ

댓글 작성하기 좋아요0 댓글수2
- 베네딕트0724 Lv.6 2018.04.12 17:53
  
  같은 생각입니다. 그리고 모바일로도 수식 입력을 편하게 할 수 있게 해주셨으면 합니다.. 모바일로는 수식 입력하는 게 일이네요....
  
  좋아요0
- 김우현 기자 Lv.5 2018.04.13 11:33
  
  구머 친구, 수학장 친구 의견 감사합니다~. 모바일앱에 관해서는 적극적으로 논의해 볼게요!
  
  좋아요0
여백 패르마 Lv.5 2018.04.16 15:28

(4)번 은 수학자님이 푸셨지요?...더도 열심히 했는데...

댓글 작성하기 좋아요1 댓글수2
- 베네딕트0724 Lv.6 2018.04.16 21:11
  
  페르마님은 5번에도 도전하셨잖아요. 5번 풀기를 한 번 기대해 봐요.
  
  좋아요0
- 김우현 기자 Lv.5 2018.04.18 10:06
  
  전 여백 패르마 팬이에요 아임 어 빅 팬 오브 유!
  
  좋아요0