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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대11. 굴림시행 즐기기

2017.10.31

같이 풀어볼까?

네이버밴드 구글플러스

양의 정수 \large n (n \ge 2)이 주어져 있다.

좌표평면 상의 부분집합 \large S_n= \left \{(a,b) \neq (0,0) : 0 \leq a,b \leq n-1, a,\, b는 정수}의 원소 \large (a, b)

로 보내는 시행을 "굴림시행"이라고 정의하자. 또한 점 \large (a, b)에 굴림시행을 \large k번 적용해 얻어지는 점을 \large Q_n^k(a,b)라 정의하자.

 

예를 들어 \large Q_5(3,1)=(4,3), \, Q_5^2(3,1)=(2,4), \large \,Q_5^3(3,1)=(1,2), \, Q_5^4(3,1)=(3,1)이 된다.

 

임의의 점 \large (a,b) \in S_n에 대해 \large \mathbf Q_n(a,b):=\{ Q_n^k(a,b) : k\ge 1\}, \,\, q_n(a,b)=\vert\mathbf Q_n(a,b)\vert라 정의하고, 

\large r_n(a,b)\large Q_n^k(a,b)\large y좌표가 0이 되는 양의 정수 \large k가 존재할 때, 가장 작은 양의 정수 \large k라 정의하자.

 

위의 예에서 보듯이 \large q_5(3,1)=4이고 \large r_5(3,1)는 존재하지 않는다. 또한 \large \large q_5(1,1)=20,\, r_5(1,1)=5임을 쉽게 확인할 수 있다.   

 

문제1. \large \mathbf Q_n(a,b)=S_n이 되는 점 \large (a, b)가 존재하는 정수 \large n을 모두 구하여라.

 

문제2. 정수 \large n=p가 소수일 때 \large r_p(1,1)이 항상 존재함을 보이고, \large \displaystyle\frac{q_p(1,1)}{r_p(1,1)}을 구하여라. 

댓글 52

  • shine 2017.10.31 20:40:00

    일단, Q_n(a,b)는 일대일대응입니다. Q^{-1}_n(a,b)= \left\{\begin{matrix} (b,a-b) \\ (b,a-b+n) \end{matrix}\right.이라는 역함수가 존재하기 때문입니다.

    좋아요0 댓글수0
  • 여백 패르마 2017.11.01 17:58:31

    저는 2번에 집중해 봤습니다..   그 굴림시행한 것의 x좌표는 피보나치 수를 n으로 나눈 나머지와 같습니다. 또, y좌표가 0이 되려면 x좌표가 0이 되어야 합니다. 즉, 모든 소수 p에 대해 피보나치 수중 p의 배수가 되는 피보나치 수가 2개가 있다는 것을 증명하면 된다. (p의 배수 번수의 피보나치 수는 p의 배수인 피보나치 수 2개의 최대 공배수이다. Fgcd(m,n)=gcd(Fm,Fn)이다.)

    좋아요0 댓글수4
    • 구머 2017.11.01 18:21:30

      저랑 같은 생각을 하셨네요. 근데 마지막 괄호 안에 있는 말은 잘 이해가 안 되는군요. 먼저 피보나치 수열 중 p의 배수가 있다는 것을 보입시다.

      피보나치 수열을 mod p로 봅시다. 이때, 피보나치 수열은 무한하기 때문에 이웃한 두 피보나치 수가 mod p로 같은 순서쌍 2개가 존재합니다. 즉, 순환마디가 존재합니다. 그런데 피보나치수의 특징상 이웃한 수 2개가 정해지면 그 두 수 바로 앞에 있는 수는 유일하게 결정되므로, 여기서 맨 앞의 1,1 또한 맨 앞이 아닌 어느 순환마디 안에 속해있음을 알 수 있습니다. 이때, 1,1앞에 있는 수는 mod.p로 0이고, 따라서 이 수는 p의 배수입니다.

       

      좋아요0
    • 구머 2017.11.01 18:22:48

      1을 첫번째 피보나치 수라고 하고, n번째에 p의 배수가 되는 피보나치 수가 있다 가정하면, 2n..3n..4n....,.번째 피보나치 수는 자명하게 p의 배수가 됩니다.

       

      좋아요0
    • 여백 패르마 2017.11.02 15:34:02

      즉,  제 아이디어와 구머님의 증명을 합하면 2번을 반 증명한것인가요??

      좋아요0
    • 구머 2017.11.02 16:41:46

      네 증명이 된거죠. 근데 사실 제가 쓴 건 그냥 말로 때웠다고 해도 별로 할말이 없어서..이제 살짝 구체적으로 설명하면 될 것 같아요.

      좋아요0
  • 여백 패르마 2017.11.02 18:01:59

    굴림시행을 한 것의 x좌표는 피보나치 수를 p로 나눈 것과 같으니 피보나치 수에 언제나 소수 p의 배수기 있다는 것을 증명하면 된다. 피보나치 수는 무한하기 때문에 순환하는 것이 있다. 1,1은 순환 주기에 있을 것이고 (mod p) 그러면 그 1,1전 수는 p의 배수가 된다. 즉, 2번 반절 증명!(이게 맞나요???)

    좋아요0 댓글수5
    • 구머 2017.11.02 18:06:44

      네(사실 문제조건은 y좌표가 0이 되어야 한다고 하지만, x좌표가 0 이면 그 전상태는 y좌표가 0인 상태일 것이니 문제가 되지 않음)

      좋아요0
    • 여백 패르마 2017.11.03 14:47:23

      그런데 꼭 무한하다고 순환한다는 것을 증명해야 되지 않을까요?

      좋아요0
    • 구머 2017.11.04 14:13:23

      By 비둘기집의 원리 로 성립.

      좋아요0
    • 미래탐정 2017.11.11 01:22:04

      비둘기집의 원리를 이용한 증명은 잘 알지 못합니다만 피사노의 주기라고 피보나치 수열에서 mod n값이 (소수가 아니여도 되요) 순환한다는 내용이 있습니다

       

      좋아요0
    • 여백 패르마 2017.11.12 09:19:32

      오옷  정보 감사합니다.

       

      좋아요0
  • 여백 패르마 2017.11.03 14:37:58

    저는 qp(1,1)을 구해봤습니다. 

    p=2,3,5,7,11,13,17,19,23일때 qp(1,1)은 3,6,20,16,10,33,36,17,88이라고 나왔네요...

    좋아요0 댓글수2
    • 여백 패르마 2017.11.05 08:39:38

      또 n=29일 때는  그 값이 13이라고 나오네요.

      좋아요0
    • 여백 패르마 2017.11.05 11:02:26

      그래서 도대체 어떻게 함수를 구할 수 있을 까요??(제가 아는 이런 함수는 뫼뷔우스 함수를 더한 함수 밖게 없습니다....)

      좋아요0
  • 여백 패르마 2017.11.05 09:51:07

    수학동아님 구머님과 저의 2번 반절이 맞는 지 좀 해주세요

    좋아요0 댓글수0
  • 수돌이 2017.11.05 13:02:36

    2번문제 아이디어 더합니다.

    //구머//

    피보나치 수열을 mod p로 봅시다. 이때, 피보나치 수열은 무한하기 때문에 이웃한 두 피보나치 수가 mod p로 같은 순서쌍 2개가 존재합니다. 즉, 순환마디가 존재합니다. 그런데 피보나치수의 특징상 이웃한 수 2개가 정해지면 그 두 수 바로 앞에 있는 수는 유일하게 결정되므로, 여기서 맨 앞의 1,1 또한 맨 앞이 아닌 어느 순환마디 안에 속해있음을 알 수 있습니다. 이때, 1,1앞에 있는 수는 mod.p로 0이고, 따라서 이 수는 p의 배수입니다.

     

    여기서 r_p(1,1)에 대한 문제조건이 틀렸습니다. (문제를 풀 수 없습니다)

    문제에서 r_5(1,1)=5라고 나와있으나, 실제로는 (2,1), (3,2), (0,3), (3,0)으로 4입니다. 따라서 \large r_n(a,b)는 \large Q_n^i(a,b)의 \large y좌표가 0이 되는 양의 정수 i가 존재할 때, 가장 작은 양의 정수 i+1이라 정의합니다.

    그러면 r_p(1,1)은 피보나치 수열을 mod p으로 보았을 때, 처음 0이 나올 때까지의 항의 수가 됩니다. 예) 1,1,2,3,0이면 r_5(1,1)=5

    처음 0이 나온 바로 그 다음 항을 k라고 합시다. 피보나치 수열은 인접한 두 항이 주어지면 바로 앞의 항도 유일하게 결정되므로

    0,1,1,2,3,......,0,k로 진행된다고 해도 무방합니다. 0,k이후의 항은 0,1 이후의 항에 모두 k를 곱한 것을 mod p로 보았을 때와 같은 항들이 나옵니다.

    따라서 다시 r_p(1,1)개의 항들이 지나면 0,k^2가 나오고, 이를 반복하여 k^a=1 (mod p)가 되는 가장 작은 정수 a가 나올 때까지 진행합니다.

    다음부터는 다시 0,1,...로 피보나치 수열이 반복되며, 따라서 그 때  \large \displaystyle\frac{q_p(1,1)}{r_p(1,1)}의 값은 a가 됩니다.

    a는 무엇이냐? ord_p(k)입니다. 얘가 항상 p-1이 된다던가 그런건 좀 더 생각해봐야겠습니다.

    좋아요0 댓글수4
    • 구머 2017.11.05 13:23:15

      제가 1번 풀면서 ord p k가 1, 2, 4밖에 되지 않음을 증명했고 따라서 1번에서 n은 2,3밖에 안 됨도 증명이 됩니다.(5는 아쉽게도 안되더군요) 하지만 1,2,4가 나오는 패턴은 아직 잘 모르겠네요.

      그리고 문제 수정은 Q집합을 k>=0을 범위로 해야 할 것 같습니다..

      좋아요0
    • 여백 패르마 2017.11.05 13:45:12

      p가 k와 서로소이기 때문에 페르마의 소 정리에 의해 당연해집니다. 하지만 k가 p의 배수라면 모르겠네요.

      좋아요1
    • 구머 2017.11.05 13:47:51

      Ord p a\leq4인 것과 p와 k가 서로소인 것이 어떻게 연결이 되죠

      좋아요0
    • 여백 패르마 2017.11.05 13:50:33

      결론으로 봅시다. 

      a^k=1(mod n)이 언제나 p-1인지 생각해야 한다고 써져 있습니다. 그걸 페르마의 소정리로 한 것이 지요.

      좋아요0
  • 여백 패르마 2017.11.05 14:39:13

    정리합시다.      

    굴림시행할 때 x좌표는 피보나치 수를 p로 나눈 나머지입니다.그리고 피보나치 수는 무한하기 때문에 주기가 존재합니다. 그렇기 때문에 1전에 것은 p의 배수가 됩니다. 그렇기  때문에 언제나  x좌표는 0이 될 수 있고, 즉 y좌표가 0이 될 수 있습니다.

    또, r-p(1,1)의 수 뒤에는 (피보나치 수에서 0뒤에 수가 k라고 하면)k^2가 되고, 계속 그러면 k^a(a번 했다.) 가 나온다. 즉, q어쩌고는 a이다. (k^a=1 in mod p이여야 한다. 언제나 a가 p-1이면 된다. 

    이건가요???

    좋아요0 댓글수1
    • 구머 2017.11.05 15:01:45

      a가 p-1이면 당연히 되겠죠. 근데 p-1보다 더 작은 수가 a여도 성립을 하니까..

      좋아요0
  • 구머 2017.11.05 16:56:38

    좋아요0 댓글수4
    • 구머 2017.11.05 16:58:50

      원래 비밀댓으로 하려 했으나 2번 푸는 데 필요할 것 같아 공유합니다. 이해 안되거나 글씨 못 알아보는 부분은 대댓으로 알려주세요~

      좋아요0
    • 수학동아 2017.11.06 10:24:26

      이미지 파일로 올린 풀이를 첨부파일 형태로 다시 올려주실 수 있나요? 이미지는 올라갈 때 자동 리사이즈 되서 확대해서 보면 글이 깨져서요. 첨부파일로 올려주시면 풀이를 보기가 더 좋을 것 같습니다. ^^

      좋아요0
    • 여백 패르마 2017.11.10 21:16:33

      과연 풀린 건가요?

       

      좋아요1
  • 구머 2017.11.09 18:55:06

    2번 진행상황: 소수 p에 대해 p의 배수가 a번째에 나타난다면, 

    a=4k+2이면 답이 1, a=4k이면 답이 2, a=4k+1,3이면 답이 4.

    좋아요0 댓글수4
    • 여백 패르마 2017.11.10 19:58:22

      그런데 a=4k 또는 4k+2이면 안 되는 돼요.

      4k,4k+2는 2로 나눠지고 그러면 2k,2k+1번의 피보나치 수는 4k,4k+2의 번호의 피보나치 수 의 약수이기 때문에 소수가 되지 않습니다.

      좋아요0
    • 구머 2017.11.10 20:18:18

      2k+1,2k번째 피보나치 수가 4k,4k+2번째 피보나치 수의 약수가 되는 이유가 뭐죠?

      그리고 a=4k, 4k+2번째 피보나치 수가 p의 배수가 되어야 한다고 했지 p가 되어야 한다고는 하지 않았습니다.

      좋아요0
    • 여백 패르마 2017.11.10 20:22:46

      앗!!!!!!!!

      그리고 루카스 수열이라는 것이 있는 데   FnLn=F2n입니다.(Ln= 루카스 수열)

      좋아요0
    • 구머 2017.11.10 21:22:36

      오 ㅋㅋ몰랐네요 정보 감사합니다.

      좋아요0
  • 여백 패르마 2017.11.10 20:00:32

    수학동아님    구머님의 1번, 저와 구머의 2번 반절 좀 체크 해주세요.

    좋아요0 댓글수1
    • 고은영 기자 2017.11.13 18:06:18

      확인 중입니다. 잠시만 기다려 주세요~:) 

      좋아요0
  • immanuel 2017.11.12 09:09:38 비밀댓글
    비밀댓글 입니다.
    댓글수3
    • 구머 2017.11.12 11:58:07

      오오 2번 하심?

      좋아요0
    • 고은영 기자 2017.11.13 18:11:17

      다른 질문입니당 smiley

      좋아요0
    • 고은영 기자 2017.11.13 18:20:29 비밀댓글
      비밀댓글 입니다.
  • 여백 패르마 2017.11.13 20:11:37

    구머님께서 말하신 2번 전광판에서 4k번쩨가 p의 배수이려면 8k번째의 피보나치 수와 12k번째의 피보나치 수의 공배수가 p이여야 합니다.

    좋아요0 댓글수2
    • 여백 패르마 2017.11.13 20:18:24

      왜냐하면 이 문제의 두번째 덧글 의 과로 안의 말에 의해서 이지요.)

      좋아요0
    • 구머 2017.11.13 20:57:47

      자명하지 않나요..?

      좋아요0
  • 구머 2017.11.15 21:06:28

    1번 풀이의 첫번째 페이지에서 언급하였던 아이디어:소수 p와 서로소인 어떤 두 자연수 a, b에 대해, (a, b)에 어떤 수를 곱해 mod p로 (1, n)이 된다면, (a, b)이 집합 Sp(n) 안에 포함된다고 정의하자.(예를 들어서, (3, 7)은 mod 11에서 S11(6)이 됨을 알 수 있다.)

    이제 편이상 Sp(n)에 속하는 원소를 n순서쌍이라고 부르도록 하겠습니다.

    이제 제가 발견한 성질을 소개하겠습니다.(단, 아직 이 성질을 증명하지 못 한 상태라서 반례가 존재할지도 모릅니다.)

    피보나치 수열은 초항 2개가 1,1입니다. 즉, 제일 먼저 나오는 순서쌍은 1순서쌍입니다. 이제 피보나치 수열을 계속 관찰하다 보면, 또다른 1순서쌍이 나오게 됩니다. 이때, 제일 처음 1순서쌍에서 다음 1순서쌍 사이에 있는 원소의 개수를 n이라고 합시다.(예를 들자면, p=5라고 하면, 1,1,2,3,5,8,13에서 1,1과 8,13은 둘다 1순서쌍이고, 두 순서쌍 사이에는 (1,1)(1,2)(2,3)(3,5)(5,8)이렇게 5개의 순서쌍이 존재하므로 n=5입니다.)

    이제 초항이 1,1이 아닌 수열을 따져봅시다. 즉, 초항이 1,a인 것을 봅시다. 이때, 제가 추측중인 것은 모든 자연수 a에 대해서 제일 처음 나온 a순서쌍과 다음 ,a순서쌍 사이에 있는 순서쌍의 개수는 모두 같다는 것입니다. 단, 반례가 존재하는데, mod 19에서 1,5가 초항인 경우를 보면, 1,5 다음 순서쌍, 즉 5,6 또한 5순서쌍이 됩니다. 이렇게 모든 순서쌍의 종류가 같은 경우만 제외한다면 그 외의 경우는 분명 길이가 다 같을 것입니디

    좋아요0 댓글수2
    • 여백 패르마 2017.11.17 14:29:50

      모든 a의 약수가 아닌 p에 대해 a^p-1은 mod p에서 1입니다. 그래서 그 수를 b에 곱한 수가 n이 되지 않나요???

      좋아요0
    • 구머 2017.11.17 14:59:31

      추측은 증명 완료, 그리고 a^p-2를 b에 곱해야 n이 됩니다. 또, 지금 mod 19에서 (1,5)처럼 같은 종류의 순서쌍이 존재할 수 있는 소수의 조건을 찾고 있습니다.

      좋아요0
  • 안성탕면 2017.11.19 08:49:09

    문제2에서 r_p(1,1)은 첫 순환에서 p번 굴림시행했을 때 피보나치수열과 제일 가깝고 작은 소수와의 차가 x좌표로 바뀌고, 피보나치수열 중 적어도 한 항 이상은 어떤 소수로 나누어진다는 것을 증명하면 r_p(1,1)은 항상 존재하고,

    q_p(1,1)/r_p(1,1)은 1/2인 것으로 추측이 됩니다만

    반박글 대 환영입니다 제가 좀 늦게 달아서요

     

    좋아요0 댓글수5
    • 여백 패르마 2017.11.19 09:30:37

      r_p(1,1)가 존재한다는 것은 구머님과 저가 증명했는데요....    

      늦게 하셔서 모르셨나요??

      좋아요0
    • 여백 패르마 2017.11.19 17:35:48

      또 p=5일때를 봐도 1/2는 아닌데요...

      좋아요0
    • 여백 패르마 2017.11.19 19:52:33

      그것이 1/2라는 근거가 있나요??

      좋아요0
    • 안성탕면 2017.11.20 08:44:13

      제가 앞 글들을 보지 않아서요..

      그리고 그 값이 일정하지 않다면.. 이상하네요? 그 값이 일정하지 않은데 어떻게 구하라는... 혹시 극한값을 구하라는 말인가요?

      좋아요0
    • 여백 패르마 2017.11.20 14:24:25

      p에 대한 식이 아닐까요??

      좋아요0
  • 구머 2017.11.21 00:06:34

    지금 위에서 말한 소수의 성질을 발견+증명했고 mod 20(또는 40)으로 봤을 때 일부의 경우에 한해서 답을 알아냈습니다. 조만간 실험을 살짝 더 해서 mod20으로 모든 소수를 분류하여 답을 찾을 수 있을 듯 합니다.

    좋아요0 댓글수0