본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대39. Welcome to grid world!
수학동아 2020.03.04 17:18

평면 \mathbb{R}^2상에 x좌표, y좌표가 모두 정수인 점을 격자점이라 한다. 격자점들의 집합을 \mathbb{Z}^2로 표현하자. \mathbb{Z}^2상에 n개의 점 v_1, \cdots , v_n을 생각하자. 이때 v_i의 좌표를 (x_i, y_i)라 하면 x_iy_{i+1}-x_{i+1}y_i 값은 항상 1이 된다. (단, v_{n+1}=v_1이라 간주하자.)

 

각각의 v_i는 하나의 벡터로 이해할 수 있다. 즉, v=(x, y), u=(z, w)라 하면, v+u=(x+z, y+w)이고, 상수 k에 대하여 kv=(kx, ky)다. 

 

 

1. 이때 v_{i-1}+v_{i+1}은 항상 v_i의 배수임을 보여라. 즉, v_{i-1}+v_{i+1}+a_iv_i=0을 만족하는 정수 a_i가 존재한다.

 

 

2. 3n+\sum_{i=1}^{n}a_i는 12의 배수가 됨을 보여라.

 

 

3. 위 문제2에 의해 \frac{3n+\sum_{i=1}^{n}a_i}{12}값은 정수임을 알 수 있다. 이 정수의 기하학적 의미를 설명해 보자.

 

 

※참고 

문제의 이해를 돕기 위해 다음 예를 생각하자. 예를 들어 v_1=(1, 0), v_2=(-1, 1), v_3=(0, -1), v_4=(1, 0), v_5=(4, 1), v_6=(3, 1), v_7=(-1, 0), v_8=(0, -1)라고 하면 문제의 조건인 x_iy_{i+1}-x_{i+1}y_i=1을 만족한다.

v_1+v_3=(1, -1)=-v_2이므로 a_2=-1이고, v_8+v_2=(-1, 0)=-v_1이므로 a_1=-1이 된다. 이런 방식으로 계산하면 a_1=-1, a_2=-1, a_3=-1, a_4=4, a_5=1, a_6=1, a_7=-3, a_8=0이다. 따라서 3   imes 8+\sum_{i=1}^{8}a_i=24이고, 이는 12의 배수다.

  •  
    code Lv.5 2020.03.04 22:17 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수5
    •  
      김미래 기자 Lv.5 2020.03.24 19:33 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      code Lv.5 2020.03.24 21:06 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      김미래 기자 Lv.5 2020.04.02 10:08

      이메일 알려주시면 질문 보내드리겠습니다!

      좋아요0
    •  
      code Lv.5 2020.04.02 17:21 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      최기자 Lv.4 2020.04.16 21:53 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    해결
    파스칼 Lv.5 2020.03.04 23:26 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      파스칼 Lv.5 2020.03.04 23:49 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      최기자 Lv.4 2020.04.16 21:54

      김다인 멘토가 검토한 결과 1번 문제 잘 푼 것 같다고 합니다.^^ 수고했어요~!

       

      부분해결 딱지 붙은 거는 해결로 고칠게요!!

       

      좋아요0
  •  
    빅수빈데요 Lv.11 2020.03.05 01:03

    2번 문제에 n이 4일때 12의 배수가 되나요?  제가 문제를 잘못 이해하고 있는거 같은데 누가 좀 알려주세요... a가 의미하는게 뭔지 모르겠어요..

    댓글 작성하기 좋아요0 댓글수0
  •  
    구머 Lv.5 2020.03.05 10:59

    문제 오류..까지는 아니지만 조금 어색한 부분이 있는 것 같습니다. 문제에서 y_ix_{i+1}-y_{i+1}x_i의 값이 1이 된다고 했는데, 이 값을 관찰하면 v_{i+1} \times v_i와 값이 동일함을 알 수 있습니다. 하지만 제 생각에는 v_{i} \times v_{i+1}=y_{i+1}x_{i}-y_{i}x_{i+1}=1로 정의하는 것이 문맥상 자연스러운 조건이라고 생각합니다.(실제로 문제에서 주어진 예시를 봐도 y_{i+1}x_{i}-y_{i}x_{i+1}=1이 성립한다는 것을 알 수 있습니다.)

    또, 아직 a_i값에 대해 정확히 정의되진 않았지만, 만약 문제1번의 정의, 즉 a_i를 v_{i-1}+v_{i+1}+a_iv_i=0를 만족하는 정수 a_i라는 정의대로 따라간다면, 문제에서 주어진 예시의 a_i값들의 부호가 반대로 되있는 것 같습니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      최기자 Lv.4 2020.03.06 09:56

      출제하신 교수님께 말씀드려 봤는데 구머 학생의 지적처럼 x_i y_i+1 - x_i+1 y_i=1이 맞다고 합니다. 혼란을 줘서 미안합니다~!

      좋아요0
  •  
    리프 Lv.6 2020.03.07 20:11

    혹시 비밀댓글 다신 분들 중 2번이나 3번 해결하신 분 있나요?

    댓글 작성하기 좋아요0 댓글수5
    •  
      code Lv.5 2020.03.07 21:08

      전 감도 못잡겠습니다.. 몇몇 특징은 발견하긴 했는데 별 도움이 안되더라고요.

      리프님은 2번 어떻게하고 계신지 궁금하네요.

      좋아요1
    •  
      리프 Lv.6 2020.03.07 22:53

      저는 아직 깊게 고민해보지 않아서 2번부턴 못 풀었습니다. 시간 되면 고민해볼껀데 아마도 난이도가 좀 있는 문제일 것 같네요

      좋아요0
    •  
      김미래 기자 Lv.5 2020.03.24 19:33 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      리프 Lv.6 2020.03.25 14:47 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      리프 Lv.6 2020.03.31 20:05 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    muse Lv.6 2020.03.10 16:40

    오! 격자점 문제다! 제가 가장 좋아하는 분야네요.

    1번은 쉬운 것 같고, 2~3번 생각해 보겠습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    해결
    엡실론-델타 Lv.3 2020.03.13 19:35 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      최기자 Lv.4 2020.04.16 21:55

      김다인 멘토가 1번 문제 풀이를 검토한 결과 깔끔하게 잘 해결한 것 같다고 하네요! 수고했어요^^

      좋아요0
  •  
    무한대의끝을본남자 Lv.6 2020.03.17 11:42

    선형대수학 쓰면될것같은데

     

    쉬우면서도 너무 어렵네요

    댓글 작성하기 좋아요0 댓글수0
  •  
    무한대의끝을본남자 Lv.6 2020.03.17 23:21

    문제에 살짝 이상한점이있는데요 원래 벡터는 (x,y)꼴로 표현하는것이아닌,  시점과종점이있어야하는것아닌가요?

    댓글 작성하기 좋아요0 댓글수2
    •  
      무한대의끝을본남자 Lv.6 2020.03.17 23:22

      만일 이것이  위치벡터라면 [n,m]꼴로 표현되어야하는것아닌가요?

      열벡터나 행벡터로 주세요

      아니면 시점 A와 B형태로오던가요

      그러면 일단 위치벡터로 생각하고 풀겠습니다

      좋아요0
    •  
      리프 Lv.6 2020.03.17 23:58

      소괄호든 대괄호든 표기의 차이지 별 상관 없잖아요 ㅋㅋ (위치벡터겠죠)

      좋아요0
  •  
    무한대의끝을본남자 Lv.6 2020.03.18 00:12
    확인요청중

    일단 이는 모두정수벡터이다

    한번 귀류법으로 1번을 증명하여보자

    u_{i-1}+u_{i+1}가 u_i의 배수가 아님으로 가정하자

    이는 정수벡터이므로 부정방정식 형태로 표현하자 즉,

    x_{i-1}+x_{i+1}이 x_i의배수가 아니거나(또는)

    y_{i-1}+y_{i+1}이 y_i의 배수가 아니여야한다

    그리고

    x_{i}y_{i+1}-y_{i}x_{i+1}=1이다

    x_k, y_k 를 각각의 정수y_{i-1}=a, y_{i} = b, y_{i+1} = c그리고 x_{i-1}=d, x_{i} = e, x_{i+1} = f라고하자(어차피정수이기때문에)

    즉, 바꿔말하면

    d+f|e 또는 a+c|b가 성립하지않아야한다

    그리고ec-bf=1 이다

    그래서

    e = \frac{1+bf}{c}

    인데 간단한 합동식의정리의 의하여 d+f/1+bf, d+f/(1/c) 의 해가 존재함은 자명하므로

     

    위에가정에모순이된다

     

    댓글 작성하기 좋아요0 댓글수8
    •  
      리프 Lv.6 2020.03.18 11:46

      마지막 줄에서 해가 존재한다는 것이 무슨 뜻이죠?

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.03.18 11:49

      a가 존재 한다는 뜻이예요

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.03.18 11:51

      a_i가요

      좋아요0
    •  
      리프 Lv.6 2020.03.18 12:53

      '간단한 합동식의 정리에 의하여 \frac{d+f}{1+bf},\frac{d+f}{1/c}의 해가 존재함은 자명하므로 위 가정에 모순이 된다.' 

      이 부분이 무슨 뜻인지 이해가 안 되는데요...

      좋아요0
    •  
      김미래 기자 Lv.5 2020.03.24 19:34 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      무한대의끝을본남자 Lv.6 2020.03.24 21:07 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      최기자 Lv.4 2020.04.16 21:59

      김다인 멘토가 검토한 결과 다음과 같은 피드백을 줬습니다. 보완 부탁해요.^^

       

       “간단한 합동식의 정리에 의하여 d+f/1+bf,d+f/(1/c)의 해가 존재함은 자명”하다는 부분을 좀 더 구체적으로 설명해주세요.
       

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.04.24 11:48

      즉, 바꿔말하면

      d+f|e 또는 a+c|b가 성립하지않아야한다

      그리고ec-bf=1 이다

      그래서

      e = \frac{1+bf}{c}

      인데 간단한 합동식의정리의 의하여 d+f/1+bf, d+f/(1/c) 의 해가 존재함은 자명... 이아니라 최기자님의 말대로 보완하도록 하죠

      그러면 d+f|e 라면 합동식으로 풀면 d+f\not\equiv 0 (MOD e)ORa+c\not\equiv 0(MODb)

      a+c가 ㅠb의 배수라고 가정하면 a+c = nb+0이므로 e = \frac{1+bf}{c}에 대입하면

      e = \frac{1+bf}{nb-a}인데 n이 2보다 크다라고 가정하면 a가 b보다 작어져야한다 따라서 배수가될조건은 a가 b보다작어지는것인데 그러려면 n이 커져야한다

      n이커지면 f가 커져야된다 n을 조건에 맞게 잡으려면 f \geq a인데 그리하면 n = a, a = -1이라는 해가 존재하여서 성립된다

       

      그러면 2번째 조건인 b+f를 e의 배수로 잡자 그러면 b+f/1+bf/c이면 c*(b+f)/bf = c/f+c/b = n 따라서 c는 f와 b의 배수이므로

      최대공약수 gcd(f,b)*m = c의 해는 존재함은 자명하다는것은 모두 아실겁니다

       

      마지막 조건으로 모두 배수가 아니도록 잡읍시다

      그러면 1,2번째 조건에서 구한 f < a 그리고  c/fb \notin \mathbb{N}

      하지만 여기서는 1의 조건인 e = \frac{1+bf}{nb-a}가 아니므로 존재하고

      c가 f,b와 서로소여도 1번조건이 없으므로 문제될 것이없다 따라서 모든전제조건이 성립되어

       

       

      존재한다

      좋아요0
  •  
    무한대의끝을본남자 Lv.6 2020.03.18 22:32

    v_{i-1}+v_{i+1}+a_iv_i=0을만족하는 정수가 a_i이므로 벡터좌표계꼴로 변환하면

    u = [x_{i-1}+x_{i+1}+a_ix_i, y_{i-1}+y_{i+1}+a_iy_i]이다

    그래서이는 |u| = 0인 영벡터이다 이는 위치벡터이므로 u = [0,0]

    즉 a_i = \frac{-(x_{i+1}+x{i-1})}{x_i} (OR) \frac{-(y_{i+1}+y{i-1})}{y_i}

    이제 \sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n} \frac{-(x_{i+1}+x_{i-1})}{x_i}= \sum_{i = 1}^{n} \frac{-(y_{i+1}+y_{i-1})}{y_i}

    여기서 \sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n} \frac{-(f+d)}{e}= \sum_{i = 1}^{n} \frac{-(a+c)}{b}

    a,b,c,d,e,f,g의 임의의 정수꼴과 3n을 더하면 12의 배수임을 증명하면된다

    (아 증명귀찮다)

     

    다른분이 대신 증명해주세요 ^^<ㅍㅍㅍㅍ

    댓글 작성하기 좋아요0 댓글수3
    •  
      무한대의끝을본남자 Lv.6 2020.03.18 22:34

      참고로 성분을 더하는것이아닌 벡터의덧셈(평행사변형법칙)을 이용하는방법도있습니다

       

      제2코사인쓰세요^^

      좋아요0
    •  
      리프 Lv.6 2020.03.18 23:51

      근데 2번 증명을 성공했는데 귀찮아서 안 올리는건가요?

      저 명제를 보이는 것이 문제의 핵심인데 저 명제를 증명했으면 올려주시기 바랍니다. (다른 분들은 못한듯)

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.03.18 23:55

      저 명제는 제가아주싫어하는 부정방정식이므로 다른분께 맡기고자합니다<ㅍㅍㅍㅍㅍ

       

      물론수학은 전부재밌죠 ㅎㅎ(농담으로)

      좋아요0
  •  
    무한대의끝을본남자 Lv.6 2020.03.19 20:16
    확인요청중

     v_{i-1}+v_{i+1}+a_iv_i=0를 만족하는정수a_i의 기하학적의미는 

    물리학적으로표현하면 F_{i-1}, F_{i+1}의합력이 F_i의배수이다 라는것이될수있겠습니다

    (이때, |u_i| = F_i라 볼 수있습니다)

    *추신: 이것의 증명은 여백이부족해안하겠<ㅍㅍㅍ 이가 아니라 |u_{i-1}+u_{i+1}| = m|u_i| 이므로 성립합니다

    하지만 여기서의 답은 물리학적이아닌 기하학적이라고했죠

    따라서 이는 닮음 삼각형(?) 뭐 그정도로 되겠습니다 배수이면 제2코사인법칙도 배수가되겠죠

    더 추가할게있으면 추후에 기하학적인것을 더살펴보겠습니다

     

     

    댓글 작성하기 좋아요0 댓글수6
    •  
      리프 Lv.6 2020.03.19 21:59

      지금 님이 적으신 2,3번 풀이는 증명이 아니라 문제로부터 알아낼 수 있는 몇 가지 특징일 뿐이고 증명이 될 수 없습니다.

      님이 적어놓으신 거에서 그 다음 부분(12의 배수에 대한 증명) 핵심인데 그걸 빼놓으시면 어쩌자는거죠...

      이건 간단하게 해결되는 부분이 아니고(제 기준) 만약 푸셨다면 증명의 아이디어라도 적어주시기 바랍니다.

       

      그리고 12의 배수에 대한 증명을 했다고 스스로 생각해도 풀이를 적다보면 오류가 발견될 수도 있으니 귀찮으셔도 풀이를 적어주셨으면 합니다.

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.03.19 22:59

      아그게 추후에 생각해보고 추가하려고요

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.03.24 21:15

      제가 배수의 기하학적 원리를 생각하여봤는데요

      아마도 삼각비에 관련된게 아닌가싶습니다

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.03.25 11:09

      하지만 리프님 문제로서 가장중요한것은 자기자신이 발전하는것이지 빠르게 푸는것은 크지 않습니다 진정한 수학자는 문제위특징을 하나하나 파헤쳐야죠

      좋아요0
    •  
      리프 Lv.6 2020.03.25 14:42

      증명은 여백이 부족해서 안 하겠다 또는 증명은 귀찮아서 생략

      이런 말이 있어서 저는 님께서 증명을 하셨는데 풀이를 안 올리는 거라 생각해서 답글을 단 거 였습니다.

      약간 오해가 있었던 것 같네요. 죄송합니다.

      (그리고 위에 있는 풀이에서 제가 물어본 질문에 대해 답 해주셨으면 하네요)

      좋아요0
    •  
      무한대의끝을본남자 Lv.6 2020.03.25 15:38

      부정방정식의해가 존재한단뜻입니다

       

      근데 다른분이 안푸셔서 제가풀어야할듯합니다...

      좋아요0
  •  
    리프 Lv.6 2020.03.29 09:22

    3번의 답이 수학동아 4월호에 나왔네요. 수학동아에 나온 답을 참고하여 증명을 완성하면 이 문제는 금방 해결될 것 같습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    무한대의끝을본남자 Lv.6 2020.04.24 11:49
    확인요청중

    최기자님이 1번풀이에 자명하다를 보완하여주라고 하셔서 올립니다

    즉, 바꿔말하면

    d+f|e 또는 a+c|b가 성립하지않아야한다

    그리고ec-bf=1 이다

    그래서

    e = \frac{1+bf}{c}

    인데 간단한 합동식의정리의 의하여 d+f/1+bf, d+f/(1/c) 의 해가 존재함은 자명... 이아니라 최기자님의 말대로 보완하도록 하죠

    그러면 d+f|e 라면 합동식으로 풀면 d+f\not\equiv 0 (MOD e)ORa+c\not\equiv 0(MODb)

    a+c가 ㅠb의 배수라고 가정하면 a+c = nb+0이므로 e = \frac{1+bf}{c}에 대입하면

    e = \frac{1+bf}{nb-a}인데 n이 2보다 크다라고 가정하면 a가 b보다 작어져야한다 따라서 배수가될조건은 a가 b보다작어지는것인데 그러려면 n이 커져야한다

    n이커지면 f가 커져야된다 n을 조건에 맞게 잡으려면 f \geq a인데 그리하면 n = a, a = -1이라는 해가 존재하여서 성립된다

     

    그러면 2번째 조건인 b+f를 e의 배수로 잡자 그러면 b+f/1+bf/c이면 c*(b+f)/bf = c/f+c/b = n 따라서 c는 f와 b의 배수이므로

    최대공약수 gcd(f,b)*m = c의 해는 존재함은 자명하다는것은 모두 아실겁니다

     

    마지막 조건으로 모두 배수가 아니도록 잡읍시다

    그러면 1,2번째 조건에서 구한 f < a 그리고  c/fb \notin \mathbb{N}

    하지만 여기서는 1의 조건인 e = \frac{1+bf}{nb-a}가 아니므로 존재하고

    c가 f,b와 서로소여도 1번조건이 없으므로 문제될 것이없다 따라서 모든전제조건이 성립되어

     

     

    존재한다

    댓글 작성하기 좋아요0 댓글수1
  •  
    리프 Lv.6 2020.06.20 17:12

    현재 이 문제를 고민하고 있는 중인데 제 생각에 문제의 예시에 오류가 있는 듯 하네요.

    아마도 a_i의 부호가 전부 반대로 되어야 할 것 같습니다.

    그 근거는 다음과 같습니다.

     

    1. 문제에서 a_i의 정의에 대입해보면 부호가 전부 반대로 나옵니다.

     

    2. 문제에서 예시로 주어진 벡터들 중 v_1, v_2, v_3 만 선택하면 동일하게 조건을 만족함을 알 수 있습니다. 이때, a_1, a_2, a_3의 값은 전부 -1이라면, 3n+시그마a_i의 값이 6이 나와 모순입니다. 그러나 부호가 반대로 된다면 12가 나오고, 실제 기하학적 의미와 동일한 수치가 나오게 됩니다.

    댓글 작성하기 좋아요0 댓글수3
    •  
      리프 Lv.6 2020.06.20 17:12

      이미 구머님께서 이 부분에 대해 질문을 했는데 답변을 못 들었네요. 확인 부탁드립니다.

      좋아요0
    •  
      최기자 Lv.4 2020.06.25 16:34

      구머 학생의 지적에 댓글을 달았답니다. 구머 학생의 지적이 맞아요. 문제도 수정을 했고요~. 혹시 다른 문제가 있는 걸까요?

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

      구머님 지적 중에서 a_i의 부호가 반대로 되어 있는 것 같다는 지적이 있었는데 그 부분이 수정이 안 되고 그대로 있는 것 같습니다.

      좋아요0
  •  
    Sin X Lv.5 2020.11.05 00:09 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911