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

Problems

폴리매스 문제 보기

문제

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

2018.07.11

같이 풀어볼까?

네이버밴드 구글플러스

59회 국제수학올림피아드가 루마니아 클루지나포카에서 열렸습니다. 이제 막 수학올림피아드 여섯 문제가 공개됐는데요. 엄상일 KAIST 교수님께서 추천한 3, 4번 문제를 풀어보세요. 폴리매스 문제를 푸는 것처럼, 다양한 아이디어와 풀이를 이끌어내 보자고요!

 

► 폴리매스 친구들에게 추천하는 3번 문제!

문제3

정수들의 다음과 같은 정삼각형 모양의 나열을 역파스칼삼각형이라 하자. 가장 밑줄에 있는 수들을 제외하고, 나머지 각 수들은 바로 밑에 있는 두 수의 차(의 절대값)이다. 예를 들어, 다음 나열은 네 개의 가로줄로 이루어지고 1부터 10까지의 모든 수가 등장하는 역파스칼삼각형이다.

2018개의 가로줄로 이루어지고 1부터 1 + 2 + · · · + 2018 까지의 모든 수가 등장하는 역파스칼삼각형이 존재하겠는가?

 

 

 

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

문제 4

좌표평면 위의 점 (x, y)에 대하여, xy가 모두 20 이하의 양의 정수일 때, 이 점을 지점이라 하자. 400개의 지점이 처음엔 모두 비어 있다. 수영과 상일이 번갈아 빈 지점에 돌을 놓고, 수영이 먼저 시작한다. 수영은 자기 차례에 빈 지점에 새로운 빨간 돌 하나를 놓되, 빨간 돌이 놓인 어떤 두 지점 사이의 거리도 \sqrt5가 되지 않도록 놓는다. 상일은 자기 차례에 빈 지점에 새로운 파란 돌 하나를 놓는다. (파란 돌은, 돌이 놓여 있는 지점과의 거리에 상관없이, 빈 지점 어디에나 놓을 수 있다.) 이 게임은 한 사람이 더 이상 돌을 놓을 수 없을 때까지 진행한다. 상일이 어떤 전략으로 파란 돌들을 놓든지 상관없이, 수영이 항상 최소한 K개의 빨간 돌을 놓을 수 있는 K 값 중 가장 큰 값을 구하여라.

 

댓글 43

  • 김우현 기자 2018.07.13 18:02:56

    3번 문제는 대회에 참가한 학생들도 무척 어려워 했다는 소식~crying

    좋아요0 댓글수2
    • 0gzg♡ 2018.07.15 22:03:44

      수가 중복되어도 1번 이상씩만 나오면 돠는거죠?

      좋아요0
    • 김우현 기자 2018.07.16 09:21:52

      삼각형을 이루는 수가 총 1+2+\cdots+2018개인데, 1부터 1+2+\cdots+2018까지 모두 등장해야 하므로 정확히 한 번씩만 나와야 할 거예요~surprise

      좋아요0
  • Euler 2018.07.16 16:05:20

    되는지 안되는지가 문제인데 풀이를 써야 하니까 어렵겠네요. 그래도 결론을 알고 풀면 쉬우니까 컴퓨터 프로그램으로 시도해 볼게요.(얼마나 걸릴지는 모르겠지만)

    좋아요0 댓글수1
    • Euler 2018.07.16 16:22:01

      이건 그냥 써본 겁니다.

      두가지 풀이가 생각났는데

      하나는 규칙을 찾는거고

      하나는 논리로 다 따져보는겁니다.

      1.

      f(n)을 밑변의 수의 갯수가 n개인 역 파스칼 삼각형을 만들수 있으면 1, 없으면 0의 값을 가진다 하자.

      f(1)=1

      f(2)=1

      3:1

      3

      1 4

      5 6 2

      4:1

      (문제 참조)

      이 f(n)함수를 점화식으로 바꿀 수 있으면 좋을것 같네요. 근데 문제가 f(n)이 1이여도 그렇게 만들어진 역 파스칼 삼각형이 n-1로 만들어진 것과 나머지 몇 개들의 수, 즉 삼각형과 선 모양으로 분리할 수가 없다는 거에요.

      그림으로 설명하면

      .

      ..

      ...

      ....

      이게

      .

      ..

      ...

      ....

      로 분리되는데 

      그 삼각형이 한 변이 n-1인 역 파스칼 삼각형이 아니라는 거에요.

      그러므로 되는 거에서 규칙성을 찾아볼 수밖에 없네요.

      저 지금 어디 가야되서 나중에 올릴게요. 엄청난게 생각난게 있는데 일단은 지금 끝낼게요.

      좋아요1
  • math 2018.07.19 20:43:48

    3번문제

    그냥 떠올라서 하는 말이기는 한데, 이 역파스칼삼각형은 밑의 두 수의차가 위의 수를 결정하는데, 홀수를 odd에서 따와 o라 하고, 짝수를 even에서 따와 e라 하면, 위의 수가 o라면, 밑의 수는 o와 e 또는, e과 o만 나올 수 있고, 위의 수가 e라면 밑의수는 e와 e 또는, o와 o만 나올 수 있고, 문제에서의 경우는 숫자의 개수가 1부터 2018까지의 합이므로, 계산하면 2037171이고, 그러면 o는 1018586개, e는 1018585개가 되고, o와 e의 개수가 이 숫자를 만족하는 모든 경우의 수를 따진다음에, 숫자들이 o면 o칸에 넣고, e면 e칸에 넣어서 이 역시 만족하는 경우의 수를 컴퓨터로 찾으면 되지 않을까요?(찾는 방법이 문제이겠지만)

    좋아요0 댓글수2
    • 수학장 2018.07.19 23:17:54

      정보) 국제수학올림피아드에서는 컴퓨터를 쓸 수 없습니다.(아마도? 참여 안 해봐서 자세히는 모르지만요)

      좋아요1
    • math 2018.07.20 15:12:50

      그.. 그렇군요 ㅠㅠ.

      좋아요0
  • 모두다같이 2018.07.24 11:57:43

    10처럼 가장 큰 수는 꼭 맨 아래에 있어야겠어요.

    문득 1에서 10까지의 역파스칼삼각형이 다른 유형도 있을까 궁금했는데.그 중 두개를 더 찾을 수 있었어요.

    3

    7 4

    2 9 5

    8 10 1 6

    ----------------

    5 2

    4 9 7

    6 10 1 8

    좋아요0 댓글수4
    • math 2018.07.24 17:19:06

      10처럼 가장 큰 수는 맨 아래에 있음과 더불어, 9는 10과 1의 차에서만 만들어질 수 있으므로, 세번째 또는 네번째줄에만 존재할 수 있고, 8은 1과 9의 차 또는 2와 10의 차에서만 만들어질 수 있는데, 10은 맨 아래에만, 9는 세번째, 네번째줄에만 존재할 수 있으므로, 8은 두번째, 세번째, 네번째에만 존재할 수 있게되는 것이죠.

      좋아요1
    • 모두다같이 2018.07.25 00:28:31

      그렇군요. 정리 고마워요!

      8이 만들어지는 경우가 (9,1) (10,2)이고,

      8이 두번째 줄에 있다면 10은 가장 아랫줄(4번째줄)에 있어야 하니 셋째 줄엔

      (9, 1) 경우만이 오게 되네요.

      하지만 9도 (10, 1)에 의해서 만들어지는데

      이대로 4번째 줄에 (10, 1)을 세우면

      1이 셋째줄, 넷째줄에 중복되니

      8또한 셋째줄, 넷째줄에서만 가능하군요.

       

       

      좋아요0
    • 모두다같이 2018.07.25 01:33:41

      (8을 셋째줄에 일일이 넣어 경우를 확인하니

      셋째줄에도 8이 있을 수 없네요..)

       

      좋아요0
    • math 2018.07.26 12:48:51

      아~~ 그렇군요! 

      좋아요0
  • 모두다같이 2018.07.25 02:24:31

    4

    5 1

    2 7 6

    8 10 3 9

    경우를 합쳐서

    1 + ... + n 에 대해

    n = 4 일때 역파스칼삼각형 개수는 4개인 것 같아요.

     

    n을 4에서 1씩 차츰 늘릴 때

    역파스칼삼각형 개수가 0 일때가 있다면

    최초로 0일 때가 언제 일까요?

    좋아요0 댓글수0
  • 모두다같이 2018.07.25 17:30:57

    그런데 n = 5에서는 역파스칼삼각형이 나올 수 있을까요?

    좋아요0 댓글수1
    • 모두다같이 2018.07.25 19:17:08

      오랫동안 모든 경우를 다 고려하니

      4 9

      7 11 2

      8 1 12 10

      6 14 15 3 13

      한 경우만 나오는 것 같군요..

      좋아요0
  • math 2018.07.26 15:34:53

    6개의 가로줄로 이루어지고 1부터 21까지의 모든 수가 등장하는 역파스칼삼각형은 존재하지 않습니다.(제 수작업이 틀리지 않았더라면요.)

     

    만약 6개의 가로줄로 이루어지고 1부터 21까지의 모든 수가 등장하는 역파스칼삼각형이 존재한다면, 이 역파스칼 삼각형은 제가 위의 댓글에서도 적어놨듯이 e와 o를 이용해서 서술할 수 있습니다. 그리고 이 역파스칼삼각형에서 e의 개수는 10개, o의 개수는 11개입니다. 그러면 이를 역으로 이용하여 만약 e와 o가 각각 10개, 11개를 이용해서 역파스칼 삼각형의 형태를 만들 수 있는 구조가 존재하지 않는다면, 이는 곧 6개의 가로줄로 이루어지고 1부터 21까지의 모든 수가 등장하는 역파스칼 삼각형이 존재하지 않는다는 뜻이 되는 겁니다.

     

    그래서 수작업으로 직접 구해 보았습니다. 삼각형이 성립하는 구조가 있을 때, 이 구조를 시계방향으로 120도 돌리면 삼각형이 나오게 되는데, 이 삼각형은 밑의 두 수가 짝수, 홀수 또는 홀수, 짝수로 되어있으면 위의 수가 홀수이고, 밑의 두 수가 짝수, 짝수 또는 홀수, 홀수로 되어있으면 위의 수가 짝수입니다. 그러므로, 이제 조합가능한 모든 삼각형을 일일히 해보면 되는데, 이때 이 삼각형이 역파스칼 삼각형이 성립하는 구조인 e가 10개, o가 11개라면 이 삼각형은 각 짝수와 홀수에 알맞은 수를 대입하였을 때, 역파스칼 삼각형이 될 가능성이 있게 되는 것입니다. 

     

    최종적으로 총 64가지의 모든 삼각형의 경우의 수를 구하고, 그것은 e와 o의 개수가 맞는 것을 찾아 본 결과... e가 10개, o가 11개인 경우는 단 한 개도 없었습니다!(제가 실수하지 않았더라면요.)

     

    이를 토대로 6개의 가로줄로 이루어지고 1부터 21까지의 모든 수가 등장하는 역파스칼 삼각형은 존재하지 않는다는 결과를 도출해 낼 수 있습니다.

    좋아요0 댓글수5
    • 모두다같이 2018.07.26 16:33:45

      그렇군요!!

      좋아요0
    • 모두다같이 2018.07.27 21:25:02

      홀수짝수 배치확인을 통해

      n = 6 외에도 어떤 n값들이

      역파스칼삼각형을 가질 수 없는 지

      호기심이 들어요.

      좋아요0
    • 21세기오일러 2018.07.29 17:21:20

      math 님의아이디어로 n이7일때 해본결과 짝수로 시작할경우 5가지경우가있었습니다.

      좋아요0
    • 21세기오일러 2018.07.29 17:28:39

      e는 짝수고 o는 홀수입니다.

      e

      ee

      eee

      oooo

      eoeoe

      eeooee

      oooeooo

       

      e

      ee

      ooo

      oeoe

      oeeoo

      oeeeoe

      eooooee

       

       

      e

      oo

      eoe

      ooee

      eoeee

      ooeeee

      oeooooo

       

      e

      oo

      oeo

      oeeo

      oeeeo

      eooooe

      eeoeoee

       

       

      e

      oo

      eoe

      eeoo

      eeeoe

      eeeeoo

      oooooeo

      로 짝수로시작할때 다섯가지입니다.

       

      좋아요0
    • math 2018.07.29 18:09:11

      컴퓨터 프로그램으로 해본 결과 나머지도 찾았습니다.

      o

      eo

      eeo

      oooe

      eoeoo

      eeooeo

      eeeoeeo

       

      e

      ee

      ooo

      eoeo

      ooeeo

      eoeeeo

      eeooooe

       

      o

      oe

      eoo

      ooeo

      eoeeo

      ooeeeo

      eoeeeeo

       

      o

      eo

      eeo

      eeeo

      eeeeo

      oooooe

      eoeoeoo

       

      o

      eo

      ooe

      oeoo

      oeeoe

      oeeeoo

      oeeeeoe

       

      o

      oe

      oee

      eooo

      ooeoe

      oeooee

      oeeoeee

       

      o

      oe

      oee

      oeee

      oeeee

      eooooo

      ooeoeoe

      좋아요0
  • 여백 패르마 2018.07.27 11:23:32

    그런데 주니어 폴리매스가 뭔가요?????????????????

    좋아요0 댓글수2
    • 모두다같이 2018.07.27 12:18:23

      그렇네요 새로운 코너인가봐요! 

      좋아요0
    • 김우현 기자 2018.07.27 14:14:32

      과연 뭘까요!!laugh

      좋아요0
  • 바람개비 2018.07.27 22:06:28

    안녕하세요. 여기에 질문을 해도 되는지는 모르지만 폴리매스 문제에 대해 3가지 묻고 싶습니다.

     

    1. 이 사이트의 모든 문제는 검증된 해결책이 존재하나요?

    2. 역으로 여러분들이 협력하여 내놓은 증명을 어떻게 검증하나요?

    3. 문제에 관한 것이면 어떤 글이든 쓸 수 있는 건가요?

     

    윗문제보단 간단한 질문일테니 빠른 답변 기대하겠습니다.

    좋아요0 댓글수3
    • orbital 2018.07.28 13:37:23

      1. 아니요, 해결책을 모르는것도 있어요

      2. 증명은 출제하신분 (교수님등)이 검증해 주시고 멘토가 검증해주기도 해요

      3.  문제에 관련된것이라면 어떤것이든 상관 없을듯하네요.

       

      좋아요0
    • 김우현 기자 2018.07.29 15:31:16

      orbital 친구가 잘 설명해줬네요. 풀이 검증에 대해 덧붙이자면,

      ①대한수학회 문제: 멘토의 확인을 거친 뒤 출제자(교수님) 확인

      ②국가수리과학연구소 문제: 출제자(연구원님) 확인

      의 과정을 거칩니다~.blush

      좋아요0
    • 바람개비 2018.07.31 23:27:46

      답해주신 두분께 감사드립니다.smiley

      좋아요0
  • 21세기오일러 2018.07.29 17:36:18

    지금까지1,2,3,4,5,7개의 가로줄이 있으면 가능하고 6개의 가로줄이 있으면 불가능합니다

    제추측으로는 소인수분해했을때 한 가지 종류의 숫자만 나오면 가능하고 두가지 이상의 숫자가 나오면 불가능한것같습니다.

    즉,소수와 제곱수만 가능한것 같습니다.

    좋아요0 댓글수1
    • math 2018.07.29 18:18:03

      그런데, 역파스칼삼각형의 구조를 따르는 홀짝삼각형의 구조가 없음은 역파스칼삼각형이 존재하지 않는다는 것은 맞지만, 역파스칼삼각형의 구조를 따르는 홀짝삼각형의 구조가 있음은 역파스칼삼각형이 존재함은 증명이 필요한 부분이 아닐까요?

      역파스칼삼각형이 존재한다 = p, 역파스칼삼각형의 구조를 따르는 홀짝삼각형이 존재한다 = q일때, p->q라는 것은 확실하고, 이의 대우인 ~q->~p는 성립하지만, 이의 역인 q->p는 성립할 수도, 성립하지 않을 수도 있기 때문입니다.

      좋아요0
  • 수돌이 2018.07.31 22:20:05

    한가지 힌트를 드리자면, 홀수와 짝수 분석을 통한 접근은.. 불가능합니다.

    저도 시험장에서 홀수짝수에 빠져서 벗어나지 못하고 쩔쩔매다가 결국 못 풀었습니다.. 휴ㅠㅠ

    실제 채점기준에도 "모듈러를 통한 접근 (어떤 수로 나눈 나머지)에는 부분점수 0점을 부여한다" 라고 나와있더군요

    좋아요0 댓글수1
    • math 2018.07.31 22:44:51

      그렇군요 ㅠㅠ.

      좋아요0
  • 구머 2018.07.31 22:47:44

    우선 4번은 100개는 확정적으로 놓을 수 있습니다(체스판처럼 나눠서 검은색에만 도배). 답이 100일지는 잘 모르겠지만..

    좋아요0 댓글수0
  • 구머 2018.08.03 21:06:08

    그저 추측이긴 하지만, imo 스타일(?)대로면, n>5인 경우는 성립하지 않는다가 성립할 듯 합니다. 게다가 modular 조건을 쓰지 말라고 떡밥까지 던져줬으니..

    좋아요0 댓글수4
    • 구머 2018.08.11 21:35:42

      풀이가 나왔네요. 일단 저 추측은 맞았다!!

      좋아요0
    • 모두다같이 2018.08.13 15:42:43

      n이 6이상일때부터는 역파스칼삼각형이 불가능하다니 신기한데요!

      구머님, 풀이가 있는 주소 알려주실 수 있을까요? 부탁드립니다~

      좋아요0
    • 구머 2018.08.25 22:34:20

      확인이 늦었네요 죄송합니다. 페이스북에서 한국수학올림피아드 사이트 가시면 답 올라와숩니다.

      좋아요0
    • 모두다같이 2018.08.26 14:56:46

      와 많은 도움되었습니다. 고맙습니다!

      좋아요0
  • 바람개비 2018.08.04 22:43:50

    3번 문제의 삼각형에서 서로 두칸 띄어진 세 수 사이에도 대다수 규칙을 만족하는데, 문제 푸는데 도움이 될지는 모르겠네요.

    그리고 기자분 말대로 4번이 훨신 쉽고 답도 나와 있는데 왜 푸시는 분이 거의 없는지....

    좋아요0 댓글수0
  • 매크로장인 2018.08.19 11:49:24

    문제 4번에 대하여

    K=100입니다

    증명)

    1) K\geq 100

    (wlog) x+y=2k를 만족하는 지점 (x,y)에 대하여 어떠한 점도 거리\sqrt{5}가 되지 않는다.

    이러한 점의 수는 총 200개이며 상일이가 그중 반절인 100개의 지점을 차지한다면

    수영이는 항상 100개의 지점에 빨간 돌을 놓을 수 있다.

    2) K\leq 100

    상일이는 다음과 같은 전략으로 수영이가 100개를 초과하여 차지하는 것을 막을 수 있다;

    20\times 20 의 격자를 4\times 4 격자 25개로 나누어 보자.

    1 6 7 4
    5 2 3 8
    8 3 2 5
    4 7 6 1

    각 칸은 하나의 점을 뜻하며 모든 격자판에 다음과 같이 넘버링 한다.

    수영이가 i에 적힌 곳에 빨간 돌을 놓으면 상일이도 i가 적힌 곳에 파란 돌을 놓는다.(1\leq i\leq 8)

    1,2,3,4만 보았을 때 수영이가 그 중 3개를 골라 빨간 돌을 놓았을 때 파란 돌과 거리가 \sqrt{5}가 되는 돌이 적어도 하나는 반드시 존재한다.

    따라서 수영이는 한 격자판에 1,2,3,4 중 2개, 5,6,7,8 중 2개, 총 4개의 빨간 돌을 놓을 수 있다.

    4\times 25=100, 수영이는 따라서 100개 이상의 빨간 돌을 놓을 수 없다.

     

    1과 2에 의하여

    K=100이다

     

     

     

     

    좋아요0 댓글수0
  • 매크로장인 2018.08.25 20:50:31

    문제 3번에 대하여

    층수를 k라했을때 예입니다

    K=1

    1

    K=2

    2

    1 3

    K=3

    3

    1 4

    5 6 2

    K=4

    4

    62

    175

    9 10 3 8

    K=5

    5

    9 4

    2 11 7

    10 12 1 8

    13 3 15 14 6

    각 층에 1부터 k까지중 하나씩만 나타나는 것과 관련이 있어보이네요 다른 반례가 나오면 모르겠지만

    좋아요0 댓글수0
  • 김우현 기자 2018.09.17 00:12:25

    국제수학올림피아드 정답이 궁금한 친구들을 위해 정답 해설 영상의 링크를 공유합니다!

    www.facebook.com/pg/KoreanMathOlympiad/videos/?ref=page_internal (페이스북 로그인 필요)

    좋아요0 댓글수0