본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[슬기로운 수학생활] 슬3. 수열의 세계
수학동아 2020.07.01 11:48

자연수 n\geq 1에 대해 a_{n}을 다음과 같이 정의하자.

 

1. a_1=1

2. 모든 자연수 n\geq 1에 대해 a_{n+1}

(i) 만약 어떤 m< n이 있어서 a_m=a_n이면, 그런 m의 최댓값을 잡고 a_{n+1}=n-m으로 정의한다.

(ii) 그런 m이 없다면 a_{n+1}=0으로 정의하자.

 

 

문제 1 모든 a_i>0인 i에 대해 i-a_i들이 서로 다른 숫자임을 보여라.

 

 

문제 2 이 수열에 0이 무한히 나옴을 보여라.

 

 

문제 3 모든 자연수가 이 수열에 무조건 한 번은 나옴을 보이거나, 절대 나오지 않는 자연수가 하나는 있음을 보여라.

 

 

문제 4 이외에도 이 수열이 가지는 수학적인 성질을 추측해보고, 가능하면 증명해보자.

 

※문제 1번에 수정이 있습니다. a_i>0인 i에 대해서라는 조건으로 변경됐으니 참고해 주세요! 파스칼 친구 관찰에 따라 수정했습니다. 그리고 1번 문제는 파스칼 회원이 해결했습니다. 축하합니다.^^

 

※문제 2번은 리프 친구가 해결한 것으로 확인했습니다. 축하합니다~!

 
  •  
    리프 Lv.6 2020.07.01 14:34

    노가다 해보면 a_3=0, a_4=1이라서 문제 1번을 만족 안 하는 것 같은데 제가 문제를 잘못 이해한건가요?

    댓글 작성하기 좋아요0 댓글수3
    •  
      파스칼 Lv.6 2020.07.01 22:26

      실제로 i=3,4 외에도 i=2,5일 때, 9,19일 때 등 i-a_i가 서로 같은 경우들이 존재합니다. 그러나 이런 경우들의 공통점을 찾아보면 모두 첫번째 a_i가 0이라는 공통점을 갖고 있습니다. 제 생각에 1번 문제는 'a_i가 0이 아닌 모든 i에 대해 i-a_i가 서로 다른 숫자임을 보여라'일 것이라고 생각합니다.

      좋아요1
    •  
      리프 Lv.6 2020.07.01 22:38

      그건 아닌듯 합니다. i=8, 10일 때 i-a_i의 값이 6으로 동일하면서 a_i가 0이 아니네요. 도대체 원래 문제가 뭘까요...

      좋아요0
    •  
      리프 Lv.6 2020.07.01 22:41

      아 제가 잘못 계산했네요 ㅋㅋ 파스칼님의 추측이 맞습니다

      좋아요0
  •  
    해결
    파스칼 Lv.6 2020.07.01 22:37 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      파스칼 Lv.6 2020.07.01 22:38

      1번 문제를 'a_i가 0이 아닌 모든 i에 대해 i-a_i가 서로 다른 숫자임을 보여라' 라고 해석했을 때 1번 문제의 풀이입니다.

      좋아요0
  •  
    리프 Lv.6 2020.07.02 12:48

    oeis에 검색해본 결과 Van Eck's sequence라고 불리는 수열이라네요. 초항에 따라 수열이 다른 형태로 나타나는데 수열의 성질은 모두 동일한듯 합니다. 참고로 oeis 좀 찾아보면 2번과 3번(확실 x)의 증명이 있는 것 같네요. 저는 증명을 아직 안 읽어봤는데 증명이 궁금하신분은 한 번 찾아보시길 바랍니다.

    (2번 증명 되게 짧은 것 같던데 생각보다 안 풀리네요 ㅠ)

    댓글 작성하기 좋아요0 댓글수1
    •  
      리프 Lv.6 2020.07.02 13:33

      위키피디아에 찾아보니 3번은 추측이라고 하네요. 더 나아가 임의의 음이 아닌 정수 쌍 (i, j)가 수열의 연속한 두 항으로 존재한다는 추측도 있네요. (단, (1,1)과 (n, n+1)은 제외)

      좋아요0
  •  
    number0316 Lv.4 2020.07.02 13:01

    제가 볼 때 n이 자연수일 때 a_{20n+16}=0이 되는 것 같습니다. 증명은 아직 하진 못했지만요..

    댓글 작성하기 좋아요0 댓글수1
    •  
      리프 Lv.6 2020.07.02 14:57

      a_56=3이여서 성립하지 않습니다. 아마도 mod로 접근하는 것은 불가능할듯 합니다.

       

      추가) a_36=23이라는 반례도 있네요

      좋아요0
  •  
    해결
    리프 Lv.6 2020.07.02 13:23 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수6
    •  
      리프 Lv.6 2020.07.02 13:24

      2번 풀이입니다.

      어제부터 몇 시간을 고민했는데 생각보다 쉬운 거여서 좀 허무하네요 ㅠ

      좋아요0
    •  
      리프 Lv.6 2020.07.03 18:05

      구글링 해보니 2번 문제의 증명에 대해 설명해놓은 영상이 있네요. 제 증명과 거의 동일하니 궁금하신 분들은 이 영상을 보시기 바랍니다.

      https://youtu.be/etMJxB-igrc

      좋아요0
    •  
      최기자 Lv.4 2020.07.16 22:17

      잘 풀었어요.^^ 다만 김다인 멘토가 다음과 같은 의견을 줬으니 참고하세요.^^

       

      p_i를 정의할 때 a_ia_{i+1}…a_{i+N}라 하면 곱셈으로 오해할 수 있기 때문에 (a_i, a_{i+1}, …, a_{i+N})이라 (N+1)중쌍으로 정의해주는 것이 더 좋을 것 같아요^^ 뒤 논의를 보았을 때 a_j 각각의 정보가 사라지지 않아야 주기임을 보일 수 있겠죠?

      좋아요0
    •  
      리프 Lv.6 2020.07.16 22:32

      피드백 감사합니다! 그런데 '뒤 논의를 보았을 때 a_j 각각의 정보가 사라지지 않아야 주기임을 보일 수 있겠죠?' 의 뜻이 잘 이해가 안 되네요...

      일단 제가 이해한 대로 답을 드리자면 임의의 p_i에 대해 a_j가 p_i의 원소로 존재하기 때문에 모든 순열은 a_j의 정보를 포함하고 있다고 할 수 있습니다.

      좋아요0
    •  
      최기자 Lv.4 2020.09.01 17:20

      김다인 학생에게 리프 학생의 질문을 보내서 답변을 받았어요.^^

       

      처음 읽었을 때 곱셈을 한 것처럼 보였어서 그 부분 서술을 깔끔하게 해줬으면 좋았겠다라고 말했던거였는데 좀 잘라서 말했나봐요,, 사실 그 뒤의 맥락에서 리프학생이 곱샘이 아니라 그냥 나열로서 생각했다는 걸 알았고 그 사실을 덧붙여준거였어요ㅎㅎ

      좋아요0
    •  
      리프 Lv.6 2020.09.04 18:11

      아 곱셈으로 오해할만한 표현이였네요 ㅋㅋ 다음부턴 주의하도록 하겠습니다

      좋아요0
  •  
    구머 Lv.5 2020.07.02 21:43

    1부터 1000까지 an값들

     

    1, 0, 0, 1, 3, 0, 3, 2, 0, 3, 3, 1, 8, 0, 5, 0, 2, 9, 0, 3, 9, 3, 2, 6, 0, 6, 2, 4, 0, 4, 2, 4, 2, 2, 1, 23, 0, 8, 25, 0, 3, 19, 0, 3, 3, 1, 11, 0, 5, 34, 0, 3, 7, 0, 3, 3, 1, 11, 11, 1, 3, 5, 13, 0, 10, 0, 2, 33, 0, 3, 9, 50, 0, 4, 42, 0, 3, 7, 25, 40, 0, 5, 20, 0, 3, 8, 48, 0, 4, 15, 0, 3, 7, 15, 4, 6, 70, 0, 7, 6, 4, 6, 2, 36, 0, 7, 7, 1, 48, 22, 0, 6, 10, 48, 5, 33, 48, 3, 26, 0, 9, 50, 50, 1, 16, 0, 6, 15, 34, 79, 0, 5, 17, 0, 3, 17, 3, 2, 35, 0, 6, 14, 0, 3, 7, 38, 0, 4, 47, 0, 3, 7, 7, 1, 30, 0, 6, 16, 33, 43, 0, 5, 30, 8, 78, 0, 5, 5, 1, 15, 42, 96, 0, 7, 21, 0, 3, 26, 59, 0, 4, 33, 23, 147, 0, 5, 18, 0, 3, 12, 0, 3, 3, 1, 25, 116, 0, 6, 41, 0, 3, 8, 38, 57, 0, 5, 20, 124, 0, 4, 29, 0, 3, 12, 24, 0, 4, 7, 44, 0, 4, 4, 1, 29, 13, 162, 0, 7, 10, 116, 34, 102, 0, 6, 36, 131, 0, 4, 16, 81, 0, 4, 4, 1, 21, 70, 149, 0, 7, 21, 5, 45, 0, 5, 3, 42, 85, 0, 5, 5, 1, 17, 126, 0, 6, 31, 0, 3, 13, 44, 51, 0, 5, 13, 5, 2, 138, 0, 6, 14, 138, 4, 39, 0, 6, 6, 1, 26, 110, 0, 6, 5, 17, 31, 28, 0, 6, 6, 1, 12, 86, 0, 6, 5, 12, 5, 2, 31, 14, 29, 86, 10, 83, 0, 12, 10, 4, 35, 179, 0, 6, 18, 135, 0, 4, 8, 124, 119, 0, 5, 24, 116, 102, 101, 0, 6, 15, 167, 0, 4, 15, 4, 2, 36, 109, 0, 7, 98, 0, 3, 82, 0, 3, 3, 1, 56, 0, 5, 28, 64, 0, 4, 20, 156, 0, 4, 4, 1, 13, 95, 0, 6, 36, 29, 64, 15, 35, 59, 199, 0, 9, 260, 0, 3, 30, 222, 0, 4, 21, 139, 0, 4, 4, 1, 26, 107, 0, 6, 26, 4, 7, 54, 0, 6, 6, 1, 12, 92, 0, 6, 5, 53, 0, 4, 14, 106, 0, 4, 4, 1, 14, 6, 12, 16, 185, 0, 9, 46, 0, 3, 46, 3, 2, 90, 0, 6, 14, 16, 14, 2, 7, 40, 362, 0, 9, 18, 124, 120, 0, 5, 39, 168, 0, 4, 35, 78, 291, 0, 5, 9, 15, 85, 205, 0, 6, 29, 92, 59, 90, 35, 15, 10, 156, 109, 129, 0, 12, 54, 76, 0, 4, 27, 0, 3, 52, 0, 3, 3, 1, 69, 0, 5, 33, 311, 0, 4, 15, 26, 99, 0, 5, 9, 42, 247, 0, 5, 5, 1, 19, 467, 0, 6, 47, 364, 0, 4, 20, 154, 0, 4, 4, 1, 14, 84, 0, 6, 14, 4, 7, 88, 0, 6, 6, 1, 12, 58, 0, 6, 5, 32, 0, 4, 14, 16, 106, 129, 71, 0, 7, 20, 33, 58, 16, 9, 52, 70, 310, 0, 10, 87, 0, 3, 74, 0, 3, 3, 1, 33, 17, 276, 0, 7, 23, 390, 0, 4, 34, 346, 0, 4, 4, 1, 15, 86, 273, 0, 7, 15, 5, 50, 467, 81, 352, 0, 8, 269, 0, 3, 32, 59, 132, 0, 5, 14, 61, 0, 4, 26, 110, 320, 0, 5, 9, 59, 14, 11, 557, 0, 7, 32, 21, 232, 0, 5, 12, 90, 157, 0, 5, 5, 1, 49, 0, 5, 4, 28, 277, 0, 5, 5, 1, 10, 83, 330, 0, 7, 27, 165, 0, 4, 15, 63, 0, 4, 4, 1, 15, 6, 120, 211, 0, 8, 67, 0, 3, 67, 3, 2, 228, 0, 6, 13, 303, 0, 4, 20, 126, 414, 0, 5, 40, 239, 0, 4, 9, 72, 0, 4, 4, 1, 34, 114, 0, 6, 23, 122, 0, 4, 9, 14, 85, 239, 20, 27, 57, 501, 0, 10, 66, 0, 3, 44, 442, 0, 4, 17, 147, 533, 0, 5, 40, 40, 1, 33, 156, 252, 0, 8, 66, 20, 27, 27, 1, 10, 26, 127, 0, 10, 4, 24, 409, 0, 5, 23, 49, 113, 0, 5, 5, 1, 17, 35, 282, 0, 7, 109, 282, 4, 19, 250, 0, 7, 7, 1, 14, 65, 0, 6, 74, 206, 0, 4, 14, 8, 46, 344, 0, 6, 10, 41, 581, 0, 5, 34, 93, 0, 4, 15, 131, 553, 0, 5, 9, 94, 0, 4, 9, 4, 2, 131, 11, 185, 377, 0, 9, 8, 32, 187, 0, 5, 18, 365, 0, 4, 16, 262, 0, 4, 4, 1, 56, 465, 0, 6, 46, 50, 236, 0, 5, 19, 71, 284, 0, 5, 5, 1, 16, 22, 728, 0, 7, 78, 386, 0, 4, 26, 111, 0, 4, 4, 1, 15, 64, 478, 0, 7, 15, 5, 23, 115, 0, 6, 38, 660, 0, 4, 16, 30, 483, 0, 5, 13, 200, 0, 4, 9, 71, 46, 53, 467, 289, 0, 8, 77, 0, 3, 175, 0, 3, 3, 1, 40, 170, 0, 6, 33, 172, 0, 4, 24, 160, 0, 4, 4, 1, 14, 133, 0, 6, 14, 4, 7, 56, 92, 447, 0, 8, 34, 134, 0, 4, 10, 143, 0, 4, 4, 1, 22, 90, 303, 257, 0, 8, 16, 67, 269, 340, 0, 6, 30, 72, 255, 0, 5, 73, 0, 3, 57, 243, 0, 4, 25, 757, 0, 4, 4, 1, 30, 18, 148, 0, 7, 50, 137, 0, 4, 10, 45, 716, 0, 5, 27, 240, 0, 4, 9, 100, 0, 4, 4, 1, 24, 82, 632, 0, 7, 24, 5, 17, 238, 0, 6, 53, 114, 302, 0, 5, 9, 22

     

    python코딩으로 구하였음, 참고바람

    댓글 작성하기 좋아요0 댓글수0
  •  
    리프 Lv.6 2020.07.02 23:19

    참고로 2번과 같은 논리에 의해 수열 a_n은 유계수열이 아님을 알 수 있습니다. (임의의 N에 대해 a_m>N인 m이 반드시 존재)

    또한, 이를 통해 자명하게 주기수열이 아님을 알 수 있습니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      무한대의끝을본남자 Lv.7 2020.07.05 12:47

      혹시 아래로 유계나 위로 유계라면 수렴해서 풀긴쉬운데 ㅠ 

      좋아요0
  •  
    리프 Lv.6 2020.07.20 22:18

    정답 처리 된 2번 풀이입니다.

    시간도 많이 지났고 딱히 건드는 사람이 없는 것 같아서 그냥 공개하겠습니다.

     

    풀이) 귀류법으로 0의 개수가 유한하다고 가정하자.

    a_x가 마지막으로 나타나는 0이라고 할 때, N=max{a_1, a_2, ..., a_x}라고 정의하자.

    이때, 만약 a_i>N (단, i>x)인 i가 존재한다면, a_(i+1)=0이 되어 모순이다.

    따라서, 임의의 i에 대해 a_i는 N 이하임을 알 수 있다.

     

    이제, 다음과 같은 순열 p_i를 정의하자.

    p_i=a_ia_{i+1}\cdots a_{i+N}

    수열의 임의의 원소는 N이하이므로, a_(i+N+1)의 값도 N이하일 것이고, 이는 p_i에 있는 원소 중 a_(i+N)의 값을 가지는 a_j가 존재한다는 뜻이다. (단, j는 i+N과 다르다.)

    즉, 임의의 p_i가 주어져 있다면 반드시 a_(i+N+1)의 값이 결정됨을 알 수 있다.

    또한, a_x 이후의 수열의 임의의 원소는 1이상 N이하이므로, p_i로 가능한 순열의 개수는 N^(N+1)개로 유한하고, 이를 통해 어떤 k와 l이 존재하여, p_k=p_l (단, x<k<l)을 만족함을 알 수 있다.

    따라서, 수열 a_n은 어떤 항 a_k 부터 길이 t의 주기를 갖는 수열임을 알 수 있다.

     

    이제, 이 사실을 통해 모순을 유도하자.

    주기가 나타나는 최초의 항을 a_k, 주기의 길이를 t라고 하자. (위에서 언급한거랑 동일)

    이때, a_(k+t-1)=a_(k+t-1+y)인 최소의 자연수 y를 정의하자.

    a_(k+t-1)=a_(k+2t-1)이므로 y가 존재함을 알 수 있다.

    따라서, a_(k+t+y)=y이고, 주기성에 의해 a_(k+y)=y 이다.

    이를 통해 a_(k-1)=a_(k-1+y)임을 알 수 있고, a_(k-1+y)=a_(k+t-1+y)이므로 a_(k-1)=a_(k+t-1)이 되어 주기가 나타나는 최초의 항이 a_k라는 것에 대해 모순이다. (무한강하와 동일한 논리)

     

    따라서, 0의 개수는 무한하다.

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

  • ☎문의 02-6749-3911