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

Problems

폴리매스 문제 보기

문제

[대한수학회] 대4. 30회 KMO 2번 문제 일반화하기_ shine, 수돌이, tommy 님 9월 30일 멘토링 진행합니다 연락처 남겨주세요!

2017.05.23

같이 풀어볼까?

네이버밴드 구글플러스

다음은 제30회 한국수학올림피아드(KMO) 최종시험 2번 문제다.

양의 정수 \large {\color{Blue} n}에 대하여  \large {\color{Blue} n+1}개의 정수로 이뤄진 순서쌍 \large {\color{Blue} (a_0, a_1, \cdots , a_n)}이 있다. 모든 \large {\color{Blue} k=0, 1, \cdots, n} 에 대해, \large {\color{Blue} (a_0, a_1, \cdots , a_n)}에서의 \large {\color{Blue} k}의  개수를 \large {\color{Blue} b_k}라 하고, \large {\color{Blue} (b_0, b_1, \cdots, b_n)}에서의 \large {\color{Blue} k}의 개수를 \large {\color{Blue} c_k}라고 하자. 이때 \large {\color{Blue} a_0=c_0, a_1=c_1, \cdots , a_n=c_n}이 되는 순서쌍 \large {\color{Blue} (a_0, a_1, \cdots , a_n)}을 모두 구하여라.

 

위의 문제에서와 같이, 음이 아닌 정수 \large n\geq 0에 대해, 정수 순서쌍 \large (a_0, a_1, \cdots, a_n)에서의 \large k의 개수를 \large b_k라고 할 때, 정수 순서쌍 \large (a_0, a_1, \cdots, a_n)을 정수 순서쌍 \large (b_0, b_1, \cdots, b_n)으로 변경하는 변환을 T라고 정의하자. 임의 정수 순서쌍에 대해, 변환 T를 반복적으로 사용하면 순서쌍은 순환하게 되며, 순환마디의 크기를 순서쌍의 '순환주기'라고 정의하자. 또한 순환마디에 도달할 때까지의 변환횟수를 순서의 'Rank'라고 정의하자.

 

예를 들어 (1,2)은 다음과 같이 변환된다.

(1,2) → (0,1) → (1,1) → (0,2) → (1,0) → (1,1) →···

그러므로 (1,2)의 순환마디는 (1,1) → (0,2) → (1,0)이고, 순환주기는 3이고, Rank는 2이다.

 

(1) 음 아닌 정수 n에 대해, 모든 순환마디를 찾고 순환주기에 따라 분류하여라. 가장 긴 순환주기를 가지는 순환마디는 무엇인가?

 

(2) 음 아닌 정수 n에 대해, 가장 큰 Rank가 되는 값을 찾고, 이때의 정수 순서쌍은 어떤 것이 있는가?

 

[공지] 검토 결과 1번은 맞았고, 2번은 틀렸습니다.

출제자에 따르면 n이 고정되면, 문제에서 정의한 변환의 치역이 고정돼 유한한 값을 갖는다고 합니다. 즉 rank 자체가 무한으로 나올 수 없답니다. 매우 큰 수긴 하지만 유한한 값이라는 것이지요.

또 증명 과정에 오류가 있답니다. \huge {\color{Blue} x_i}들 간의 순환이 없음을 증명해야 하는데 그 부분이 빠졌다고 합니다.

하지만 shine 님의 아이디어는 매우 좋았고, 접근 방법도 훌륭하다고 합니다. 어쩌면 이 접근으로 낼 수 있는 결론이 이 문제의 최대치가 아닐까 생각된다면서 이보다 더 좋은 결과를 앞으로 얻기는 어렵다고 밝혔습니다. 

 

따라서 출제자인 신희성 인하대 교수님과의 멘토링을 진행하기로 했습니다. 멘토링 날짜는 9월 30일 토요일입니다. 문제 푸는데 기여한 shine님과 수돌이님, tommy님은 비밀댓글로 연락처와 이름, 학교, 학년을 남겨주세요! 

멘토링 날짜는 조율 가능합니다. 교수님께서는 평일에는 아무때나 가능한데, 주말에는 9월 30일만 가능하다고 합니다. 그래서 일단 이때로 정했습니다.

댓글 35

  • 수학동아 2017.05.23 15:57:08

    A파랭이 2017.04.01. 02:07

    n=0이면 (a)
    i) a=0 (0)->(1)->(0) Rank=1
    ii) a>0 (a)->(0)->(1)->(0) Rank=1


    n=1일때 순서쌍 (a,b)에 대해서 다음과 같은 경우로 분류해보았습니다.
    i) a,b>1
    0 또는 1이 없기에 다음 변환들은 필연적으로 (0,0)->(2,0)->(1,0)->(1,1)->(0,2)->(1,0) Rank는 2입니다.

    ii) a>1, b=1
    (a,b)->(0,1)->(1,1)->(0,2)->(1,0)->(1,1) Rank는 2입니다.
    iii) a=1, b=1 는 ii와 같은 경우로 볼 수 있습니다.
    iv) a=1, b=0도 ii와 같은 경우로 볼 수 있습니다.
    v) a=0, b=0 는 i와 같은 경우로 볼 수 있습니다.

    뾰족한 수가 떠오르지 않으니 일단 몇가지 경우를 구해보고 생각해봐야겠네요..
    n=2일때는 (1,1,1)->(3,0,0)->(2,0,0)->(2,0,1)로 Rank=3임을 확인 했습니다.


    *수정
    Rank에 대한 이해가 잘못됬었네요
    Rank를 순환마디-1로 오해해서 발생한 문제이니 위 내용은 무시하셔도 됩니다.

    좋아요0 댓글수2
    • 수학동아 2017.05.23 15:57:42

      c 언어 2017.04.02. 17:52

      n이 정해져도 Rank의 값이 처음 값에 따라서 다르게 나올수 있지 않을까요?
      그래서 (1,1,1)의 Rank값이 3이라고 n=2일때 Rank값이 3이라고 단정지을수는 없을것 같네요.

      만약 Rank값이 0이상이라면 (1,1,1)에서 순환마디가 (1,1,1)을 포함하니 Rank의 값이 0이라고도 할 수 있지 않을까요?

      좋아요0
    • 수학동아 2017.05.23 15:58:05

      A파랭이 2017.04.02. 21:04

      c 언어  예 지금 확인해보니 제가 문제 이해를 잘못했네요 ㅠㅠ
      Rank가 아니라 순환마디가 4인건데 ㅋㅋㅋㅋ
      새벽에 하느라 정신이 없었나보군요

      좋아요0
  • 수학동아 2017.05.23 15:58:23

    A파랭이 2017.04.01. 02:14

    수학적 증명과는 별개이지만 직관적으로 보았을때 개미수열이 먼저 떠오르더군요..
    조금더 계산해보면 반례를 찾을 수 있을지도 모르겠지만 개미수열과 관련이 있다면
    순환마디는 4 또는 5이상이 되지 않을거라는 추측을 해봅니다..

    좋아요0 댓글수1
    • 수학동아 2017.05.23 15:59:06

      tommy 2017.04.04. 20:48

      오ㅎ 그럴지도 모르겠네요. 다만 개미수열은 있는 수들만 취급하고 이 수열은 0부터 정해진 수까지만 정확하게 체크하니 계속 변하겠군요

       

      좋아요0
  • 수학동아 2017.05.23 15:59:50

    c 언어 2017.04.04. 23:08

    개수가 3일때 64개를 다 해보았습니다.(64개를 하지는 않고 64개에서 변환 t를 한번 하였을때 종류가 20가지가 나와서 20가지에 대하여서 주기와 Rank를 구해 보았습니다.
    그 결과 주기는 모두 4가 나왔고 Rank는 (0이 될경우)0,1,2 (0이 않될경우)1,2,4가 나왔습니다.

    n의 값이 1,2,3인경우 순환주기와 Rank의 값입니다.
    http://blog.naver.com/hello662200/220975338526

    좋아요0 댓글수0
  • 수학동아 2017.05.23 16:00:11

    c 언어 2017.04.05. 00:39

    정리: n=1 주기:2 Rank 최대값:0
    n=2 주기:3 Rank 최대값:2
    n=3 주기:4 Rank 최대값:3

    좋아요0 댓글수6
    • 수학동아 2017.05.23 16:00:32

      tommy 2017.04.06. 19:25

      +너무 이른지 모르지만, 프로그램 돌려서 n=6까지 찾아냈습니다.
      n=0일 때 Rank 최대: 0
      n=1일 때 Rank 최대: 3
      n=2일 때 Rank 최대: 3
      n=3일 때 Rank 최대: 6
      n=4일 때 Rank 최대: 7
      n=5일 때 Rank 최대: 7
      n=6일 때 Rank 최대: 7
      (이상하다.. 왜 다르죠..? a_k에 n+1을 포함해서 그런가)
      근데, Rank 최댓값을 만들어내는 a 수열을 찾아보니 신기한 추측이 하나 생겼습니다. n이 3 이상일 때 (0, 1, ..., n)은 항상 Rank의 최댓값을 만들어낼까요? (0, 1, 2, 3)의 Rank는 6, (0, 1, 2, 3, 4)의 Rank는 7, (0, 1, 2, 3, 4, 5)의 Rank는 7, (0, 1, 2, 3, 4, 5, 6)의 Rank는 7이거든요.

      좋아요0
    • 수학동아 2017.05.23 16:01:28

      tommy 2017.04.06. 19:47

      참, n=0~6일 때 순환고리는
      n=0 (0)→(1)→(0) 주기 2
      n=1 (0, 2)→(1, 0)→(1, 1)→(0, 2) 주기 3
      n=2 (0, 3, 0)→(2, 0, 0)→(2, 0, 1)→(1, 1, 1)→(0, 3, 0) 주기 4
      n=3 (1, 2, 1, 0)→(1, 2, 1, 0) 주기 1 (2, 0, 2, 0)→(2, 0, 2, 0) 주기 1
      n=4 (2, 1, 2, 0, 0)→(2, 1, 2, 0, 0) 주기 1
      n=5 (2, 3, 0, 1, 0, 0)→(3, 1, 1, 1, 0, 0)→(2, 3, 0, 1, 0, 0) 주기 2
      n=6 (3, 2, 1, 1, 0, 0, 0)→(3, 2, 1, 1, 0, 0, 0) 주기 1
      (3, 3, 0, 0, 1, 0, 0)→(4, 1, 0, 2, 0, 0, 0)→(4, 1, 1, 0, 1, 0, 0)→(3, 3, 0, 0, 1, 0, 0) 주기 3
      이렇게 됩니다. 이들이 n=0~6일 때의 모든 순환고리들입니다.

      좋아요0
    • 수학동아 2017.05.23 16:02:03

      A파랭이 2017.04.06. 22:50

      tommy  우연인지는 모르겠지만 여기까진 순환주기가 4이군요 ㅋㅋ

      좋아요0
    • 수학동아 2017.05.23 16:02:51

      tommy 2017.04.06. 23:10

      A파랭이  최고 순환주기 말씀하시는 거죠? 그러네요ㅎㅎ
      n=6인 경우도 1시간 동안 프로그램 돌려서 겨우 찾아냈습니다ㅋㅋ

      흠.. 아무래도 (0, 1, ..., n)이 최고 Rank를 만들어낸다는 제 추측은 틀린 것 같네요. n이 0~6일 땐 프로그래밍으로 구했듯이 Rank는 0, 1, 1, 6, 7, 7, 7이고, n이 7 이상일 땐 항상 Rank는 8이더군요. 증명은 간단합니다.
      (0, 1, 2, 3, ..., (n-3), (n-2), (n-1), n)
      →(1, 1, 1, 1, ..., 1, 1, 1, 1)
      →(0, (n+1), 0, 0, ..., 0, 0, 0, 0)
      →(n, 0, 0, 0, ..., 0, 0, 0, 0)
      →(n, 0, 0, 0, ..., 0, 0, 0, 1)
      →((n-1), 1, 0, 0, ..., 0, 0, 0, 1)
      →((n-2), 2, 0, 0, ..., 0, 0, 1, 0)
      →((n-2), 1, 1, 0, ..., 0, 1, 0, 0)
      →((n-3), 3, 0, 0, ..., 0, 1, 0, 0) ★
      →((n-2), 1, 0, 1, ..., 1, 0, 0, 0)
      →((n-3), 3, 0, 0, ..., 0, 1, 0, 0) ★
      n이 커져도 최고 Rank가 계속 8에 머무를 것 같진 않아서 말입니다. 하지만.. 이것도 추측이니 가능성을 배제할 순 없겠죠. 어쨌든 n이 7 이상일 때의 순환고리가 하나는 나왔네요;;

      참, n이 7 이상일 때만 저 수열이 성립하는 이유는 아래에서 2번째 줄에서 ..., 부분이 최소 0개일 수 있기 때문입니다. 만약 n이 7 미만이 되면 그 부분에서 순환고리가 안 나오고 꼬입니다; 그리고 참고로 ..., 부분은 첫째, 둘째 줄을 제외하고는 모두 0으로 채워집니다

      좋아요0
    • 수학동아 2017.05.23 16:03:42

      수돌이 2017.04.29. 16:31

      tommy 아쉽게도 Rank가 9인 경우를 발견했습니다.
      n=2816에서 아래와 같은 경우입니다.

      1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 68 68 68 68 68 68 68 68 68 68 68 68 68 68 68 68 68 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 71 71 71 71 71 71 71 71 71 71 71 71 71 71 71 71 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 74 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 77 77 77 77 77 77 77 77 77 77 77 77 77 77 77 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 79 79 79 79 79 79 79 79 79 79 79 79 79 79 79 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 81 81 81 81 81 81 81 81 81 81 81 81 81 81 81 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 83 83 83 83 83 83 83 83 83 83 83 83 83 83 84 84 84 84 84 84 84 84 84 84 84 84 84 84 85 85 85 85 85 85 85 85 85 85 85 85 85 85 86 86 86 86 86 86 86 86 86 86 86 86 86 86 87 87 87 87 87 87 87 87 87 87 87 87 87 87 88 88 88 88 88 88 88 88 88 88 88 88 88 88 89 89 89 89 89 89 89 89 89 89 89 89 89                90 90 90 90 90 90 90 90 90 90 90 90 90 91 91 91 91 91 91 91 91 91 91 91 91 91 92 92 92 92 92 92 92 92 92 92 92 92 92 93 93 93 93 93 93 93 93 93 93 93 93 93 94 94 94 94 94 94 94 94 94 94 94 94 94 95 95 95 95 95 95 95 95 95 95 95 95 95 96 96 96 96 96 96 96 96 96 96 96 96 97 97 97 97 97 97 97 97 97 97 97 97 98 98 98 98 98 98 98 98 98 98 98 98 99 99 99 99 99 99 99 99 99 99 99 99 100 100 100 100 100 100 100 100 100 100 100 100 101 101 101 101 101 101 101 101 101 101 101 101 102 102 102 102 102 102 102 102 102 102 102 102 103 103 103 103 103 103 103 103 103 103 103 104 104 104 104 104 104 104 104 104 104 104 105 105 105 105 105 105 105 105 105 105 105 106 106 106 106 106 106 106 106 106 106 106 107 107 107 107 107 107 107 107 107 107 107 108 108 108 108 108 108 108 108 108 108 108 109 109 109 109 109 109 109 109 109 109 109 110 110 110 110 110 110 110 110 110 110 111 111 111 111 111 111 111 111 111 111 112 112 112 112 112 112 112 112 112 112 113 113 113 113 113 113 113 113 113 113 114 114 114 114 114 114 114 114 114 114 115 115 115 115 115 115 115 115 115 115 116 116 116 116 116 116 116 116 116 116 117 117 117 117 117 117 117 117 117 117 118 118 118 118 118 118 118 118 118 119 119 119 119 119 119 119 119 119 120 120 120 120 120 120 120 120 120 121 121 121 121 121 121 121 121 121 122 122 122 122 122 122 122 122 122 123 123 123 123 123 123 123 123 123 124 124 124 124 124 124 124 124 124 125 125 125 125 125 125 125 125 125 126 126 126 126 126 126 126 126 127 127 127 127 127 127 127 127 128 128 128 128 128 128 128 128 129 129 129 129 129 129 129 129 130 130 130 130 130 130 130 130 131 131 131 131 131 131 131 131 132 132 132 132 132 132 132 132 133 133 133 133 133 133 133 133 134 134 134 134 134 134 134 134 135 135 135 135 135 135 135 136 136 136 136 136 136 136 137 137 137 137 137 137 137 138 138 138 138 138 138 138 139 139 139 139 139 139 139 140 140 140 140 140 140 140 141 141 141 141 141 141 141 142 142 142 142 142 142 142 143 143 143 143 143 143 143 144 144 144 144 144 144 145 145 145 145 145 145 146 146 146 146 146 146 147 147 147 147 147 147 148 148 148 148 148 148 149 149 149 149 149 149 150 150 150 150 150 150 151 151 151 151 151 151 152 152 152 152 152 152 153 153 153 153 153 153 154 154 154 154 154 155 155 155 155 155 156 156 156 156 156 157 157 157 157 157 158 158 158 158 158 159 159 159 159 159 160 160 160 160 160 161 161 161 161 161 162 162 162 162 162 163 163 163 163 163 164 164 164 164 165 165 165 165 166 166 166 166 167 167 167 167 168 168 168 168 169 169 169 169 170 170 170 170 171 171 171 171 172 172 172 172 173 173 173 173 174 174 174 174 175 175 175 176 176 176 177 177 177 178 178 178 179 179 179 180 180 180 181 181 181 182 182 182 183 183 183 184 184 184 185 185 185 186 186 186 187 187 188 188 189 189 190 190 191 191 192 192 193 193 194 194 195 195 196 196 197 197 198 198 199 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213

      좋아요0
    • 수학동아 2017.05.23 16:04:02

      tommy 2017.04.30. 12:25

      수돌이  n=2816이라고요?! ㄷㄷㄷ
      추측이 깨질 것 같긴 했지만 반례가 나올 줄은 몰랐네요.. 어쨌든 저 수열로 시작하면 Rank가 9가 된다는 거죠..? 혹시 그때의 순환마디는 어떻게 되나요?

      좋아요0
  • 수학동아 2017.05.23 16:04:19

    로직 매니아 지망생 2017.04.28. 20:08

    복잡복잡

     

    좋아요0 댓글수0
  • 수학동아 2017.05.23 16:04:33

    반짝별 2017.05.08. 07:12

    순환주기에 관해서는 거의 다 풀었고 수정중에 있습니다.
    풀이를 간략히 설명하자면 n이 8 이상일때 순환마디에 속하는 순서쌍을 하나 잡고,
    A0+A1+A2+...+An = n+1 과
    0*A0+1*A1+2*A2+...+nAn = n+1 을 보입니다.

    그 순서쌍에서 T의 역변환을 계속 거쳤을때,
    A2+A3+...+An 이 대략 3,4 이상이면
    A0+A1+A2+...+An의 값이 계속 증폭되어 모순이 생긴다는 것을 보입니다.

    이를 이용해 순환마디가 될 수 있는 경우를 제한할 수 있습니다.

    저의 풀이로는 n이 8 이상일때 순환주기가 1,2 밖에 나올 수 없고,
    n=6까지는 이미 해놓으셨더군요.

    n=7일때는 프로그램 돌려서 구하고 있습니다.

    좋아요0 댓글수1
    • 수학동아 2017.05.23 16:04:57

      tommy 2017.05.08. 23:36

      음.. 잘 이해가 안 가네요. 일단.. T의 역변환을 거칠 때 A2+A3+..+An이 3, 4 이상이면 왜 계속 증폭되는 거죠?

      좋아요0
  • shine 2017.05.28 16:05:01

    영재교 준비로 업로드가 늦어졌네요. 개인적으로 타이핑보다 직접 쓰는 것이 편한지라 사진으로 올립니다.

    참고로 저는 일전에 댓글을 썼던 반짝별입니다.

     

    좋아요0 댓글수2
    • 수학동아 2017.06.02 10:08:23

      멘토에게 풀이가 맞는지 확인해본 결과 n이 8 이상인 경우 모든 순환마디를 잘 찾았다고 합니다^^. 앞에 나온 n이 6 이하일 때도 모두 맞다고 합니다. 아무래도 이번 문제제는 해결이 된다면 온라인으로 함께 문제를 풀자는 폴리매스 프로젝트의 취지에 맞게 여러 명의 이름이 명예의 전당에 오를 것 같습니다.^^조금만 더 힘내주세요!

      좋아요0
    • shine 2017.06.03 09:13:09

      생각해보니 n=7일때 바뀌는 건 VIII 쪽에서 x{_{y{_0}}}< 2  가 x{_{y{_0}}}\leq 2로 바뀌는 것 뿐인데, x{_{y{_0}}}= 2 인 조건에 맞는 유일한 경우인 (0,0,0,0,2,0,0,0)가 순환마디에 속하지 않음이 자명하니 n=7일때도 8이상일 때와 마찬가지입니다.

      좋아요0
  • 미래탐정 2017.07.04 14:56:01

    shine님이 n=7인 경우를 해결하셨는데 아직 미해결이라 나오네요^^

    좋아요0 댓글수1
    • shine 2017.07.04 16:18:21

      1번 문제에 답하는데 필요한 것이 다 모인 것이지 하나로 정리하진 않았으니 그렇겠죠?

      좋아요0
  • shine 2017.07.06 21:31:33

    자, 문제를 마무리지어보죠.

     

    순환주기=1 인 경우

    (1, 2, 1, 0)⟲

    (2, 0, 2, 0)⟲

    (2, 1, 2, 0, 0)⟲

    (3, 2, 1, 1, 0, 0, 0)⟲

    n>6일때 (n-2, 2, 1, 0, … ,0, 1, 0, 0, 0)

     

    순환주기=2 인 경우

    (0)↔(1)

    (2, 3, 0, 1, 0, 0)↔(3, 1, 1, 1, 0, 0)

    n>6일때 (n-3, 3, 0, … , 0, 1, 0, 0)↔(n-3, 1, 0, 1, 0, … ,0, 1, 0, 0, 0)

     

    순환주기=3 인 경우

    (0, 2)   →   (1, 0) 

        ↖         ↙

               (1,1)

    (3, 3, 0, 0, 1, 0, 0) → (4, 1, 0, 2, 0, 0, 0)

                     ↖                      ↙

                   (4, 1, 1, 0, 1, 0, 0)

     

    순환주기=4 인 경우

    (0, 3, 0)→(2, 0, 0)

                     

    (1, 1, 1)←(2, 0, 1) 로 이게 제일 긴 순환마디입니다.

     

    좋아요0 댓글수0
  • shine 2017.07.08 15:19:31

    수돌이님의 rank가 9가 되는 예시에서 힌트를 얻어 생각해보았는데,  n을 충분히 크게 해 준다면 rank를 무한히 키울 수 있다는 것을 알아냈습니다.

    증명은 조금 뒤에 올리겠습니다.

    좋아요0 댓글수0
  • shine 2017.07.15 18:45:35

    좋아요0 댓글수0
  • shine 2017.07.18 15:52:54

    제가 푼 게 맞는지 확인해주십시오.

    좋아요0 댓글수2
    • 수학동아 2017.07.19 13:33:14

      shine님께서 올린 이미지 파일이 보여지 않습니다. 엑스 박스가 뜨네요.

      아마도 이미지를 복사해서 붙여넣기 하신 것 같은데...

      이미지 업로드 하는 아이콘을 눌러 이미지를 입력해야 엑스 박스가 뜨지 않습니다.

      이미지 다시 올려주세요!

      좋아요0
    • shine 2017.07.19 17:03:46

      수정했습니다.

      좋아요0
  • shine 2017.07.22 21:21:26

    검토를 기다리고 있습니다...

    좋아요0 댓글수1
    • 수학동아 2017.08.03 16:12:39

      현재 검토 중에 있습니다. 멘토 확인은 끝났고, 출제자에게 확인을 받고 있습니다. 다만 교수님께서 해외 출장 중이라 시간이 오래 걸리고 있습니다. 검토가 늦어져서 죄송합니다. 검토가 완료되는 되면 바로 공지하겠습니다.

      좋아요0
  • 미래탐정 2017.09.07 00:50:51

    언제까지 검토중인건가요??

    좋아요0 댓글수2
    • shine 2017.09.07 16:37:32

      그러게요...

      좋아요0
    • 수학동아 2017.09.11 09:53:36

      죄송합니다. 조금만 더 기다려주세요. 철저하게 검증하다보니 시간이 많이 걸리고 있습니다. 순화마디에 대한 검증은 끝났고, rank에 관해서 검증을 하고 있습니다. 곧 검증 결과를 공지하겠습니다. 다시 한 번 죄송합니다. 

      좋아요0
  • shine 2017.09.12 16:15:36 비밀댓글
    비밀댓글 입니다.
    댓글수0
  • 수돌이 2017.09.24 09:36:43 비밀댓글
    비밀댓글 입니다.
    댓글수0
  • tommy 2017.09.24 23:26:52 비밀댓글
    비밀댓글 입니다.
    댓글수0