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

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

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

  1. v를 택해 v와 연결된 새로운 흰 점 w를 잡고, v의 색을 흰색이면 검은색으로, 검은색이면 흰색으로 반전한다. (‘부가’ 시행)
  2. 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_BB번째 검은 점보다 오른쪽에 있는 흰 점의 개수가 되며 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로 나온 적이 있었다.

이 (만약 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여야 한다는 것.

트윗 타래를 정리. (2020/04/13)

답글 남기기

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

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중