수학동아 - 폴리매스

폴리매스 문제

아직 아무도 답을 모르는 문제에 도전하세요!

[국가수리과학연구소] 국24. 다시 도망간 개구리

수학동아 2018.12.03 00:02 조회 2587

페이스북 트위터 카카오톡 카카오스토리 네이버블로그 네이버밴드

국가수리과학연구소 24번

다시 도망간 개구리

문제 출제자 : 백진언 수리과학연구소 연구원

개구리 한 마리가 수직선 위에 앉아있다. 이번에는 가은이 대신 나은이가 손을 뻗어 개구리를 잡으려 한다. 개구리를 잘 잡는 나은은 한 번 손을 뻗으면 길이가 1인 구간 안에 있는 개구리를 모두 잡을 수 있다. 손을 뻗을 때마다 구간의 위치를 바꿀 수 있지만, 구간의 길이를 늘이지는 못한다. 만약 손을 뻗었는데 개구리를 못 잡으면 개구리는 일정한 간격만큼 일정한 방향으로 점프한다. 이때 개구리의 처음 위치와 뛰는 간격, 방향은 알 수 없다.

[문제]

나은이 원하는 만큼 손을 뻗을 수 있을 때, 유한 번 안에 항상 개구리를 잡을 수 있을까? 나은이는 한 번씩 손을 뻗고, 손을 뻗을 때마다 개구리가 잡혔는지 여부만 알 수 있다.

만약 나은이가 $n$ 번째 시도에서 손을 뻗을 수 있는 구간의 길이가 $n^{^{-\alpha}}$ 이면 항상 유한 번 안에 개구리를 잡을 수 있을까? 만약 그렇다면, $\alpha$ 의 최댓값은 얼마일까? 여기서 $\alpha$ 는 양수다.

※알립니다.

Simon 친구가 1번을, Q 친구가 2번 문제를 해결했어요! 이로써 24번 문제 '해결'입니다.

이전글 국23. 순열 품은 수열

다음글 국25. 심심할 땐 NIM과 함께!

문제 찜하기 목록보기

댓글 작성하기

아인수타인 Lv.12 2018.12.03 07:11

1,2번 모두 개구리가 있는 위치는 실수 범위겠죠?(정수 범위면 저번과 거의 비슷한 방법으로 하면 되가지고...)

댓글 작성하기 좋아요1 댓글수1
- 김우현 기자 Lv.5 2018.12.03 20:59
  
  네, 실수 위치입니다!
  
  좋아요0
YEElight Lv.1 2018.12.04 01:57

길이가 1인 구간에서의 실수의 개수도 비가산 무한이니까 유한번 시행 안에는 못 잡지 않을까요?

댓글 작성하기 좋아요0 댓글수1
- 아인수타인 Lv.12 2018.12.04 09:20
  
  실수가 비가산 무한이긴 하다만 이번엔 개구리를 잡을 수 있는 범위가 훨씬 넓어 무조건 못 잡는다고는 단정 짓기 힘들 것 같습니다.
  
  좋아요0
베네딕트0724 Lv.6 2018.12.04 06:25

전 저번 문제도 이해를 못한 터라 이번 문제도 못 풀겠군요

댓글 작성하기 좋아요0 댓글수0
아인수타인 Lv.12 2018.12.04 09:21

일단 제 개인적인 느낌으로는 가능할거 같네요.(어디까지나 '추측'입니다.)

댓글 작성하기 좋아요0 댓글수0
CoderLab Lv.4 2018.12.04 21:40

1번문제는 귀류법으로 풀어봐야 할 것 같아요!

댓글 작성하기 좋아요0 댓글수4
- CoderLab Lv.4 2018.12.04 21:41
  
  아참! 수열을 이용해 풀어보는 것도 좋을 것 같아요~
  
  좋아요0
- CoderLab Lv.4 2018.12.05 21:37
  
  일방적으로 수열을 이용해 귀류법으로 풀어낸다면 1번문제는 안됀다고 70%정도 확신이 드는데, 어떻게 될지는 저도 모르겠습니다.
  
  좋아요0
- 아인수타인 Lv.12 2018.12.07 09:34
  
  귀류법은 저도 괜찮다고 보는데, 수열...은 좀 뭐할거 같네요. 이게 개구리가 뛰는 범위, 개구리가 처음 있는 위치 등 조건이 정수인 게 없거든요. 수열은 a_1,a_2,a₃,... 등 정수여야 하잖아요. 물론 나은이가 잡는 범위는 정수지만, a₁을 구해야 합니다. 이렇게 되면 a_n을 뭘로 잡을지부터 문제가 발생합니다.
  
  좋아요0
- CoderLab Lv.4 2018.12.07 18:49
  
  생각해보니 그렇네요.
  
  좋아요0
냐뇨기 Lv.1 2018.12.07 05:23

전 3학년이라서 포기 할께여....

댓글 작성하기 좋아요0 댓글수2
- CoderLab Lv.4 2018.12.07 18:50
  
  저는 4학년인데 포기는 아직 이른 듯 합니다.
  
  좋아요0
- s.pie Lv.6 2020.10.26 07:38
  
  헉!! 저도 3학년 입니다!
  
  좋아요0
아인수타인 Lv.12 2018.12.07 08:58

저도 지난 문제도 이해를 못해서 이것도 못풀거 같지만 일단 할 수 있는 데까진 해 볼 생각입니다. (대한수학회 문젠 이해부터가 어려워 풀 게 매스펀 제외하고는 이거밖에 없어요ㅠㅠ)

댓글 작성하기 좋아요0 댓글수0
디듀우 Lv.7 2018.12.09 06:26

지난번 문제와 유사하게 풀 수 있을 것 같습니다! 개구리의 시작위치 s, 한 번에 움직이는 거리를 v라고 하고 (s, v)순서쌍 꼴로 좌표평면 위의 모든 실수에 가능한 모든 개구리를 대응 시킬 수 있습니다. (t+1)번째에 이 좌표평면 위에서 잡을 개구리를 선택해 잡는다고 하면 수직선의 s+vt위치에 손을 뻗으면 됩니다. 그 값이 n이라고 하면, 그 양쪽 범위 n-0.5~n+0.5에 해당하는 개구리를 잡을 수 있습니다. 일단 s+vt=n을 만족하는 개구리 좌표평면 위의 모든 개구리와, v를 가로축이라고 하면 그 위아래로 0.5만큼 범위 안의 개구리도 잡히겠군요. s+vt=n이 일차함수 형태를 띨 테니, t번째에 시작위치 s, 움직이는 거리 v인 개구리를 잡기 위해 n으로 손을 뻗으면 s=-tv+n-1과 s=-tv+n+1 사이의 모든 개구리를 잡을 수 있습니다.이러한 꼴의 범위로 순서를 잘 정해 손을 뻗어 개구리 좌표평면을 빈틈없이 덮을 수 있다면 1번 문제의 답은 참이 됩니다. 하지만 손을 뻗을 때마다 기울기에 관여하는 t가 증가합니다. 처음엔 기울기가 0이지만 두 번째는 1이 되기 때문에 두 범위에 간격이 생깁니다. 1보다 큰 t의 범위로는 x축이 커지는 방향 혹은 작아지는 방향으로 한쪽밖에 덮을 수 없습니다. 그리고 새 범위와 그 이전 범위 사이에는 더 큰 간격이 생깁니다. 예를 들어 x축이 작아지는 방향의 간격을 덮는다면 t가 커질 뿐만 아니라 y절편에 관여하는 n이 작아집니다. t가 항상 양수이므로 새 간격(사실 양쪽으로 생기지만)이 생기는 x축이 커지는 방향으로는 더 넓은 간격이 생기게 됩니다. 그 반대 방향을 덮는다고 해도 같은 원리로 더큰 간격이 생기므로 새 간격을 덮으려고 할수록 t가 커져서 더 많은 간격이 생깁니다. 따라서 1번의 답은 '불가능하다'라고 생각합니다. 틀린 부분 있으면 알려주세요!

댓글 작성하기 좋아요0 댓글수9
- 깜냥 Lv.1 2018.12.09 06:57
  
  그런데 2번에서 α가 양수이므로 구간의 길이는 항상 1 이하일 것이고 이는 1번보다 개구리를 잡기 힘들다는 뜻이므로
  
  1번이 불가능하면 2번도 자연스레 불가능해지니까 1번이 가능해야 하지 않을까요?
  
  좋아요0
- 디듀우 Lv.7 2018.12.09 21:10
  
  2번의 답도 불가능일 수도 있지 않을까요?
  
  좋아요0
- 깜냥 Lv.1 2018.12.10 01:10
  
  물론 그럴 수도 있는데...만약 그렇다면 2번 문제를 낸 의미가 없어집니다. 1번이 불가능하면 2번을 풀 필요가 없으니까요.
  
  그리고 α의 최댓값을 구하라는 말이 괜히 있는 게 아닐 것이기 때문에 1번이 가능하다는 것이 좀 더 합리적인 추측(?)이 아닐지요.
  
  좋아요0
- 디듀우 Lv.7 2018.12.10 06:30
  
  그렇다면 어디가 잘못되었을지 생각해봅시다!
  
  좋아요0
- 아인수타인 Lv.12 2018.12.10 08:12
  
  제 생각엔 지난번과 거의 비슷하면 이 문제를 낸 의미가 없어지니 아예 다른 방식으로 접근해도 좋을 것 같다고 생각합니다. (물론 맞을 거란 확신은 하지 않습니다.)
  
  좋아요0
- 아인수타인 Lv.12 2018.12.10 08:15
  
  그리고, 나은이가 잡는 범위가 1이란 뜻이 아니라, 나은이가 뻗은 위치와의 거리가 1이하이면 잡을 수 있다는 뜻 아닌가요? 그렇게 되면 n-1~n+1의 범위가 됩니다.
  
  좋아요0
- 디듀우 Lv.7 2018.12.11 00:58
  
  구간의 길이가 1이라고 했으니 구간의 중점에 손을 뻗는다고 생각하면 n-0.5~n+0.5의 범위가 맞지 않을까 싶네요.
  
  좋아요0
- 아인수타인 Lv.12 2018.12.11 09:21
  
  그런가...? 이건 김우현 기자님이나 출제자분께서 언급을 해줘야 할 거 같네요.
  
  좋아요0
- 김우현 기자 Lv.5 2018.12.11 18:49
  
  디듀우 친구 말대로 길이가 1인 구간입니다~. 단, 손을 뻗은 점을 중심으로 좌우로 0.5씩 나눌 필요는 없고 길이가 1이기만 하면 어떤 구간을 택해도 상관없습니다. 단위가 점에서 선분으로 바뀐 셈이에요!
  
  좋아요0
Simon Lv.2 2018.12.12 03:41

A PHP Error was encountered

Severity: Warning

Message: mkdir(): Permission denied

Filename: libraries/Common.php

Line Number: 202

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 202
Function: mkdir

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: Warning

Message: file_put_contents(/DATA/upload/polymath/latex/7deac02ede7733025b906e81180b85a1.gif): failed to open stream: No such file or directory

Filename: libraries/Common.php

Line Number: 213

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 213
Function: file_put_contents

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: Warning

Message: mkdir(): Permission denied

Filename: libraries/Common.php

Line Number: 202

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 202
Function: mkdir

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: Warning

Message: file_put_contents(/DATA/upload/polymath/latex/980f75e673fbcf23974967a97a3d1373.gif): failed to open stream: No such file or directory

Filename: libraries/Common.php

Line Number: 213

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 213
Function: file_put_contents

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

지난번과 비슷하게 풀립니다.

우선, n번째에 a+nb에 존재하도록 실수 a, b를 잡을 수 있음은 자명합니다.

이때, a와 b를 구하는 것이 문제가 될 것 입니다.

나은이가 k부터 k+1까지 검증하면, (a, b) 평면에선 $k\leq a+nb \leq k+1$ 이 검증된 것과 같습니다.

다시말해, 이 문제는 위 부등식을 n이 자연수일때를 모두 이어붙여 평면을 채울 수 있느냐를 묻고 있습니다.

이가 가능함은 어떤 자연수 m에대해, m부터 유한개의 위 부등식을 이용해 한 단위셀을 채울 수 있는지를 묻는 것가 같습니다.

단위셀을 0.5*0.5정사각형으로 보고 보여봅시다.

우선 n=m일때의 부등식은 k가 0이 되도록 맞춥시다.

(정사각형이 원점에 있다고 해도 무방하니 그렇게 하였습니다.)((0, 0)부터 (0.5, 0.5)까지 입니다.)

그 뒤, k를 0.5로 설정하여 a=0.5그래프의 부분을 조금 채웁나다.

지금 채워진 a=0.5그래프의 가장 윗 점을 k=a+nb그래프가 지나가도록 k를 계속 설정해주면 $\sum _{i=m+1}^\infty \frac{1}{i} =\infty >\frac{1}{2}$ 이므로 언젠가는 전체가 채워지게 됩니다.

(b축이 a=0.5보다 빨리 채워짐은 몇 개만 그려보면 쉽게 알 수 있습니다.)

따라서, 가능합니다.

댓글 작성하기 좋아요0 댓글수6
- 디듀우 Lv.7 2018.12.12 07:45
  
  검증한다는 것은 손을 뻗어 그때 그 위치에 개구리가 있는지 확인한다는 뜻인가요?
  
  좋아요0
- Simon Lv.2 2018.12.12 23:31
  
  네
  
  좋아요0
- 디듀우 Lv.7 2018.12.13 03:30
  
  a,b가 의미하는 것은 무엇인가요?
  
  좋아요0
- 김우현 기자 Lv.5 2018.12.19 04:24
  
  백진언 연구원이 확인한 결과 Simon 친구의 풀이가 정답으로 판명됐습니다.
  
  아래 Q 친구도 비슷한 아이디어로 풀었네요. 축하해요!
  
  좋아요0
- 김우현 기자 Lv.5 2018.12.20 02:53 비밀댓글
  
  비밀 댓글이 등록 되었습니다!
- Simon Lv.2 2018.12.22 10:39 비밀댓글
  
  비밀 댓글이 등록 되었습니다!
Q Lv.4 2018.12.17 21:50

(a 를 (초기 위치 - 뛰는 간격)으로 정의해야 n=1 부터 시작할수 있겠네요. 종이에는 초기위치라고 써있는데 감안해주시면 감사하겠습니다.ㅠㅠ)

1번만 시도해보았습니다. 잘못된 부분 지적해주시면 감사하겠습니다. 증명을 쓰는것이 익숙하지 않아서 이렇게 써도 되는건지 잘 모르겠네요ㅠㅠㅠ

댓글 작성하기 좋아요0 댓글수5
- Q Lv.4 2018.12.17 21:50
  
  (1번 이어서)
  
  좋아요0
- Q Lv.4 2018.12.17 23:02
  
  2번도 시도해보았습니다
  
  좋아요0
- 김우현 기자 Lv.5 2018.12.19 04:26
  
  1번 문제의 아이디어는 Simon 친구와 비슷하지만, 좀더 자세하게 써주었네요! 2번 문제 역시 잘 풀었습니다. 1, 2번 문제 모두 해결입니다. 축하해요!
  
  좋아요0
- 김우현 기자 Lv.5 2018.12.20 02:54 비밀댓글
  
  비밀 댓글이 등록 되었습니다!
- Q Lv.4 2018.12.20 08:56 비밀댓글
  
  비밀 댓글이 등록 되었습니다!
베네딕트0724 Lv.6 2018.12.19 04:37

오 금방 해결됬네요. 추가 문제는 거절하겠습니다.

댓글 작성하기 좋아요1 댓글수1
- 김우현 기자 Lv.5 2018.12.19 07:57
  
  좋아요0
아인수타인 Lv.12 2018.12.19 09:38

쩝... 내년 1월까지 (또)기다려야겠네요...

댓글 작성하기 좋아요0 댓글수0