본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대35. 무리수 덧셈으로 나타나는 수열 세기
수학동아 2019.11.01

0과 1 사이의 두 실수 a와 b가 있다고 하자. 그러면 양의 실수 x와 자연수 n에 대해 다음 수열을 생각해 볼 수 있다.

 

x_n=\left\{\begin{matrix} 1, \left \{ x+na\right \}< b & \\ 2, \left \{ x+na \right \} \geq b & \end{matrix}\right.

이때, 실수 x에 대해 \left \{ x \right \}는 실수 x의 소수 부분을 나타낸다. 예를 들어 \left \{ 2, 5 \right \}=0.5, \left \{ \sqrt{2} \right \}=\sqrt{2}-1이다. 실수 x를 넘지 않는 최대 정수를 \left [ x \right ]라고 하면, \left \{ x \right \}=x-\left [ x \right ]라고 쓸 수도 있다. 수열 x_n은 x+na의 소수 부분만 생각한 값이 b보다 작은지 큰지를 알려주는 값이다.

 

x가 변할 때마다 당연히 수열 x_1, x_2,\cdots이 변한다. 그런데 각각의 x_i는 1 또는 2의 값만 가지므로, 자연수 n이 정해지면 수열 x_1\cdots x_n이 나올 경우의 수는 많아야 2^n개 뿐이다. 실제로는 2^n개보다 훨씬 적은데, 이번 문제는 다양한 a, b에 대해 이 경우의 수를 세는 것이 목적이다. 자연수 n에 대해 수열 x_1\cdots x_n(단, x는 양의 실수)의 경우의 수를 f(n)이라 하자.

 

f(n)=집합 {x_1x_2\cdots x_n:x는 양의 실수\right \}}의 원소의 수

=양의 실수 x가 변할 때 가능한 모든 수열 x_1\cdots x_2의 수일 때

 

1. a가 유리수이면, 모든 자연수 n에 대해 f(n)\leq M을 만족하는 수 M이 있음을 보여라.

 

2. a=b가 무리수이면, 모든 자연수 n에 대해 f(n)=n+1임을 보여라.

 

3. a, b가 무리수이고, 어떤 자연수 k에 대해 \left \{ka \right \}=b라 하자. 이때, 충분히 큰 모든 자연수 n에 대해서 f(n)은 일차함수가 된다. 이 함수 f(n)을 구하라.

 

4. a, b가 무리수이고, 모든 자연수 k에 대해 \left \{ka \right \}\neq b라 하자. 이때, 충분히 큰 모든 자연수 n에 대해 f(n)은 다항식이 된다. 이 다항식 f(n)을 구하라.

 

 

  •  
    21세기오일러 Lv.11 2019.11.01

    국가수리과학연구소는 언제 나오나요?

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

    현재 국가수리과학연구소 문제 출제가 늦어지고 있습니다. 문제가 도착하는 대로 업로드하겠습니다. 출제 전 업로드 일정이 나오면 다시 공지할게요~ㅜㅜ

    댓글 작성하기 좋아요0 댓글수2
    •  
      21세기오일러 Lv.11 2019.11.01

      알겠습니다. 대한수학회 문제는 이해가 안 되서 국가수리과학연구소 문제를 주로 기다려요.

      좋아요0
    •  
      뉴_턴 Lv.8 2019.11.14

      저도요...... ㅠㅠ

      좋아요0
  •  
    퍼즐-Scratch Lv.4 2019.11.01

    1. a를 기약분수 형태로 나타내어 \frac{p}{q}가 되었다면, x_n의 정의에 따라 x_{n+q} = x_n임을 알 수 있습니다. n이 q 이하의 자연수인 경우 f(n) \leq 2^n \leq 2^q이 성립하고, n이 q보다 큰 자연수인 경우 x_1부터 x_q까지의 q개의 항이 정해지면 그 뒤의 항들도 자동으로 결정되므로 f(n) \leq({x_1} , \cdots , x_q)를 정할 수 있는 가짓수 \leq 2^q가 성립합니다. 따라서 임의의 자연수 n에 대해 f(n) \leq 2^q가 성립합니다. 

    댓글 작성하기 좋아요0 댓글수0
  •  
    나랃말싸미 듕귁에 Lv.11 2019.11.05 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
  •  
    나랃말싸미 듕귁에 Lv.11 2019.11.06

    문제가 무슨 말인지 모르겠어요ㅠㅠ 국가수리과학연구소는 그나마 이해까지는 되는데..

    댓글 작성하기 좋아요0 댓글수2
    •  
      B.C.I.수학장 Lv.5 2019.11.06

      천천히 읽어보시면 이해가 될 거예요!! 국가수리과학연구소 문제가 이해하기는 쉽죠ㅠㅠ 그런데 이해하고 나서 푸는 거는 국가수리과학연구소 문제가 더 어려워요ㅠㅠ 전 대한수학회식 문제도 재밌고 좋더라구요.

      좋아요0
    •  
      리프 Lv.6 2019.11.17

      솔직히 대한수학회 문제는 이해만 하면 그래도 접근은 가능한데 국가수리과학연구소는 아예 접근도 힘든 문제들이 많은 것 같아서 저는 대한수학회 문제를 좋아해요

      좋아요0
  •  
    Simon Lv.2 2019.11.09 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      Simon Lv.2 2019.11.09

      사소한 사실 하나때문에 서술 막혀서 수정중에 있습니다ㅠㅠ

      빨리 완료하고 올리겠습니다.

      3번답은 n+k, 4번답은 2n입니다

      (+다른분이 푸셨길래 가만히 있겠습니다

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

    음... 힌트라고 할 것도 없이 쉬운 아이디어지만 이 아이디어를 공유하고 싶어요.

     

    x가 0일 때 수열을 생각한 후 부터 시작해서 수열이 달라질 때까지 x를 증가시키세요. x가 1이 되면 다시 처음의 수열로 돌아옵니다. 그러면 수열이 바뀐 횟수를 세면 되는데, 이걸 이용하면 2번 문제는 쉽게 풀립니다. 2번 문제가 성립하는 예시를 하나 보여드릴게요. a가 sqrt(2)이고 n이 2라고 합시다. 처음 수열은 당연히 22, x를 증가시키다 보면 21이 되고, 더 증가시키면 12가 되고, 계속 증가시키면 다시 22로 돌아옵니다. 그러면 수열은 22, 21, 12 3가지이므로 f(n)=n+1이죠.

    댓글 작성하기 좋아요0 댓글수2
    •  
      B.C.I.수학장 Lv.5 2019.11.19

      문제가 어려우신 분들 이렇게 한 번 접근해보세요! 2번은 쉽답니다.

      좋아요0
    •  
      김우현 기자 Lv.4 2019.11.29

      좋아요0
  •  
    B.C.I.수학장 Lv.5 2019.11.24
    확인요청중

    시간이 많이 지났으니 공개댓글로 2번을 풀겠습니다. n=1일 때 수열은 1, 2 두 가지이므로 f(n)=n+1이 성립합니다.

    n=k일 때 f(k)=k+1이라고 합시다. 그러면 f(k+1)=k+2임을 증명한다면 모든 자연수 n에 대하여 f(n)=n+1이 성립하게 됩니다.

     

    x=0일 때를 처음 수열이라고 합시다. x=1까지 증가시킬 때 x_{k+1}은 처음 수(1이라고 합시다.)에서 1->2->1 두 번 바뀝니다. 그러면 가능한 수열은 2개가 늘어났습니다. 그런데, \left \{ x+ka \right \}=a라면, \left \{ x+(k+1)a \right \}=x+(k+1)a-\left [ x+(k+1)a \right ]=a이므로 x+ka-\left [ x+(k+1)a \right ]=0이고, \left [ x+(k+1)a \right ]가 정수이므로 x+ka 또한 정수입니다. 따라서 \left \{ x+ka \right \}=0이고, 정의에 의해 x_{k}=1이 되는 순간 x_{k+1}=2가 되는 것입니다. x_{k}는 원래 있던 것이니까 이 때의 x는 이미 있었고, 새로운 경우는 2->1 이 경우 뿐이죠. a는 무리수이기 때문에 이 때 다른 항이 변하지 않는 것은 자명합니다. 

     

    새로운 경우가 하나 생겼으므로 f(k+1)=f(k)+1=(k+1)+1=k+2. 수학적 귀납법에 의해 모든 자연수 n에 대해 f(n)=n+1이 됩니다.

    댓글 작성하기 좋아요1 댓글수5
    •  
      B.C.I.수학장 Lv.5 2019.11.25

      3. x_1x_2...x_k를 생각해보자. x를 0부터 1까지 증가 시켰을 때 수열이 바뀌는 지점은 x=\left \{ -a \right \},\left \{ -2a \right \},...,\left \{ -ka \right \},\left \{ (k-1)a \right \}, \left \{ (k-2)a \right \}, ...,\left \{ a \right \}, 0일 때이다.

      (\left \{ x+a \right \}, \left \{ x+2a \right \}, ..., \left \{ x+ka \right \}가 \left \{ ka \right \} or\0이 되는 지점)

      a가 무리수이므로, x들은 모두 다르다. 그러면 수열이 2k번 바뀌므로, 수열은 2k개 존재한다. (처음 수열과 마지막 수열은 한 번 순환했으므로 같다.) 즉 f(k)=2k이다.

       

      이번에는 x_1x_2...x_kx_{k+1}을 생각해보자. x_{k+1}이 바뀌는 지점은 x=\left \{ -(k+1)a \right \}, \left \{ ka-(k+1)a \right \}=\left \{-a \right \}일 때이다. 여기서 \left \{ -a \right \}는 이미 있던 값이다. 따라서 x는 2k+1번 바뀐다. 일반적으로 k보다 큰 자연수 m에서, x_m이 바뀌는 지점은 x=\left \{ -ma \right \}, \left \{ (k-m)a \right \}이다. 여기서 \left \{ (k-m)a \right \}는 x_{m-k}가 바뀌는 지점과 동일하다. 따라서 x_1x_2x_3...x_{m-1}과 비교했을 때, x_1x_2x_3...x_{m}은 수열이 바뀌는 지점이 한 개 증가한다.

       

      f(k)=2k이고 k보다 큰 자연수 m에 대하여 f(m)=f(m-1)+1이므로 k보다 큰 모든 자연수 n에 대하여 f(n)=n+k이다. 

       

      4. 문제가 잘못됐습니다.b=\left \{ -a \right \}일 때 조건을 만족하지만 b=\left \{ -a \right \}일 때와 b\neq \left \{ -a \right \}일 때 f(n)이 다릅니다. 모든 자연수 k 대신 모든 정수 k라고 하고 문제를 풀겠습니다.

       

      x_1x_2...x_n에서 수열이 바뀌는 지점은 x=\left \{ b-a \right \}, \left \{ b-2a \right \}, ..., \left \{ b-na \right \}, \left \{ -a \right \}, \left \{ -2a \right \},...,\left \{ -na \right \}이므로 총 2n가지 입니다. b=\left \{ -a \right \}이면 안 되는 이유이기도 합니다. \left \{ b-a \right \}=\left \{ \left \{ -a \right \}-a \right \}=\left \{ -a+\left [ -a \right ] -a\right \}=\left \{ -2a \right \}이기 때문에 공통되는 지점이 계속해서 나타나기 때문이죠. 그러면, 모든 자연수 k에 대해 b\neq \left \{ ka \right \}라고 해봅시다. 저 지점들 중 공통되는 것이 없다면 f(n)=2n입니다. 일단, a는 무리수이기 때문에 \left \{ -a \right \}, \left \{ -2a \right \},...,\left \{ -ka \right \}가 모두 다른 것은 자명합니다. 만약 같은 지점이 있다면 어떤 자연수 l,m에 대해 \left \{ b-la \right \}=\left \{ -ma \right \}이겠죠. 이런 l, m이 존재한다고 가정합시다.

      b-la-\left [ b-la \right ]=-ma-\left [ -ma \right ]

      b=-ma+la-\left [ -ma \right ]+\left [ b-la \right ]

      \left \{ b \right \}=\left \{-ma+la-\left [ -ma \right ]+\left [ b-la \right ] \right \}=\left \{ -ma+la \right \}=\left \{ (l-m)a \right \}

      l,m이 자연수이므로 l-m은 정수이다. 그러면 b\neq \left \{ ka \right \}에 어긋나므로 모순입니다. 따라서 이런 l, m은 존재하지 않습니다.

       

      그러므로 x=\left \{ b-a \right \}, \left \{ b-2a \right \}, ..., \left \{ b-na \right \}, \left \{ -a \right \}, \left \{ -2a \right \},...,\left \{ -na \right \}는 모두 다른 값이고, x가 증가하면서 수열이 2n번 바뀝니다. 처음과 끝 수열은 같으므로 f(n)=2n입니다.

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

      '수열이 바뀔 때 전에 나왔던 수열이 다시 나오지 않는다'라는 가정을 깔고 증명했습니다. 그럼 이것을 증명하겠습니다.

      편의를 위해 x_1x_2...x_n를 다음과 같은 규칙으로 재배치합시다.

      1) 처음 값이 1인 것을 앞으로, 2인 것을 뒤로 옮긴다.

      2) 처음 값이 1, 2인 부분 각각을 x가 증가할 때 먼저 바뀌는 순서대로 바꾼다.

       

      그렇게 만든 수열을x_{\alpha1}x_{\alpha 2}...x_{\alpha a}x_{\beta 1}...x_{\beta b}(a+b=n)(여기서 알파가 붙은 것은 처음 값이 1인 것, 베타가 붙은 것은 처음 값이 2인 것입니다. 알파가 붙은 것부터 봅시다. 처음에는 11....1이었다가 21....1, 221....1, 이렇게 앞에서부터 바뀝니다. 이게 다시 12..21...1로 바뀐다고 해도 맨 처음 값이 다시 2로 바뀌려면 x가 1 이상 증가해야 합니다. 그러면 알파가 붙은 수열은 바뀔 때마다 모두 각각 다릅니다. 베타가 붙은 수열도 같은 논리를 사용할 수 있습니다. 따라서 같은 수열은 나타나지 않습니다.

       

      음... 111111 211111, 221111, 122111, 122211, 112211, 112221, 111221, 111222, 111122, 111112은 모두 다르다 이런 겁니다.

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

      음... 이번에 수학동아에 이 문제에 달린 코멘트를 보면 제 생각이 잘못된 것 같은데요... 어디가 잘못된지 잘 모르겠네요...

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

      -a의 소수부 계산을 실수한 것 같네요. 다시 생각해서 수정한 풀이 올릴게요! 그리고 다른 곳도 틀린 논리가 있나 살펴보도록 할게요!

      좋아요0
    •  
      최기자 Lv.4 2020.02.05

      주정훈 멘토가 검토한 결과 2번은 잘 푼 것 같다고 합니다. 다른 문제도 다시 수정해서 도전해 보세요~!^^

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

  • ☎문의 02-6749-3911