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

Problems

폴리매스 문제 보기

문제

[대한수학회] [IMO] 58회 국제수학올림피아드 문제 함께 풀어요!

2017.07.20

같이 풀어볼까?

네이버밴드 구글플러스

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) 가장 키가 작은 두 선수 사이에는 아무도 없다.

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

 

댓글 28

  • shine 2017.07.21 09:01:37

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

    좋아요0 댓글수2
    • 누군가 2017.07.21 14:23:44

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

      좋아요0
    • 수학동아 2017.07.21 16:45:41

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

      좋아요0
  • 몽이 2017.07.22 11:13:12

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

    좋아요0 댓글수1
    • shine 2017.07.22 16:41:52

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

       

      좋아요1
  • 수돌이 2017.07.25 13:35:52

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

    3번 힌트:

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

    그걸 증명해 봅시다.

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

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

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

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

     

    5번 힌트:

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

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

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

    좋아요0 댓글수1
    • 구머 2017.08.19 13:08:33

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

      좋아요0
  • MainGarden 2017.07.25 19:48:22

    N=2일때 입니다

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

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

     

    좋아요0 댓글수1
    • MainGarden 2017.07.25 21:03:10

      5번 문제 푸는 중입니다

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

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

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

      좋아요0
  • wendy 2017.08.19 20:16:50

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

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

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

    좋아요0 댓글수2
    • 구머 2017.08.20 13:38:09

      같습니다^^

      좋아요0
    • 매민 2017.08.20 13:45:36

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

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

      좋아요0
  • 구머 2017.08.20 20:24:46

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

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

    좋아요0 댓글수3
    • 수학동아 2017.08.21 09:37:55

      100이 맞습니다~!

      좋아요0
    • 구머 2017.08.23 00:54:18

      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
    • 구머 2017.08.23 00:59:48

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

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

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

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

      좋아요0
  • 구머 2017.08.21 09:38:16

    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
    • 구머 2017.08.21 09:39:33

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

      좋아요0
    • shine 2017.08.21 11:37:46

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

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

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

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

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

      좋아요2
    • 구머 2017.08.21 15:40:31

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

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

      좋아요0
    • 구머 2017.08.23 22:30:47

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

      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
  • 구머 2017.08.27 18:03:41

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

    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 댓글수2
    • 구머 2017.08.27 18:07:58

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

      좋아요0
    • 구머 2017.08.31 20:21:59

      어..근데 보니까 제가 사냥꾼이란 말을 안 쓰고 나무꾼이란 말을 쓰고 있었네요...(ㅋㅋㅋㅋㅋㅋㅋㅋ) 

      좋아요0
  • 구머 2017.08.29 00:44:10

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

     

    좋아요0 댓글수3
    • 수학동아 2017.08.31 16:24:21

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

      좋아요0
    • 구머 2017.09.03 23:53:09

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

      좋아요0
    • 수학동아 2017.09.04 09:02:15

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

       

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