본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] [IMO] 58회 국제수학올림피아드 문제 함께 풀어요!
수학동아 2017.07.20 18:03

58회 국제수학올림피아드가 브라질 리우데자네이루에서 열렸습니다. 7월 20일 현재 시험만 끝날을 뿐 아직 결과는 나오지 않았습니다. 따끈따끈한 문제를 함께 풀어봅시다. 엄상일 KAIST 교수님께서 여섯 문제 중 다음 두 문제를 함께 풀어볼만한 문제로 추천해 주셨습니다. 필즈상 수상자인 테렌스 타오가 2009에 열린 IMO 6번 문제를 미니 폴리매스 프로젝트를 통해 수학자들과 함께 풀었던 것처럼 우리도 함께 풀어 다양한 답안을 이끌어내 봐요!

 

► 가장 어려웠던 문제!

문제3. 한 사냥꾼과 보이지 않는 토끼 한 마리가 평면 상에서 다음과 같은 게임을 한다. 토끼의 출발점 A_0와 사냥꾼의 출발점 B_0는 일치한다. 게임의 n-1번째 라운드를 마친 후 토끼가 위치한 점을 A_n_-_1, 사냥꾼이 위치한 점을 B_n_-_1이라 하자. n번째 라운드에서 다음과 같은 세 가지가 순차적으로 발생한다.

(i) 토끼가 보이지 않게 점 A_n으로 움직이고 A_n_-_1A_n의 거리는 정확히 1이다.

(ii) 사냥꾼의 추적기가 점 P_n의 위치를 알려준다. 이 추적기가 알려주는 점 P_nA_n의 거리는 1 이하임이 보장될 뿐이다.

(iii) 사냥꾼은 눈에 띄게 점 B_n으로 움직이고, B_n_-_1B_n의 거리는 정확히 1이다.

토끼가 어떻게 움직이든, 추적기가 어떤 점을 알려주든 상관없이 항상 사냥꾼이 10^9 라운드 후에 그와 토끼의 거리가 100 이하가 되도록 할 수 있겠는가?

 

► 3번보다는 쉽지만 재밌는 문제!

문제 5. 정수 N\geq 2이 주어져 있다. N(N+1)명의 축구 선수들이 한 줄로 서 있고, 이들 중 어느 두 사람도 키가 서로 같지 않다. 알렉스 경은 이 선수들 중 N(N-1)명을 빼내, 2N명의 선수들을 남기되, 남아 있는 선수들이 다음과 같은 N개의 조건을 만족하도록 한다.

(1) 가장 키가 큰 두 선수 사이에는 아무도 없다.

(2) 세 번째로 키가 큰 선수와 네 번째로 키가 큰 선수 사이에는 아무도 없다.

(N) 가장 키가 작은 두 선수 사이에는 아무도 없다.

이렇게 하는 것이 항상 가능함을 보여라.

 

  •  
    shine Lv.1 2017.07.21 09:01

    5번 문제에서 n의 조건이 없는데, n이 2이상의 정수라는 조건인가요?

    댓글 작성하기 좋아요0 댓글수2
    •  
      누군가 Lv.1 2017.07.21 14:23

      문제 원본을 찾아보니  N(n+1),N(n-1)에서 n 이 아니라 N이여서N(N+1),N(N-1)입니다.

      좋아요0
    •  
      조가현 편집장 Lv.4 2017.07.21 16:45

      죄송합니다. 문제를 입력하는 과정에서 대문자 N을 소문자 n으로 잘못 표기했나 봅니다. 혼돈을 드려 죄송합니다! 올바르게 수정했습니다.

      좋아요0
  •  
    몽이 Lv.1 2017.07.22 11:13

    몇 명의 선수들이 줄을 서던지 키의 순서가 123456....이런 식으로 줄배열을 하고 알렉스 경이 마지막부터 키가 작은 순으로 차례대로 몇 명을 빼내면 남은 2N명의 순서는 반드시 N개의 조건을 만족하리라 생각합니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      shine Lv.1 2017.07.22 16:41

      처음에 사람들이 어떻게 서있든 상관없이 가능해야 하는거라 그 방법은 안됩니다.

       

      좋아요1
  •  
    수돌이 Lv.3 2017.07.25 13:35

    이대로 풀면 너무 어려울 것 같아서 (특히 3번은...) 힌트를 조금씩 드리겠습니다!

    3번 힌트:

    토끼가 사냥꾼을 거리 100 초과로 따돌릴 수 있습니다.

    그걸 증명해 봅시다.

    토끼와 사냥꾼 모두 한 라운드에 1의 거리를 움직이므로 사냥꾼이 토끼의 이동 방향을 안다면 토끼는 절대 사냥꾼과의 거리를 벌릴 수 없습니다.

    따라서 토끼는 조금씩 사냥꾼의 이동 방향에 대해 옆으로 움직이되, 사냥꾼이 보기에 토끼가 왼쪽으로 움직였는지 오른쪽으로 움직였는지 모르도록 합니다.

    충분히 사냥꾼의 방향과 옆으로 빗겨갔다면, 자신이 가던 방향으로 경로를 꺾습니다. 그 과정에서 사냥꾼과의 거리가 아아아아아주 조금 늘어납니다.

    이 아이디어를 실제 전략으로 구체화 시키고, 얼마나 늘어나는지를 여러분이 계산해야 합니다. 그리고 그 계산에 따르면 거리를 100까지 벌리는데 10^9 이내의 라운드가 필요함을 보이변 됩니다.

     

    5번 힌트:

    N(N+1)명의 사람들을 연속한 N+1명씩 N개의 그룹으로 자릅니다.

    각 그룹에서 2명씩 잘 뽑아봅시다.

    어떤 알고리즘으로 뽑을지는 여러분이 생각해 보세요.

    댓글 작성하기 좋아요0 댓글수1
    •  
      구머 Lv.5 2017.08.19 13:08

      만약 추적기가 초고성능이라 토끼가 있는 곳만을 계속 가르킨다면 토끼는 사냥꾼과의 거리를 100 이상 벌릴 수 없습니다. 즉, 항상 토끼가 사냥꾼과의 거리를 100이상 벌릴 수 있는 것은 아닙니다.

      좋아요0
  •  
    MainGarden Lv.1 2017.07.25 19:48

    N=2일때 입니다

    6명을 키가 큰 순서대로 기호를 매겼습니다

    a1이 키가 가장 크고>...>a6이 가장 작아요

     

    댓글 작성하기 좋아요0 댓글수1
    •  
      MainGarden Lv.1 2017.07.25 21:03

      5번 문제 푸는 중입니다

      N이 3인 경우는 '처음의 순위가 이웃하는 두 사람이 한 그룹 안에 있을 때/있지 않을 때' 로 풀면(스캔해서 올린 방법) 안 되겠네요

      그것보다는 한 그룹에 4명이니까 '1~12 중 4개의 수를 고르면 두 수의 차가 3 이하인 두 수가 적어도 1쌍 있다' 와

      '남은 8개의 수 중 4개 수를 고르면 두 수의 차가 2 이하인 두 수가 적어도 1쌍 있다'를 이용해야겠습니다

      좋아요0
  •  
    wendy Lv.1 2017.08.19 20:16

    제가 처음이라서 잘 모르는데 질문 5번에서

    N(N+1)에서의 N이랑 조건의 개수 N이랑 다른거죠?

    (설마 그렇지는 않겠죠?)

    댓글 작성하기 좋아요0 댓글수2
    •  
      구머 Lv.5 2017.08.20 13:38

      같습니다^^

      좋아요0
    •  
      매민 Lv.1 2017.08.20 13:45

      1,2등/3,4등/.../2N-1등, 2N등

      이렇게 묶이면 같은 N이라는걸 알 수 있습니다

      좋아요0
  •  
    구머 Lv.5 2017.08.20 20:24

    3번은 사냥꾼이 어떤 전략을 써도 토끼와의 거리가 100 이상 벌어지는 경우가 존재합니다. 지금 학원을 가야 해서 나중에 풀이 적겠습니다.

    (근데 문제에서 거리가 100이 아니라 1000이상인지 아닌지 구별하는 것 아닌가요? 확인 부탁드립니다)

    댓글 작성하기 좋아요0 댓글수3
    •  
      조가현 편집장 Lv.4 2017.08.21 09:37

      100이 맞습니다~!

      좋아요0
    •  
      구머 Lv.5 2017.08.23 00:54

      3번 풀이입니다. 먼저 다음과 같은 특수한 조건을 만족하는 경우를 생각합시다:


      조건 )1)  (i)과정에서 토끼는 나무꾼과 최대한 멀어지려는 방향으로 1만큼 움직인다

      조건 (2)  (ii)과정에서 추적기는 나무꾼의 위치에서(An) 토끼의 위치(Bn+1)를 중심으로 반지름이 1인 원에 그은 두 접점 중 한 점을 알려준다.

      조건 (3) 나무꾼은 운이 매우 나쁘다.

       

      이제 나무꾼과 토끼의 거리, 즉 과 Bn의 거리를 Dn이라고 합시다. 그리고 (i)과정을 시행하면 조건 (1)에 따라 나무꾼과 토끼의 거리는 Dn+1이 됩니다. 이제 과정 (2)를 생각해 봅시다. 점 An이 있고, 나무꾼은 추적기가 알려주는 점 Cn을 알고 있습니다. 이때, 나무꾼은 토끼가 Cn의 왼쪽에 있는지 오른쪽에 있는지 알 수 없고, 그렇다고 한 방향으로 치우쳐서 간다면 조건 (3)에 의해 토끼로부터의 거리가 더 멀어질것입니다. 따라서 나무꾼은 Cn방향으로 1만큼 이동할 것이고, 이로부터 (약간의 계산을 통해)

                                                                                       Dn+1=\sqrt{D_{n}^2+2D_{n}+2-2\sqrt{D_{n}^2+2D_{n}}}

      임을 알 수 있습니다. 이제 D109가 100보다 큼을 보이겠습니다.

       

      먼저 다음과 같은 함수  P(n)=Dn2-Dn-12을 정의합시다. 이때,

                                             P(n)=Dn2-Dn-12=2Dn+2-2\sqrt{D_{n}^2+2D_{n}}=(\sqrt{D_{n}+2}-\sqrt{D_{n}})^{2}=\frac{4}{\sqrt{(D_{n}+2}+\sqrt{D_{n}})^2}>\frac{1}{D_{n}+1}

      가 성립합니다. 이제 D109가 100보다 작다고 가정합시다. 이때, 109이하의 자연수 k에 대해 P(k)는 1/101보다 큽니다. 즉,

                                                                            P(1)+P(2)+....P(109)>10^{9}\times \frac{1}{101} >5X106

      이 성립합니다. 그런데   P(1)+P(2)+....P(109) 은 D1092-D02과 같으므로 10000보다 작습니다. 따라서 10000>5X106에서 모순입니다.

       

      따라서 '항상' 사냥꾼이 토끼와의 거리를 100 이하가 되도록 할 수 있는 것은 아닙니다.

       

       

       

      좋아요0
    •  
      구머 Lv.5 2017.08.23 00:59

      풀이에서 보완해야 할 부분들:

      (1) 제일 처음 토끼가 출발했을 때 사냥꾼은 토끼 중심 원 위에 있게 되는데 이때 접선을 그으면 접점과 사냥꾼의 위치가 같게 됨.

      (2) '사냥꾼이 토끼가 Cn에서 왼쪽방향에 있는지 오른쪽방향에 있는지 모른다' 라는 명제의 조금 더 구체적인 증명이 필요함.

      (3) 109은 제 풀이에서는 쓸데없이 너무 큼. 증명하면서 놓친 부분이 있을 지도 모름. 

      좋아요0
  •  
    구머 Lv.5 2017.08.21 09:38

    5번 풀이: 수학적 귀납법으로 풀어보겠습니다. 

    먼저 편이상 선수들의 키를 1,2,3,....,N(N+1)이라고 둡시다.

    1) 먼저 N=1일 때는 자명하게 성립합니다.

    2) 이제 N=k일 때 문제 조건에 맞게 2k명을 뽑을 수 있다고 가정합시다. 이제 N=k+1일 때를 보면, (k+1)(k+2)명의 사람들을 k+2개씩 순서대로 묶어 k+1개의 그룹을 만듭니다. 그리고 맨 뒤에 있는 그룹을 보면, 비둘기집의 원리에 의해 키가 i(k+2)<x≤(i+1)(k+2) 을 만족하는 x인 선수가 2명 이상 존재하는 음이 아닌 정수 i가 존재합니다. 이제 그 선수 두명을  선수 명단에 남긴 후, 맨 뒤에 있는 그룹을 모두 빼고, 또 키가 i(k+2) 초과 (i+1)(k+2)이하인 모든 선수들을 뺍니다. 그럼 남은 선수들은 정확히 k(k+1)명이고, 또한 먼저 뽑힌 두 선수 사이에 들어갈 수 있는 선수도 없습니다. 이제 처음 가정에 의해 남은 선수들 사이에서 2k명을 뽑은 후, 먼저 뽑은 2명을 합치면 정확이 2k+2명을 뽑을 수 있습니다.

     

    즉, 모든 자연수 N에 대해 (N+1)N명의 선수들 중 문제 조건을 만족하게 2N명을 뽑을 수 있습니다.

    댓글 작성하기 좋아요0 댓글수4
    •  
      구머 Lv.5 2017.08.21 09:39

      중3이라 서술이 조금 부실할 수 있습니다. 양해 부탁드립니다~

      좋아요0
    •  
      shine Lv.1 2017.08.21 11:37

      구머님의 풀이에서 먼저 빼놓은 2명을 A,B 라고 놓겠습니다. 또 일반성을 잃지 않고 두명의 키가 A>B라 합시다.

      말씀하신 방법대로 2k+2명을 뽑았을 때 A,B가 각각 p,p+1번째로 키가 크다고 하면,

      p가 홀수일 때는 문제가 되지 않지만, p가 짝수가 될 때는 A와 p-1번째 사람, B와 p+2번째 사람이 각각 이웃하는 것이 조건이 됩니다.

      그런데 이렇게 되는 경우에 대해서는 고려하지 않으셨더군요.

      이 점에 대해 다시 생각해주시기 바랍니다.

      좋아요2
    •  
      구머 Lv.5 2017.08.21 15:40

      날카로운 지적이네요. 한번 그부분을 수정해보도록 하겠습니다.

      (솔직히 수정 못할것 같음ㅜ)

      좋아요0
    •  
      구머 Lv.5 2017.08.23 22:30

      수정에 성공했습니다! 원래 쓰려고 했던 수학적 귀납법과 수돌이 님의 힌트를 잘 조합하여 풀이를 완성했습니다.

      5번 풀이)

      i) 먼저 N=1일 때는 자명하게 성립합니다.

      ii) 이제 (n-1)n명일때 문제 조건에 맞게 2(n-1)명을 뽑을 수 있는 것은 물론, 선수들을 줄 선 순서대로 n명의 n-1개의 그룹으로 나누고, 각 그룹에서 2명을 뽑았을 때 2(n-1)명을 뽑을 수 있다고 가정합시다. 이제 n(n+1)명일 때를 생각해봅시다. 우선 n+1명씩 n개의 그룹으로 나눈 후, 각각의 그룹에서 2번째로 키가 큰 사람을 뽑은 후, 뽑힌 n명의 사람들 중 키가 가장 큰 사람을 A라고 합시다. 그리고 A가 속한 그룹에서 가장 키가 큰 사람을 B라고 합시다. 이제 A와 B를 뽑은 후, A가 속한 그룹과 각 그룹에서 키가 가장 큰 사람을 제거합니다. 이제 n명씩 n-1개의 그룹으로 이뤄진 사람들이 남는데, 앞에서 한 가정처럼 각 그룹에서 2명씩 뽑아 2(n-1)명을 뽑습니다. 이제 A,B와 2(n-1)명은 문제 조건을 만족하는 2n명이 됩니다.

      좋아요1
  •  
    구머 Lv.5 2017.08.27 18:03

    풀이에 앞서 몇가지를 가정합시다.

    1)풀이에 나오는 n,N은 자연수이고,

    2)나무꾼은 운이 매우 나쁘다.

     

    3번 풀이: 먼저 문제의 시행을 n번 한후 나무꾼과 토끼의 거리를 Dn이라고 가정합시다. 이제 토끼가 사냥꾼에게서 멀어지려는 방향으로 이동하되, \bar{A_{n}B_{n}}을 기준으로 왼쪽(또는 오른쪽)으로 \frac{1}{N}만큼 멀어지게 이동한다고 합시다. 그리고 추적기는 \bar{A_{n}B_{n}}위의 점들 중 하나를 알려줍니다. 그러면 나무꾼은 토끼가 \bar{A_{n}B_{n}}으로부터 왼쪽에 있는지 오른쪽에 있는지 알 수 없게 되므로 \bar{A_{n}B_{n}}위를 따라가게 됩니다. 이 과정을 N번 시행(N번 시행하는 과정을 '구머'라고 정의합시다)하면 토끼는 \bar{A_{n}B_{n}}에서 정확히 1만큼 떨어져있고, An으로부터 거리 N만큼 떨어져있게 됩니다.(N은 자연수) 그리고 사냥꾼은 Bn으로부터 N, An으로부터 N-Dn만큼 떨어지게 됩니다.(N>Dn) 이제 원래 나무꾼과 토끼의 거리와 '구머' 후 토끼와 나무꾼의 거리의 '제곱'의 차를 계산해보면,

                                              D^{2}-{D_n}^2=(\sqrt{N^{2}-1}-(N-D_{n}))^2+1=N^2-2\sqrt{N^2-1}(N-D_{n})+N^2-2ND_{n}=2(N-D_{n})(N-\sqrt{N^2-1})=2(N-D_{n})\frac{1}{N+\sqrt{N^2-1}}>1-\frac{D_{n}}{N}

    이 됩니다. 여기서 N=!2Dn+1!이면 거리의 제곱의 차는 1/2보다 커지게 됩니다. 이제 토끼가 나무꾼과의 거리를 100 초과로 넘길 수 없다고 가정합시다......(a) 그러면 N=201일때 '구머'를 시행하면 거리의 제곱의 차가 1/2만큼 벌릴 수 있습니다. 이때, '구머'를 20000번 시행하면, 즉 문제의 시행을 4020000번 시행하면 거리의 제곱의 차를 10000이상 벌릴 수 있습니다. 즉, 토끼와 나무꾼과의 거리가 100 이상 벌어지게 됩니다. 따라서 이는 (a)에 의해 모순이고, 토끼는 나무꾼과의 거리를 100 이상 벌릴 수 있습니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      구머 Lv.5 2017.08.27 18:07

      원래 있던 기존의 풀이는 '나무꾼이 추적기가 알려주는 점으로부터 왼쪽에 있는지 오른쪽에 있는지 모른다'라는 것을 증명해야 하였지만, 그 부분은 증명이 되어야 한다기 보단 그냥 틀린 것 같았습니다. 따라서 이 부분에 의심의 여지가 없도록 새로운 풀이를 작성하였고, 이 과정에서 수돌이 님의 힌트도 이용하였습니다.(대체...이분은 그냥 천잰것 같아요) 수정이나 제가 빼먹은 부분들은 덧글로 알려주시면 감사하겠습니다.

      좋아요0
  •  
    구머 Lv.5 2017.08.29 00:44

    수학동아 님 제가 쓴 3번 풀이랑 5번풀이 인정해주시는 건가요???

     

    댓글 작성하기 좋아요0 댓글수3
    •  
      조가현 편집장 Lv.4 2017.08.31 16:24

      엄상일 교수님께 구머님의 풀이를 확인한 결과 5번은 풀이가 맞았고, 3번은 아직 부족하다고 합니다. 3번의 경우 조금만 보안하면 맞는 풀이가 된다고 의견을 주셨는데요. 201번 이동 후 사냥꾼의 위치에 따라 토끼가 왼쪽 혹은 오른쪽에 있는 걸 설명해야 한다고 합니다. 좀 더 힘내주세요!

      좋아요0
    •  
      구머 Lv.5 2017.09.03 23:53

      흠..질문을 잘 이해하지 못했는데 혹시  '사냥꾼이 토끼가 \bar{A_{n}B_{n}} 왼쪽 또는 오른쪽에 있는지 모른다' 라는 것을 묻는 것이라면, '구머' 시행 과정에서는 추적기가 알려주는 점들을 모두 이은 직선이 사냥꾼을 지남으로 사냥꾼이 토끼가  \bar{A_{n}B_{n}}(즉, 추적기가 알려주는 점들을 이은 직선) 왼쪽에 있는지 오른쪽에 있는지 또는 그냥  \bar{A_{n}B_{n}}위에 있는지 모르고, 만약 한 방향을 찍어서 간다 하면 조건 1): 나무꾼은 운이 아아아주 나쁘다 에 의해 항상 토끼와 반대방향으로 갈 것입니다.

      좋아요0
    •  
      조가현 편집장 Lv.4 2017.09.04 09:02

      엄상일 교수님의 코멘트를 그대로 이야기 해드리면,

       

      구머 2017.08.23 00:54:18 풀이의 경우 틀린 풀이 : 사냥꾼이 무조건 추적기가 알려주는 점으로만 간다고 가정하는 경우 IMO에서는 0점 처리됐습니다.. 더 논리가 있어야 합니다. 
       
      구머  2017.08.27 18:03:41은 좀더 맞긴 하지만 논리가 여전히 부족합니다. 여전히 사냥꾼이 추적기 알려주는 곳으로만 간다고 주장하는데 근거가 빈약합니다. 물론 조금 더 보완하면 맞는 풀이가 됩니다. 201번 이동후 사냥꾼의 위치에 따라 토끼가 왼쪽 혹은 오른쪽에 있는 것이다라고 가정해 설명해야 합니다. 
      좋아요0
  •  
    럼럼이 Lv.1 2017.12.23 19:10

    수학적 귀납법으로도 증명 도전해봤어요

    숫자는 키라고 보시면 됩니다

    편의상 1은 1cm, 2는 2cm.... 숫자가 클수록 키가 더 크다. 그렇게 보면 되고요

    증명 방법은 비둘기집 원리를 이용한 수학적 귀납법이에요

    k 맞다고 가정 k+1이 맞다부터 하고

    N=2를 후에 했어요

    틀린거면 빤스런함

    댓글 작성하기 좋아요0 댓글수1
    •  
      vorn보른 Lv.1 2017.12.23 22:21

      풀이사진 찍을때 꿀팁! 사진이 가로로 나오는 문제는 찍을때 돌려서 찍으면 된답니다.

      좋아요0
  •  
    nohdaniel Lv.1 2018.01.02 23:10

    문제3 풀이가 대충 나오신 분

    라운드 몇개만 좌표평면 위에... 어떻게 진행되야 되는건지 그림 좀 그려주세요

    전 아무리 해도 거리1에서 쳇바퀴

    댓글 작성하기 좋아요0 댓글수1
    •  
      구머 Lv.5 2018.01.03 00:06

      ..?저요?

      좋아요0
  •  
    Simon Lv.2 2018.05.24 20:27

    어디서 본 문젠가 했더니 art of problem solving IMO Collection에 있었네요

    3번 정답 링크: https://artofproblemsolving.com/community/c6h1480157p8633324

     

    댓글 작성하기 좋아요0 댓글수0
  •  
    우리집고양이 Lv.1 2019.03.23 15:13

    5번 문제를 해석하자면, 1~N(N+1)까지의 정수로 된 어떤 수열을 편한 N개의 구간으로 나누고(A1,A2,A3,A4...AN) 각 구간에서 두 수를 뽑아 그 구간의 시작과 끝이라고 할때(시작을 a,끝을 b로 하여 Ai(ai,bi),ai<bi) 구간으로 줄을 세울 수 있다(ai<bi<ak<bk<aj<bj....) 가 되겠네요. 그러면 편의를 위해 a1<b1<a2<b2... 라고 할게요. n개의 구간에 숫자를 넣는데, n+1이하의 숫자가 두 개 든 구간이 최소 하나 존재하므로 이 구간을 A1으로 쓰면 b1<=n+1 이 됩니다. b1=n+1일 때 a1은 n 이하의 어떤 정수(편의상 1? 가정할때 편함)이고, 나머지 구간들은 n 이하의 정수를 하나씩 갖습니다. 이제 같은 형식으로 b2<=2n+2~~~bn<=n(n+1)이면 증명 끝 하고 참 좋겠는데, A1이 이미 선택되었으므로 첫 번째 시도와 다른 점이 생깁니다. 만약 2N+2이하의 숫자가 두 개 든 구간이 A1이라면 충돌이 생기니까요. 이를 해결하기 위해 다시 구간을 나누기 전의 수열로 돌아갑니다. A1은 수열에서 임의로 잘라낸 구간이므로, 수열의 맨 끝에 있다고 해도 최소 하나의 구간과 맞닿아 있게 됩니다. 즉 다른 구간에서 맞닿아있는 원소 하나 혹은 그 이상을 가져올 수 있죠. 이때 어떤 원소를 어떤 구간으로 옮기던지에 상관없이 b2<=2(N+1)임을 보일 수 있습니다.   ...이런 식으로 하면 될 것 같은데 명확히 서술하는 법을 모르겠어요. 도와주세요..!

    댓글 작성하기 좋아요0 댓글수1
    •  
      우리집고양이 Lv.1 2019.03.23 15:29

      구머님 풀이 좋네요~ 열심히 하다보면 언젠간 저도 잘 풀 수 있겠죠.

      좋아요1
  •  
    우리집고양이 Lv.1 2019.03.25 12:49

    3번 문제에서, N번째 경보기가 울렸을 때 토끼가 있을 범위는 n번쩨 경보기의 위치를 Pn이라 하고 Pn으로부터 반지름N+1-n인 원을 그렸을 때 겹치는 구역과 같으며 (사용할 전략에서, 이 구역은 대체로 PN, 혹은 PN과 PN-1만 따지면 됩니다) 지금 따지는 것은 최악의 케이스고, 최악의 케이스는 토끼가 가능한 구역 안에서 BN과 가장 멀리 있는 것이다. 이러한 최대 길이를 BAN이라 하면 사냥꾼의 최선의 수는 가능한 BN중 최소의 BAN을 갖는 점이다. + 최악의 케이스이므로 경보기는 토끼가 원하는 곳에서 울린다. 로 하면 토끼는 갈길을 가면서 사냥꾼은 경보기 따라 지그재그로 움직이게 할 수 있는 것 같네요.(지그재그의 각도는 점점 작아짐) 계산을 어떻게 할까...

    댓글 작성하기 좋아요1 댓글수0
  •  
    임채민 Lv.1 2021.02.16 20:45

    뒷북이지만 쌉 불가능입니다

    사냥꾼이 멍청해서 점을 따라가지 않고 토끼의 반대방향으로 쭉 갈경우 100 이상의 거리는 당연히 벌려집니다

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

  • ☎문의 02-6749-3911