| [ QuizWit ] in KIDS 글 쓴 이(By): iLUSiON (BBiZi Land) 날 짜 (Date): 1998년 6월 29일 월요일 오후 01시 27분 49초 제 목(Title): 리: 땅파기 2 흠 폼프씨가 아니라고해서 깜짝놀랐습니다. 가만히 생각해보니까 아니게 할수가 있긴 있군요. ^^ 그런데 솔직히 이게 답인지는 여전히 확실하지 않습니다. 위에서 다른분이 말한 최소거리보다 더 적은 값이 나오지만. 몇가지 다양한방법으로 생각해보았는데, 반드시 다음이 필요합니다. 1. 반드시 짧은 선분들로 구성되어야한다. (면적으로 구성된게 아니라 그리고 곡선으로 구성될경우 선분으로 더적게 만들수있으니까.) 2. 반드시 4개의 꼭지점을 지나야한다. 만약 어느한점이라도 안지나게될경우, 꼭지점은 extream point of convex hull 이기때문에 이 안지나는 꼭지점을 중심으로 조그마한 엡실론 네이버후드를 그릴수있고 이 엡실런 네이버후드를 관통하는 직선을 만들수 있기때문에. 3. 결국 반드시 최소한 4개의 선분으로 구성될것. 그러나, 이 4개의 선분이 굳이 연결될필요는 없을것. ^^ 하지만 A= 이 4개의 선분의 집합 이라고 불리면 Px(A) = the projection of A onto x-axis 마찬가지로 와이축으로의 프로젝션은 반드시 정사각형의 양변의 길이를 커버해야합니다. 이러한 프로젝션성질은 정사각형의 중점을 관통하는 어떠한 직선위의 프로젝션에 대한 성질로 확장시킬수있습니다. 위의 3가지 성질을 만족하는 집합에서 최소거리를 구하면 그게 폼쁘씨가 원하는 답입니다. 문제는 이 이게 최소거리다! 라고 증명하는일이지요. (뽐쁘씨 증명이 필요없이 한눈에 나오는답이시면 꼭가르쳐주세요. ^^) 제가생각해본건 다음과같습니다. 정사각퓽� 한대각선과 나머지 두변으로 구성하는 직각삼각형과 이 직각삼각형을 마주하는방향으로 있는 대각선의 1/2의 집합에서 최단거리를 구합니다. 즉 직각삼각형의 세꼭지점을 연결하는 세개의선분에서 이 직각삼각형을 커버할수있게끔 답이 나와야합니다. 대충해보면, 3선분은 연결이되는데 나머지 한선분은 따로이 떨어져있는 형태가 나오는군요. 위에서말한 최소거리인 '스테너그리드'보다 더적게나옵니다. 문제는 이게 정말 최소냐하는건데, 그런것같다! 라노느 부족한것같네요. ^^ 아마도 뽐쁘씨께서 이부분은 명확히 최소임을 증명(?) 해주실수있을듯. [일반화] 이문제의 결국 일반화문제 (삼각형으로) 가 위에서 설명한방법에 다시나왔네요. 일반화는 위에서 말한 3가지조건을 만족시키면서 어떻게 대충구할수있지 않을까합니다. 최소라는 단서가 빠진다면, 4각형에서 재미있는 구조를 리커시브하게 (프렉탈처럼) 정의할수도 있습니다. 정사각형을 지나는 직선과교점을 만드는 집합 = 정사각형의 싸이즈의 1/4만한 적은 정사각형을 지나는 직선의 교점을 만드는 집합 + 나머지 귀퉁이부분 직각삼각형을 지나는직선과 교점을 만드는 집합 이니까 결국 1/4만큼 계속 축소되는꼴로 리커시브하게 이 집합을 정의하게만들수도있습니다. 그렇다면 이런집합에서의 최소거리에 대해서도 정말 최소인지 증명이 필요하겠네요. ^^ 뽐쁘씨 이문제에대한 코멘트 눈빠지게 기다리니까 빨리올려주세요. / 안녕하세요 환상입니다 팬여러분 안녕하세요 환상입니다 팬여러분 안녕하세요 환상입니다 팬여러분 안녕하세요 환상입니다 팬여러분 안녕하세요 환상입니다 팬여러분 안녕하세요 환상입니다 팬여러분 어 이상하다 왜 줄이 딱 맞는거지? / |