>평면 상의 A와 B 두 지점 사이의 거리가 1mile 이다.
>
>당신이 A에서 B로 N개의 직선으로 이루어져 있는 길( 동시에 당신과 B 점과의 거리는 매순간 가까워지는 길 )을 따라 간다고 가정할 때,
>가능한 가장 먼 길의 길이를 N의 함수로 표현하시오.
>
>다음은 원문입니다.
>
>Points A and B are on a plane surface, 1 mile apart. Suppose you must walk in a path consisting of N straight lines from point A to point B, such that at all times your (Euclidean) distance to point B is decreasing. What is the longest possible route length (as a function of N)?
>
풀이를 올리겠습니다.
구하고자 하는 루트의 거리를 D(N)이라 합시다. 그 루트를 R이라 합시다.
이해를 돕기 위해, R을 이루고 있는 각 직선들의 끝부분과 점 B를 직선으로 잇습니다.
R의 각 직선들은 그 끝 부분에서 그 부분에서 점 B까지 이은 직선과 수직으로 만나야 합니다. 예각으로 만나면, 매 순간 가까워진다는 조건에 어긋나는 것이고, 둔각으로 만나면, 가장 먼 길이 아니게 됩니다.
그렇다면, R을 이루고 있는 각각의 직선 길이는 위에서 그린 보조선 사이의 각을 선분 AB에 가까운 쪽 부터a1,a2,.....a(n-1)이라 하면, A와 B사이의 직선거리는 D(1) 이므로 ( 물론 이 문제에선 D(1)=1 )
D(1)*sin(a1), D(1)*cos(a1)*sin(a2), D(1)*cos(a1)*cos(a2)*sin(a3), ..... 이 됩니다.
이 경우에 D(N)은 위 값들의 합이 됩니다. 즉, D(N) = D(1) * T = T 의 꼴이 됩니다. ( D(1) 의 길이를 곱하는 꼴 )
D(N+1)의 경우, 보조선 사이의 각을 선분 AB에 가까운 쪽 부터 a1,a2,.....a(n) 이라 하면,
D(N+1) = 1 * sin(a1) + D(N) * cos(a1)이 됩니다. N+1의 선분으로 이루어진 루트 R에서
점 A에서 선분 AB와 임의의 각을 두고 출발 했다고 할 때,
점 B에서 이은 선분과 수직이 되는 점(P라 하자)까지 직선으로 이동해야 합니다. 그 이후부터는 직선 PB에서
N개의 직선으로 이루어진 루트 R( 거리는 D(N) * cos(a1) )을 찾는 것과 같습니다.
따라서 D(N+1) = 1 * sin(a1) + D(N) * cos(a1) 입니다.
삼각함수에 관한 지식을 이용해, D(N+1) = sqrt(D(N)^2 + 1) * sin(a1 + A)
단, sinA = D(N)/sqrt(D(N)^2 + 1) , cosA = 1 / sqrt(D(N)^2 + 1) 0<A<90
D(N+1) 은 최대의 거리 이므로, D(N+1) = sqrt(D(N)^2+1) 이 됩니다.
D(1) = 1 = sqrt(1) 이므로, D(N) = sqrt(N)이라 가정하면, D(N+1) = sqrt(N+1) 이 되므로,
수학적 귀납법에 의해 D(N) = sqrt(N) 이 됩니다. (단, N 은 양의 정수 )
공책에 쓰면서는 쉽게 설명하겠는데, 글로 표현하려니 어렵네요;;
그럼.. 이만 풀이를 마칩니당.
|