미술관 문제(The art gallery problem) 또는 박물관 문제(The museum problem)라고 불리는 문제는 단순 다각형 모양의 미술관 모퉁이 최적의 위치에 경비원을 세우는 경우, 이 경비원들이 미술관 전체를 볼 수 있으려면 경비원의 수를 얼마까지 줄일 수 있는가 하는 문제입니다.
이 문제는 1973년 수학자 Victor Klee가 전자계산학과 교수였던 Václav Chvátal에게 냈던 문제입니다. 크바탈은 오래지 않아 이 문제를 풀었고, 그 결과는 1975년 그의 논문에 소개됩니다. 이것을 미술관 정리(The art gallery theorem)라 합니다. 이 문제에 흥미를 느낀 많은 학자들은 이 문제를 변형해서 전시실에 기둥과 같은 장애물이 있는 경우, 경비원이 움직이는 경우, 또는 전시실이 여러 층으로 개방되어 입체적으로 봐야 하는 경우 등 다양한 모델에 대해서 연구를 계속해 왔습니다. 여기서는 단순히 원래의 문제만 살펴보기로 합니다.
크바탈은 $n$개의 벽을 가지는 다각형 모양의 전시실에는 최대 $[n/3]$명의 경비만 있으면 충분하다는 사실을 알아냅니다. 우선은 아래 그림과 같은 전시장의 경우에 $n/3$명의 경비가 필요함을 증명한 후 다른 경우에 대해서는 수학적 귀납법으로 증명을 했습니다.
1978년, Steve Fisk는 아주 간단한 증명법을 알아냅니다. 그는 다각형의 원래 꼭짓점을 적절히 연결해서 삼각형으로 다각형을 조각낸 후 삼각형의 세 꼭짓점에 다른 색이 칠해지도록 차례대로 점에 색을 칠한 후, 같은 색으로 칠해진 지점에 경비원이 있으면 전시실을 다 볼 수 있다는 것을 설명하고, 비둘기집 원리에 의해 다각형의 꼭짓점 개수의 1/3개 이하의 점에 색칠된 색이 있을 수밖에 없다는 아이디어로 증명을 했습니다. 그러고보니 너무 당연하죠.
위 그림은 가상의 전시실을 가정해서 Fisk의 방식을 따라서 해 본 것입니다. 어느 색이든 같은 색으로 칠해진 곳에 경비가 자리잡으면 전시실 전체 감시가 가능합니다. 16개 점 중 빨강, 초록이 5개씩, 파랑이 6개 이므로 정리가 잘 맞음을 알 수 있습니다. 위 그림의 경우는 특별히 화살표로 표시한 두 부분에만 경비가 있어도 감시가 가능하므로 $[n/3]$이 최적값은 아니라는 것을 알 수 있습니다.