2019년 도쿄공대 입시 수학 문제

2019년 도쿄공대 전기(前期) 수학시험 문제 4번이 어렵다며 화제가 되었다는 듯. 문제를 요약하자면:

n개의 평면으로 3차원 공간이 T개의 영역으로 나뉘었을 때

(1) T의 최댓값

(2) n \geq 2일 때 2번째로 큰 T의 값

(3) n \geq 3일 때 3번째로 큰 T의 값

최댓값 같은 경우는 generic position(평행한 평면 없고 평행한 교선 없으며 4개의 평면이 한 점에서 만나거나 3개의 평면이 한 직선에서 만나는 경우가 없음)에서 나온다는 사실을 이용하면 Euler characteristic을 통해 비교적 쉽게 구할 수 있다. 3차원 문제를 해결하기 전에 먼저 2차원 케이스, 즉 평면 위의 직선들로 나뉘는 영역 개수의 최대값을 구하는 문제를 보도록 한다.

2차원의 generic position, 즉 평행한 직선 없고 3개의 직선이 한 점에서 만나는 경우가 없는 경우를 생각한다. 여기서 직선들의 교점을 꼭지점으로 잡고, 두 꼭지점을 연결하는 선분이 있는 경우 그를 변으로 보고, 나뉘는 영역을 면으로 볼 수 있게 된다. 꼭지점은 두 직선을 택할 때마다 교점 1개가 나와야 해 그 개수는 v=\binom{n}{2}가 되고, 변은 n개의 모든 직선이 각각 총 n-1개의 교점을 가져 n개의 선분으로 나뉘므로 그 개수는 e=n^2가 된다. 따라서 v-e+f=1을 통해 f=(n^2+n+2)/2를 얻을 수 있다.

이와 비슷하게 3차원에서 생각하면, 꼭지점은 세 평면을 잡을 때마다 교점 1개씩 나오게 되어 그 개수는 v=\binom{n}{3}, 변은 두 평면을 잡을 때마다 나오는 교선을 먼저 잡고 그 교선 위에는 다른 n-2개의 평면과의 교점들이 있어야해 각각 총 n-1개의 선분으로 나뉘게 되므로 e=\binom{n}{2}(n-1)이다. 또한 2차원 면의 경우, n개의 각각의 평면에 대해 그 위에 나타나는 교선과 교점들을 생각하면 n-1개의 직선들로 이루어진 generic position이기 때문에 앞서 구한 바와 같이 (n^2-n+2)/2개의 영역들로 나뉘게 된다. 따라서 f=n(n^2-n+2)/2을 얻게 되므로 평면들로 나뉘게 되는 영역 개수를 r이라 하면 r-f+e-v=1에서 r=(n^3+5n+6)/6을 얻게 된다.

이 식은 사실 \binom{n}{3}+\binom{n}{2}+\binom{n}{1}+\binom{n}{0}과 같은데 우연인건 아니다. 쉽게 이야기하자면 아무것도 없는 상태(영역 개수 1개)에서 평면을 추가할 때마다 기존의 평면, 교선, 교점마다 1개씩 새 영역이 추가되기 때문에 초기 상태 1=\binom{n}{0}에다 평면개수 \binom{n}{1}, 교선개수 \binom{n}{2}, 교점개수 \binom{n}{3}을 더하면 된다. 이는 일반화도 가능해서, m차원 유클리드 공간에 n개의 hyperplane이 있을 때 영역 개수의 최댓값이 \binom{n}{m}+\cdots+\binom{n}{0}임을 얻을 수 있다. affine hyperplane arrangement에서 극초반 연습문제 정도로 나올 법한 내용…

전자의 접근법은 후속문제들을 풀 때에 곧바로 응용하기 좋다. (2)번 문제의 답은 최댓값에서 1을 뺀 (n^3+5n)/6이 된다. 이건 예만 하나 잡으면 되는데, 가장 간단하게는 앞서 잡은 generic position에서 평면 하나를 평행하게 움직이다가 다른 교점을 지나는 순간 영역 개수가 1개 줄어든다는 것을 이용하면 되지만 (3)의 설명을 용이하게 하기 위해 다른 arrangement를 잡도록 한다.

먼저 평면에서, n-1개의 직선들의 generic position을 잡고 n번째 직선은 어느 한 직선과 평행하게 잡은 상황을 생각한다. 이 경우 꼭지점은 두 개의 직선을 잡을 때 그 두 개가 평행인 두 직선인 경우 0개, 나머지의 경우 1개씩 나오므로 v=\binom{n}{2}-1, 변은 평행인 두 직선의 경우 n-2개의 교점을 가지므로 선분 개수가 n-1이고 나머지의 경우 n이므로 e=2(n-1)+n(n-2)=n^2-2가 된다. 따라서 f=1-v+e=(n^2+n)/2를 얻는다.

이제 3차원 케이스를 보도록 한다. 먼저 n-1개의 평면들의 generic position을 잡고, n번째 평면은 다른 어떤 평면들과도 평행하지는 않지만 어떤 교선하고는 평행하게 잡는다. 즉 세 평면 \alpha,\beta,\gamma가 있어 삼각기둥을 이룬다고 생각하면 됨. 이 때 꼭지점은 이 세 평면을 잡을 때 0개, 나머지의 경우 1개씩 나와 v=\binom{n}{3}-1, 변은 이 세 평면의 세 교선의 경우 n-2개의 선분으로 나뉘고 나머지의 경우 n-1개로 나뉘어 e=3(n-2)+\left(\binom{n}{2}-3 \right) (n-1), 면은 각각의 평면 위로 n-1개의 교선들이 나타나는데 이 세 평면의 경우 위 문단과 같은 arrangement가 등장해 (n^2-n)/2개의 영역으로 나뉘고 나머지의 경우는 generic position이 나타나 (n^2-n+2)/2개로 나뉘므로 f=3(n^2-n)/2 + (n-3)(n^2-n+2)/2를 얻는다. 이를 통해 r=(n^3+5n)/6이 나오는 것을 확인할 수 있다. (단 n=2는 따로 처리해야하는데, 그냥 두 평면을 평행하게 잡으면 r=3이 되고 이 역시 위 식으로 같이 표현할 수 있다)

그러면 (3)도 이 결과와 앞서 설명한 평행이동 논의를 적용해 바로 얻을 수 있다. n개의 평면이 위와 같은 arrangement를 이루고 있을 때 \alpha,\beta,\gamma가 아닌 제4의 평면을 평행이동시켜 어떤 교점을 지나는 순간을 잡으면 (n^3+5n-6)/6이 되는 것. n=3인 경우는 세 평면이 한 직선에서 만나도록 잡아 6개의 영역으로 나누면 역시 이 식으로 표현 가능하다. 하지만 n=4일 때엔 위 방식을 적용할 수 없는데, \alpha,\beta,\gamma만 잡은 상황에서 4번째 평면을 평행이동시킨다고 할 때 이 3개의 평면은 교점을 이루지 않아 교점을 지나는 순간을 잡을 수 없는 것. 그래서 n=4일 때엔 따로 생각해야 하는데, 위 식대로라면 13이어야 하지만 케이스 나눠서 따져보면 13개가 나올 수 없어 답은 12가 됨.

물론 위의 논의들은 모두 최댓값이 generic position에서 나온다는 것을 이용한 것이라 실제 시험에서 푼다면 그 점도 따로 입증해야한다. 상한임을 보이는건 위 영상이나 다른 곳에 나온 풀이들처럼 귀납적으로 부등식 세워서 푸는게 자연스러울 듯. 해당 시험의 다른 문제들도 이 링크를 통해 볼 수 있으며, 맨 처음 인용한 영상을 올린 채널에서 (2)번 문제의 풀이도 올렸으니 다른 풀이가 궁금하다면 체크해보는 것도.

트윗 타래를 정리. (2019/03/11)

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중