국가수리과학연구소 4번
겹치지 않는 경로는 몇 가지?
문제 출제자 : 이석형 수리과학연구소 연구원
직선을 홀수 n개 긋습니다.
이때 어떤 두 직선도 평행하지 않고, 어떤 세 직선도 한 점에서 만나지 말아야 합니다.
그러면 한 직선 위에는 반드시 교점이 n-1개 있습니다.
이제 한 교점에서 다른 교점으로 움직이는 이동을 생각합니다.
점 P와 점 P를 지나는 직선 ℓ의 경우, 점 P가 직선 ℓ의 교점 중 i번째라면 점 P에서 직선 ℓ의 n-i번째 교점으로 이동합니다.
(몇 번째 교점인지는 직선의 어느 쪽에서 세어도 상관없습니다.)
이런 이동을 몇 번이고 활용해서 점 P에서 갈 수 있는
모든 점의 집합을 “경로”라고 할 때,
모든 교점은 절대 겹치지 않는 서로 다른 경로 몇 개로 나눌 수 있습니다.
이 때 서로 다른 경로는 최대 몇 개, 최소 몇 개일까요?
n=7, n=9일 때를 해결하는 것부터 시작해 보세요.
※아래 나온 예시 그림은 n=5일 때 나올 수 있는 직선 배치 중 일부입니다.
각 경우에 흰색 점들이 경로 하나를 이루고, 빨간색 점들이 다른 경로 하나를 이룹니다.
n=5일 때 직선을 배치할 수 있는 방법은 이외에도 2가지가 더 있는데,
이때에도 경로는 2가지로만 나뉩니다.
즉, n=5일 때 서로 다른 경로는 최대 2개, 최소 2개인 셈입니다.
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
Severity: Warning
Message: file_put_contents(/DATA/upload/polymath/latex/aa66042ec80945619f6dd8d8ddf31577.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
[mathdonga.blog.me에서 옮겨 온 댓글입니다]
benedict07242017.03.31. 21:20
최솟값==최댓값 아닌가요?
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
Severity: Warning
Message: file_put_contents(/DATA/upload/polymath/latex/aa66042ec80945619f6dd8d8ddf31577.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
수돌이2017.04.01. 13:39
//추측//
각각의 경로의 점들이 모두 지나는 직선이 존재한다.
//추측//
그 직선 위에서 각각의 경로의 점들은 정확히 두 개 있다.
이 둘을 증명하면 최솟값==최댓값입니다.
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
Severity: Warning
Message: file_put_contents(/DATA/upload/polymath/latex/aa66042ec80945619f6dd8d8ddf31577.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
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
Severity: Warning
Message: file_put_contents(/DATA/upload/polymath/latex/bb04722db2f5a635b76c494d7b141be0.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
benedict07242017.04.01. 21:33
일단 별 모양일 때는 n번째 점에서만 왔다갔다 하므로 입니다.그래서 최솟값
최댓값이라는 것은 증명할 수 있습니다.
benedict07242017.04.01. 21:36
증명하기는 못 할 것 같지만 반례는 못 찾겠네요.
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
Severity: Warning
Message: file_put_contents(/DATA/upload/polymath/latex/aa66042ec80945619f6dd8d8ddf31577.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
엔곰2017.04.01. 22:42
점 P에서 Q로 간다면 점 Q에서 P로 간다.
그리고 이는 항상 일대일 대응.
n=3~9의 경우에서는
의 반례를 못찾겠네요.
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
Severity: Warning
Message: file_put_contents(/DATA/upload/polymath/latex/aa66042ec80945619f6dd8d8ddf31577.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
엔곰2017.04.01. 22:53
k번째 점과 n-k번째 점은 항상 같은 경로고, 이 경로들이 k가 다를 시에 항상 다르면 최소, 최대 모두 라는 게 증명되겠군요.
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: 200
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
Severity: Warning
Message: file_put_contents(/DATA/upload/polymath/latex/aa66042ec80945619f6dd8d8ddf31577.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: 200
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
수돌이2017.04.01. 23:29
그 직선을 지나지 않는 경로가 있다면 경로의 수가 보다 많을 수도 있지 않나요?
수돌이2017.04.02. 01:29
[추측 실패]
경로의 수가 1인 경우도 존재합니다. 그 예시를 찾았습니다.
http://blog.naver.com/dillon0108/220972903453
benedict07242017.04.02. 10:17
이런
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: 200
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
Severity: Warning
Message: file_put_contents(/DATA/upload/polymath/latex/aa66042ec80945619f6dd8d8ddf31577.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: 200
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
수돌이2017.05.12. 22:16
Nicholas그리고 새로 찾은 반례로 를 넘어가는 경우도 있습니다.
n=9일때 별처럼 그리면 (문제에서 예시의 경우는 n=5일 때의 별입니다)
경로의 개수가 총 6개가 됩니다 ^^
서제원2017.04.07. 09:25
위상기하학의 쾨니히스베르크 다리문제로 치환하여 오일러경로와 해밀턴회로 그래프로 풀 수 있을 듯 한데...
최댓값의 하한을 구하는 데에는 수학적 귀닙법을 쓸 수 있을 것 같습니다. 교점이 있는 곳 외부에 두 직선을 그으면 최소 1만큼은 증가하게 됩니다.