관리 메뉴

이쁜왕자 만쉐~~

[퍼즐] 등대 문제 본문

퍼즐판

[퍼즐] 등대 문제

이쁜왕자 2012.08.02 14:31

Q1. 등대 20개가 무한평면바다 위에 있고, 각 등대는 18도 만큼의 빛을 비추는 각도를 가진다.
이 때 임의의 등대 위치에 대해서 등대가 빛을 비추는 방향을 잘 조절하면, 바다 모든 곳에 빛이 닿게 할 수 있음을 보여라.


오유에 RGB 님이 낸 문제 

사족 추가)
- 등대는 점으로 간주하며, 그림자는 무시한다.
- 등대의 빛의 도달하는 거리는 무한하다.



18도*20 = 360도 이므로, 방향을 잘 맞추면 가능할 것으로 보인다.

문제의 이해를 쉽게 하기 위해서 문제를 극단적으로 간결화 시켜 보자.

Q2. 등대 2개가 있고, 각 등대는 180도를 비춘다.


간단히 등대가 서로 향해서 빛을 비추면 된다는 것을 유추해 낼 수 있다.

그런데 이게 4개의 등대로 확장되면, 난이도가 급 상승한다.
 

Q3. 등대 4개가 있고, 각 등대는 90도를 비춘다.


가장 심플하게 4개의 등대가 정사각형을 이루고 있다고 가정하면, 정사각형의 중심을 향해서 비추면 된다. 하지만, 정사각형이 아니라 직사각형으로 바꾸면, 무게중심을 향해 비추는 것으로는 해결되지 않는다.

어떤 등대가 비추는 각도 비추는 각도를 k도 라고 하면, 나머지 3개는 반드시 k+90도, k+180도, k+270도 여야 한다.

현재 더이상 진전 없음..


대략 하얀까마귀옹의 아이디어를 정리하면..

정리1) 네 점이 서로 다른 사분면에 위치한다면, 모든 평면을 덮을 수 있다.

각 점은 각각 대각선 방향의 사분면을 모두 덮을수 있도록 비추면, 된다.
만약 두점 이상이 X축 또는 Y축에 위치한다면, 유리한 쪽을 선택한다.

따름정리2) 한점이 원점에 있고, 다른 세점이 서로 다른 사분면에 위치한다면, 모든 평면을 덮을 수 있다.
trivial



4점 중에서 가장 멀리 떨어진 두 점 A,B을 선택하여 두 점을 지나는 직선AB를 그린다. 그러면, 다른 두 점 C,D 는 이 직선을 기준으로 같은 쪽에 있거나, 서로 다른쪽에 있게 된다.

* 서로 같은 쪽에 있는 경우

두 점 C,D 중에서 직선AB에 더 가까운 점을 선택하여, 이를 원점으로 하는 직교 좌표계를 구성한다. 단 X 축은 직선 AB 와 평행하도록 구성한다. 그러면, 한점은 원점에, 나머지 3점은 서로 다른 사분면에 위치하게 된다.

* 서로 다른쪽에 있는 경우..

두 점 C,D 중 아무거나 하나 선택해서 직선AB 에 수선의발을 내림. 그점을 원점으로 하는 직교 좌표계를 구성한다. 단, X축은 직선 AB.



훨씬 더 쉬운 하얀까마귀옹의 방법.

* 점 4개가 볼록 사각형일때

두 대각선의 교점이든, 무게중심이든, 대충 그 내부의 한점을 원점으로 선택하여 4개의 점이 서로 다른 사분면에 위치하도록 직교좌표계 구성.

* 점 4개가 오목 사각형일때 (즉, 3점으로 만들어진 삼각형 내부에 한점이 위치할때)

내부의 한점을 원점으로 하면, 간단히 세점을 서로 다른 사분면에 위치하는 직교 좌표계를 만들수 있음.


ps> 그런데 이 방법을 6개, 8개,, 또는 20개등 더 큰 수로 확장을 어떻게 해야 할지 모르겠음. 

ps2> 홀수의 경우는 2k 의 경우인 짝수일때 해결되면, 점2개를 각각 겹치는 방법으로 간단히 증명 가능.

- 이쁜왕자 -
 
저작자 표시 비영리
신고
3 Comments
  • 프로필사진 지나가다 2012.08.02 16:10 신고 볼록사각형의 경우에는 아무 대각선이나 하나 이어서 그것을 x축이라고 했을 때 x축상에는 두점이 존재합니다. 이 두 점을 왼쪽부터 a, b라고 할때 a가 1사분면, b가 3사분면 쪽을 보이도록 비추게 하고 나머지 두 점이 2, 4분면 쪽을 비추게 하면 될 것 같아요. 그런데 오목사각형의 경우에는 저런식으로 잘 안되네요.^^
  • 프로필사진 이쁜왕자 2012.08.02 16:33 신고 오목 사각형의 경우는, 내부의 한점을 원점으로 잡고, 남은 3개중 한점을 X축에 위치하도록 좌표계를 잡으면, 다른 2점은 반대쪽의 사분면에 각각 위치합니다.
  • 프로필사진 하얀까마귀 2012.08.03 12:09 신고 divide and conquer로 임의의 등대 갯수에 대해 증명 가능한듯. 그림이 없으면 설명이 거식하긴 한데 -_- 기본 아이디어는,

    1. 두개의 직선이 각도 theta를 이루고 원점 O 에서 교차한다고 할때, 그 한쪽에 theta/n 각도의 조명각을 가지는 n개의 등대가 있다면 그 등대들은 O 맞은편의 부채꼴 영역을 전부 커버할 수 있다.

    1.을 증명하면, 평면을 적당히 쪼개서 원래 문제를 증명 가능.

    2. 평면에서 등대들이 있는 영역을 L1, 맞은편 영역을 L2라고 할때 원점 O를 L1 안의 임의의 점 P로 좌표이동시킨다고 했을 때, L1과 L2가 그렇게 이동한 영역을 L1', L2' 라고 한다면 L2'는 L2를 완전히 포함한다.

    3. 앞에 의해 L1'의 영역 안에 원래 L1의 모든 등대가 포함되어 있기만 하다면 O를 적당한 점 P로 좌표이동을 해도 무방.

    P를 잘 움직이면 L1' 안의 등대들 중에서 가장 가장자리에 붙은 등대를 하나 "떼어낼" 수 있음. 그럼 문제는 n-1개의 등대와 theta - (theta/n) 각도의 영역에 대한 문제로 줄어듬. 모든 등대를 처리할 때까지 반복.
댓글쓰기 폼