사상 최악의 일본 입시 수학 문제

구독중인 ‘타마키의 수학’ 유튜브 채널에 올라온 한 영상. 1998년 도쿄대 후기 이과 입시 문제로 나왔던 한 수학문제를 다루고 있는데, 그 악명높은 난이도로 인해 전설이 된 문제라고.

문제는 다음과 같다. 먼저 흰 점 한 개만 있는 그래프가 주어져있다. 여기서 말하는 그래프는 각각의 점에 흑과 백 두 색 중 하나를 칠한 단순그래프를 뜻한다. 이 때, 다음과 같은 시행을 생각한다.

점 $v$ 를 택해 $v$ 와 연결된 새로운 흰 점 $w$ 를 잡고, $v$ 의 색을 흰색이면 검은색으로, 검은색이면 흰색으로 반전한다. (‘부가’ 시행)
변 $uv$ 를 택해 그 위에 새로운 흰 점 $w$ 를 잡고, $u,v$ 의 색을 모두 반전 한다. (‘삽입’ 시행)

여기서 1번 문제는 주어진 그래프들이 이 시행을 통해 얻을 수 있음을 보이는 문제인데 그냥 그 방법을 찾으면 되는 일종의 퍼즐 문제에 가깝다. 주목해야할 곳은 2번 문제로, 이 시행을 통해 흰 점으로만 이루어진 길이 $n$ 의 chain을 만들 수 있는 $n$ 의 필요충분조건을 묻는 문제이다. chain임을 유지하기 위해서는 부가 시행은 반드시 chain의 양 끝에서만 시행해야 하기 때문에, 이는 결국 일렬로 나열되어있는 흑백의 점들에 대해 (1) 양쪽 끝 중 한 곳에 흰 점을 두고 그 옆의 점의 색을 반전시키거나 (2) 삽입 시행과 같은 시행을 통해 흰 점 1개에서 흰 점 $n$ 개로 변형시킬 수 있는 $n$ 이 무엇인지를 묻는 것과 같게 된다.

시도하다보면 주어진 조건을 만족하는 것은 $n=1,3$ 일 때에 가능하고, $n$ 일 때 가능하면 $n+3$ 일 때도 가능함을 보일 수 있기 때문에 mod 3으로 $n \equiv 0, 1$ 일 때에는 $n$ -chain을 만들 수 있음을 알 수 있다. 실제로 문제의 답은 $n \equiv 0,1$ 이고, 이를 증명하기 위해서는 $n \equiv 2$ 일 때에는 불가능함을 보여야 한다. 이렇게 주어진 시행으로 무언가가 불가능함을 보이는 문제는 지금까지의 constructive한 방향이 아니라 수학적 장치를 고안해서 증명해야 하기 때문에 그 성격도 다르고, 단순한 직관을 넘어 수학적 센스를 필요로하기 때문에 고등학교 수준 시험 문제로는 꽤 어려운 편에 속할 수밖에 없다. 해당 영상에서는 이 문제가 일본 수학 올림피아드 본선(한국으로 치면 KMO) 중에서도 꽤 어려운 포지션 급의 문제라고 소개하고 있다. (후술하겠지만 이는 그럭저럭 맞는 표현임이 다른 방식으로 증명된다)

보통 이런 유형의 문제의 경우 그 해결책으로 자주 등장하는게 앞에서 주어진 시행을 적용시켜도 변하지 않는 적절한 불변량의 설정인데, 해당 영상에서는 다음과 같은 불변량을 설정하는 것이 자연스러운 것임을 설명하고 실제로도 불변량으로 잘 작용한다는 것을 보이고 있다. 먼저 검은 점의 개수를 $B$ 라 하고, $i$ 번째 검은 점과 $i+1$ 번째 검은 점 사이에 있는 흰 점의 개수를 $w_i$ 라 한다. ( $w_0$ 은 1번째 검은 점보다 왼쪽에 있는 흰 점의 개수, $w_B$ 는 $B$ 번째 검은 점보다 오른쪽에 있는 흰 점의 개수가 되며 $w_i \geq 0$ 이다) 그리고 주어져있는 chain $P$ 에 대해 $f(P) = \sum_{i=0}^{B} (-1)^i w_i + (-1)^{B+1} + 1$ 로 정의한다. 그러면 $P$ 에서 부가 시행이나 삽입 시행을 행한 후의 chain $P^{\prime}$ 에 대해, $f(P^{\prime})$ 는 mod 3으로 $f(P)$ 혹은 $1-f(P)$ 와 같음을 보일 수 있다. 즉 $f(P)$ 를 3으로 나눈 나머지가 0 혹은 1이었다면 $f(P^{\prime})$ 을 3으로 나눈 나머지 역시 0 혹은 1이 되고, 2였다면 2가 됨을 알 수 있다. 따라서 $n \equiv 2$ 이라면 1개의 흰 점이 있는 상태의 $f$ 값은 1이라 시행을 아무리 하더라도 $f$ 의 값은 mod 3으로 0 혹은 1이어야 하지만 $n$ -chain의 $f$ 값은 mod 3으로 2라서 불가능함을 알 수 있다.

앞서 이게 올림피아드 문제급임을 이야기했는데, 실은 사실상 IMO 수준의 문제 그 자체라고도 볼 수 있는게.. 영상에서는 소개되지 않았지만 이 문제와 매우 흡사한 문제가 2005년 IMO Shortlist로 나온 적이 있었다.

Source: https://www.imomath.com/imocomp/sl05_0707.pdf

이 (만약 IMO에 출제됐다면 2번/5번 급으로 출제됐을 법한) C5 문제는 다음과 같이 기술되어있다. 한 쪽은 흰 면, 다른 한 쪽은 검은 면인 동전(오셀로 말이라고 생각하면 좋음) $n$ 개가 일렬로 나열되어 있는데, 여기서 양 끝에 있지는 않은 흰 동전 하나를 택해 없애고 그 동전의 양 옆에 있는 두 동전을 각각 뒤집는 시행을 했을 때 최종적으로 2개의 동전이 남기게 할 수 있음은 $n$ 이 mod 3으로 1이 아님과 동치임을 보이라는 것.

사실 이 문제는 앞서 소개한 1998년 도쿄대 문제와 동치이다. C5 문제에서 시행을 거꾸로 진행하고 양 끝에 있는 동전을 없애면 도쿄대 문제의 configuration과 일치하고, 반대로 도쿄대 문제에서 시행을 거꾸로 진행하고 $n$ 개의 점 양 옆에 흰 점을 두어 부가 시행의 역시행이 있을 때마다 그에 해당하는 끝쪽 점의 색을 반전시키면 C5 문제의 configuration과 일치하기 때문. 따라서 $n$ 개에 대한 도쿄대 문제와 $n+2$ 개에 대한 C5 문제가 대응된다.

이 C5 문제의 경우 앞에서 잡은 불변량과 비슷하지만 더 강력한 불변량을 잡아서 증명한다. $i$ 번째 검은 동전에 대해 그보다 왼쪽에 있는 흰 동전의 개수를 $w_i$ 라 하면 $\sum (-1)^{w_i}$ 가 mod 3으로 아예 유지가 된다는 것. 그래서 원래 문제에서도 맨 왼쪽에 대해 부가 시행을 하는 것만 주의해서 이 불변량을 살짝 변경하는 식으로 해결할 수 있다.

더 덧붙여서 가장 좋아하는 C5의 풀이는 다음과 같다. Symmetry group $S_3$ 의 두 generator $x = (1,2,3)$ , $y=(1,2)$ 를 잡으면 $x^3 = y^2 = \text{id}$ , latex x^2y=yx$, $yx^2 = xy$ , $yxy = x^2$ 가 성립하기 때문에 흰 동전을 $x$ , 검은 동전을 $y$ 로 바꾸고 순서대로 그대로 곱한 값은 불변량이 된다. 검은 동전의 개수의 기우성 또한 유지되기 때문에 마지막에 2개의 동전이 남으면 그건 흰 동전 2개 혹은 검은 동전 2개여야 하므로 이 불변량의 값은 $x^2$ 혹은 $y^2 = \text{id}$ 가 되므로 $x^n$ 이 이와 같아지려면 $n \equiv 0,2$ 여야 한다는 것.