당연해 보이는데 증명 어떻게 하지

수학 채널

알림 알림 중 알림 취소

구독자 2299명 알림수신 53명 @시스티나

각종 수학 이야기를 해는 채널

질문 당연해 보이는데 증명 어떻게 하지

시스티나

추천 2 비추천 0 댓글 30 조회수 508 작성일 2023-07-08 03:54:12

⚠️ 이 게시물은 작성자가 삭제할 수 없도록 설정되어 있습니다.

https://arca.live/b/math/80563534

조건: 유클리드 평면 상에 두 점 A, B와 장애물이 있다. 장애물은 유한 개의 매끄러운 닫힌 곡선과 그 내부로 이루어져있다.

가설: 장애물을 통과하지 않고 A, B를 잇는 최단경로는 선분과 장애물의 표면의 부분으로만 이루어진다. 이때, 각 선분의 양 끝점은 A, B 또는 장애물 위의 점이다.

댓글 [30] 글쓰기

ㅇㅇ

2023-07-08 04:08:42 답글

수학적인 증명은 아니지만 물리적인 아이디어로 임의의 경로가 있을 때 그 경로 위에 실을 올리고 당기는 방식으로 하면 극소가 되는 모든 경로가 저 조건을 만족함을 보일 수 있음. 여기서 극소라고 한 이유는 실로 대체하면 장애물과의 위치 관계 때문에 생기는 가능한 경로의 제한이 생기니까 그냥 그렇게 얘기함. 수학적인 증명을 하려면 귀납법으로 하면 될거 같긴 한데

펼쳐보기▼

시스티나

2023-07-08 04:09:39 답글

물리적이라는게 좀 다듬으면 변분법인 듯?

펼쳐보기▼

ㅇㅇ

2023-07-08 04:10:35 답글

저걸 수학적으로 기술하면 변분이 되겠지. 그냥 직관적으로 저렇게 생각하면 당연하게 느껴지긴 하지

펼쳐보기▼

시스티나

2023-07-08 04:10:44 답글

Specificity

2023-07-08 04:10:13 답글

대충 생각해본다면,

장애물이 구성요소 n개로 이루어져있다고 한다면, 처음에 선분AB(경로0)를 끊는 구성요소가 아무 것도 없다면 그걸로 끝. 만약 선분AB를 끊는 구성요소가 하나 있다면, 그것만 있다고 생각했을 때 구한 최단경로(경로1)는 가설을 만족함. 이 때, 어떤 다른 구성요소가 경로1을 끊어버린다면 다시 구한 최단경로(경로2)는 역시 가설을 만족함.

구성요소가 유한 개 있으므로 어딘가에서 이 과정은 종료되며, 그 때의 경로는 가설을 만족함.

펼쳐보기▼

시스티나

2023-07-08 04:10:26 답글

Specificity

2023-07-08 04:18:55 답글

아 그런데 경로0이 바로 최단경로가 되지 않는 경우들에서, 구성요소 하나씩 붙여나갈 때마다 최단경로 구할 때 무조건 기존 계열을 사용하는 게 아니라 반대편 계열을 사용해야 할 가능성도 있네요. 결론이 달라지는 건 아니지만..좀 복잡한 듯

펼쳐보기▼

Hess

2023-07-08 06:38:14 답글

과정에서 최단만 남길게 아니라 minimal한걸 다 남기면서 진행하고 맨 마지막에 최소만 선택하면 될듯

펼쳐보기▼

수학싫어요

2023-07-08 06:13:42 답글

해석학특) ㅈㄴ 자연스러워 보이는게 막막함

펼쳐보기▼

시스티나

2023-07-08 06:35:04 답글

다경

2023-07-08 08:21:57 답글

장애물 위의 점이 아닌 두 경로위의 점 x,y에 대해 x에서 y까지 경로가 선분이 아니라고 하자. 그렇다면 x에서 y까지 최단거리가 아니므로 경로는 더 짧게 구성할 수 있다. 경로가 장애물의 경계 외에서 곡선 부분경로를 하나 이상 갖는다면 이 과정을 반복할 수 있으므로 참.
이거 아님?

펼쳐보기▼

시스티나

2023-07-08 08:52:53 답글

정규식

2023-07-08 08:46:36 답글

이거 완전 그리디 알고리즘

펼쳐보기▼

시스티나

2023-07-08 08:52:58 답글

다경

2023-07-08 09:10:55 답글

어떻게 그리디?

펼쳐보기▼

정규식

2023-07-08 09:13:08 답글

각 순간순간에(수학적인 표현은 아니지만) 직선으로 그을 수 있다면 직선으로 긋고보면 되는 문제 아니야?

펼쳐보기▼

다경

2023-07-08 09:13:58 답글

그게 이해가 잘 안되는데 예를 들어 설명좀

펼쳐보기▼

정규식

2023-07-08 10:00:31 답글

*수정됨

가정상 현재 위치(?)에서 어떤 점으로 직선을 그어도 장애물의 곡선과 교차하지 않아야함
가능한 B에 가까운 방향으로 유향선분을 잡으면 장애물 위 접선의 일부분(0<길이) 또는 어떤 선분으로 나타날텐데
아무튼 이게 최단경로랑 일치한다고 가정

A에서 B로 바로 가는 유향선분이 존재하면 해당 경로가 최단경로니까 패스하고
중간에 장애물이 존재해서 바로 가지 못한다면 A를 지나는 장애물 위의 접선을 잡게될텐데
X에서 Y로 가는 경로는 X에서 Y를 이은 직선이 가장 짧으므로 장애물에 접하는 위치P0에 가기 위해서는 해당 경로가 가장 빠름
장애물에 마지막으로 접하는 위치 Pn과 n-1번째로 접하는 위치 P(n-1)의 최단경로까지 구해내고 나면
이렇게 만들어진 부분적 최단경로중 한 점에 인접한 두개의 경로를 뽑아봤을 때(A->B, B->C 두가지)
A->B->C가 아닌 경로는 그보다 길거나 장애물의 곡선과 교차하니까 A->C의 최단경로는 A->B->C이므로
이렇게 부분 최단경로들을 합쳐서 전체 최단경로를 만들 수 있다고 생각함

펼쳐보기▼

다경

2023-07-08 10:06:13 답글

장애물이 단순폐곡선인 것으로 충분하니까 내가 생각한 그리디의 반례로 A에서 B로 가는 직선거리 위에 수많은 동심원이 있고 왼쪽(또는 오른쪽)이 일부 잘려 있어서 최단거리가 잘린 단면을 따라가는 경우를 생각했는데 위에 써준 알고리즘만으로는 동심원을 수많이 돌면서 안으로 들어갔다가 다시 바깥의 동심원으로 나가서 도달하는 경로를 뱉을 수도 있다고 생각하는데 맞음?

펼쳐보기▼

정규식

2023-07-08 10:09:00 답글

C 모양으로 단순화할 수 있을텐데 아무튼 어떤 지점에 도달하고 나면 거기선 바로 직선을 그어버릴 수 있으니까 괜찮지 않을까?하고 생각함

펼쳐보기▼

정규식

2023-07-08 10:10:36 답글

C에서 곡선이 안으로 들어가는 그 위치에서 따라서 안쪽으로 들어간다면 그건 B에 가까운 방향이 아니잖아

펼쳐보기▼

다경

2023-07-08 10:13:25 답글

https://arca.live/b/math/80590464
b에 가까운 방향의 예시

펼쳐보기▼

정규식

2023-07-08 10:15:03 답글

아 폐곡선이 딱 하나인것만 생각해봤는데 다시 보니까 여러개일수도 있구나
이건 또 난감하네

펼쳐보기▼

다경

2023-07-08 10:16:18 답글

하나인 것만 봐도 저 그림에서 제일 바깥 한 겹만 가져왔을때 대충 반례같기도?

펼쳐보기▼

정규식

2023-07-08 10:17:28 답글

ㄴㄴ 하나는 분명히 괜찮다고 생각함 애초에 경로가 접선이 아니잖아

펼쳐보기▼

다경

2023-07-08 10:22:11 답글

일단 내 풀이는 모든 장애물에 대해 직선거리로 이동할 수 있는 경우를 모두 포함한 그래프를 그리고 중복방문을 허용하는 다익스트라 굴리면서 로테이팅 캘리퍼스 삼분탐색으로 시뮬레이션 굴리는건데 더 나은 방법을 모르겠음

펼쳐보기▼

정규식

2023-07-08 10:23:47 답글

다익스트라는 무조건 최단경로 존재하니까 싹다 따져보자랑 똑같은얘기 아님?
그게 본문에 나온 경로랑 일치한다는건 어떻게 보이는데

펼쳐보기▼

다경

2023-07-08 10:24:46 답글

본문에 나온 경로는 특정 경로가 아니고 최단경로가 특정 성질을 만족한다는거 아님? 그 성질을 만족하는 모든 경로를 탐색하자는거임

펼쳐보기▼

정규식

2023-07-08 10:16:14 답글

그래도 그리디로 풀리지 않을까 싶은데 증명은 못하겠다..

펼쳐보기▼

정규식

2023-07-08 10:05:18 답글

아주 짧은 직선을 아주 많이 잡아놓고 곡선이랑 똑같다고 말하는게 올바른 얘기인지는 제대로 배워본 내용이 아니라 잘 모르겠다

펼쳐보기▼

댓글 작성

업로드 중

0초

녹음 중지 삭제

글쓰기

전체글 개념글

최근 최근 방문 채널

최근 방문 채널

전체 수학 정보 공지·운영 질문 교육 정보 유머 간단한 문제 정답/풀이 답변 운영 대회

번호 제목

작성자 작성일 조회수 추천

질문 궁금한게 대학교 수학과 들어가면 기호논리학을 수강하나요? [6]

cree 2023.07.09 411 1

고딩 수2 개념 질문 도와주세요.. [6]

ㅇㅇ (211.241) 2023.07.09 422 0

간단한 문제 오늘자 서울과학고 2차 기하문제 [22]

_Theorem_ 2023.07.09 866 2

질문 ⁴2가 왜 2¹⁶이죠? [7]

ㅇㅇ (218.233) 2023.07.09 650 1

원래 본전공은 [2]

방랑자 2023.07.09 714 11

정칙? 이라는게 뭔가요 [11]

ㅇㅇ (133.28) 2023.07.09 392 0

질문 풍요가 멸망을 초래한다는 걸 들어본 적이 있습니다 [44]

wertox 2023.07.09 1115 10

질문 근데 소수가 왜 중요한것임? [3]

ㅇㅇ 2023.07.09 393 0

특정 식이 정수임을 증명하는 문제에서 [9]

kusakusa 2023.07.08 400 1

유머 가장 억울한 입체도형은? [10]

ㅇㅇ 2023.07.08 1071 13

정답/풀이 아래 자작문제 해설

Ha_Rua 2023.07.08 320 0

간단한 문제 자작문제 풀어볼 사람 [8]

Ha_Rua 2023.07.08 587 2

간단한 문제 오류 찾기에서 오류 찾기 [6]

이과지망생 2023.07.08 443 0

유머 비전공자를 위한 소개 [4]

fgh 2023.07.08 1058 14

최단거리 문제 솔루션 관련 [1]

다경 2023.07.08 295 2

질문 당연해 보이는데 증명 어떻게 하지 [30]

시스티나 2023.07.08 508 2

질문 고딩 질문 하나 [9]

ㅇㅅㅇ 2023.07.07 433 0

간단한 문제 다변수함수 문제 [3]

ㅇㅇ (59.26) 2023.07.07 399 -1

간단한 문제 회전 변환 문제 [1]

사렌좋아 2023.07.07 362 -10

간단한 문제 등차수열 문제 [1]

ㅇㅇ (121.179) 2023.07.06 431 2

간단한 문제 적분 문제 [2]

사렌좋아 2023.07.06 425 -2

선형대수 기초적인 질문 [2]

ㅇㅇ (112.171) 2023.07.06 360 0

수학 정보 폐비셰프 필터, 체비셰프 다항식, 그리고 GraphConvolutionNetwork.

뿌리골무 2023.07.06 347 2

질문 이렇게 해도 됨? [6]

ㅇㅇ (211.235) 2023.07.06 377 2

간단한 문제 다변수 함수 문제 [6]

사렌좋아 2023.07.06 386 -13

Lang I.45 조금 다르게 해봄

Hess 2023.07.05 240 0

질문 수학 약어중에 [2]

illusion 2023.07.05 388 2

질문 단순폐곡선과 영역 [6]

자유극대필터 2023.07.05 358 0

잘못 붙힌 원뿔곡선의 이름들? ytb [3]

뿌리골무 2023.07.05 336 2

실시간에 마우스로 2차원 푸리에변한 해보자 [7]

뿌리골무 2023.07.04 807 7

글쓰기

전체글 개념글