당신 소유의 미술관은 현재 심각한 적자에 시달리고 있습니다

돈을 어떻게 충당할지 고민하던 중, 삼삼오오 모여 노가리를 까고 있는 경비원들이 당신의 눈에 들어옵니다

당신은 꼭 필요한 인원만 남기고 나머지 인원을 정리해고 하고자 합니다

남겨야 하는 경비원은 몇 명일까요?

세 가지 가정:

1. 경비원은 한 자리에 고정된 채 경비를 선다

2. 경비원의 시야는 무한하고, 시야각에는 제한이 없다

3. 단, 위치 상 벽에 가려져 보이지 않는 부분은 감시할 수 없다

위의 조건에 맞춰서 필요한 경비원의 수를 계산해보자

미술관이 다음과 같이 간단하게 생긴 구조라면,

단 한 명의 경비원 만으로도 충분히 모든 구역을 감시할 수 있음

(경비원이 다른 곳을 보는 동안 뒤로 도둑이 드는 상황은 고려하지 않도록 하자)

그럼 다음과 같이 총 3m개의 벽이 있는 복잡한 형태의 미술관에는

모든 구역을 커버하기 위해 최소 몇 명의 경비원을 배치해야 할까?

이렇게 뾰족하게 튀어나온 꼭짓점에 경비원을 한 명씩 배치한 다음에

복도 전체를 감시하는 경비원까지, 총 m+1명 세워 놓으면 될 것 같은데?

아니, 1번 경비원의 자리를 왼쪽 위로 옮겨 놓으면 한 명을 굳이 더 고용하지 않고도

모든 구역을 충분히 감시할 수 있음!

그렇다면 여기서 질문:

총 n개의 벽, 즉 n개의 꼭짓점이 있는 미술관에는 몇 명의 경비원이 필요할까?

가장 간단한 예시를 들어보자

위의 그림처럼 꼭짓점이 3개 있는 삼각형 모양의 구역에 경비원이 총 3명이 있지만

사실 나머지 2명은 필요 없는 인력임

왜냐? 두 명이 없어도 나머지 한 명이 모든 구역을 커버할 수 있거든

따라서 우리는 하나의 삼각형 구역의 꼭짓점마다 

서로 다른 색의 옷을 입힌 경비원을 한 명씩 배치할 거야

왜 이렇게 하는지는 나중에 가면 알게 됨

이제 12개의 꼭짓점을 가진 복잡한 구조의 미술관을 생각해보자

이렇게 꼭짓점끼리 적당히 이어 여러 개의 삼각형 구역들로 분할한 다음

각 삼각형마다 파랑, 빨강, 노랑 경비원들이 여러 명 들어가지 않고

한 삼각형 구역에 각 색깔의 경비원이 딱 한 명씩만 들어갈 수 있도록 적절히 배치해 주자

그렇게 배치하는 방법이 없으면 어떡하냐고? (4색 문제)

다행히 3가지 색깔만으로 배치하는 방법이 존재한다는 걸 누군가가 증명해 놓았음

증명 과정은 귀납법을 이용하는데 간단히 설명하면

1. 3개의 꼭짓점을 가진 도형(삼각형)은 자명하게 배치할 수 있고

2. k개의 꼭짓점을 가진 도형에 배치할 수 있다고 가정하면

3. k+1개의 꼭짓점을 가진 도형은 적절한 대각선으로 분할해서 꼭짓점 개수를 줄인 다음 각각 배치한 후에 다시 합치면 되겠지

그런데 앞서 말했듯이 한 삼각형에는 딱 한 명만 있어도 된다 그랬지?

그러니까 위 그림의 색칠한 부분에서 있는 노란색, 빨간색 경비원 4명은 필요 없는 인력임

따라서 같은 색 옷을 입은 경비원만 남기고 모두 해고하면

다음과 같이 4명의 경비원 만으로도 모든 구역을 커버할 수 있음

만약 꼭짓점의 개수가 3의 배수가 아니라면,

같은 방법으로 경비원들을 적당히 배치한 다음에 가장 적은 색깔만 남기고 모두 지우면 되니까

필요한 경비원 수는 다음과 같음

따라서 꼭짓점이 n개인 미술관이 어떤 모양을 하고 있더라도, 

⌊n/3⌋명의 인원으로 충분히 모든 구역을 커버할 수 있음

( ⌊ ⌋ 기호는 내림 기호임 : e.g., ⌊5.6⌋ = 5 )

물론 반드시 이만큼 필요하다는 건 아님

앞에서 육각형 모양의 미술관에서는 중심에 딱 한 명 배치하는 걸로 끝났잖아

이만큼 있으면 적어도 경비원 숫자가 부족하진 않다, 는 얘기

* 틀린 부분이나 오류가 있으면 댓글 남겨주시면 감사하겠습니다