회원님이 요청이 처리되지 않았습니다.요청을 처리하는 중 문제가 발생하였습니다. 가능한 한 빨리 문제를 해결하도록 하겠습니다.
Meta © 2022 구독중인 ‘타마키의 수학’ 유튜브 채널에 올라온 한 영상. 1998년 도쿄대 후기 이과 입시 문제로 나왔던 한 수학문제를 다루고 있는데, 그 악명높은 난이도로 인해 전설이 된 문제라고.  문제는 다음과 같다. 먼저 흰 점 한 개만 있는 그래프가 주어져있다. 여기서 말하는 그래프는 각각의 점에 흑과 백 두 색 중 하나를 칠한 단순그래프를 뜻한다. 이 때, 다음과 같은 시행을 생각한다.
여기서 1번 문제는 주어진 그래프들이 이 시행을 통해 얻을 수 있음을 보이는 문제인데 그냥 그 방법을 찾으면 되는 일종의 퍼즐 문제에 가깝다. 주목해야할 곳은 2번 문제로, 이 시행을 통해 흰 점으로만 이루어진 길이 의 chain을 만들 수 있는 의 필요충분조건을 묻는 문제이다. chain임을 유지하기 위해서는 부가 시행은 반드시 chain의 양 끝에서만 시행해야 하기 때문에, 이는 결국 일렬로 나열되어있는 흑백의 점들에 대해 (1) 양쪽 끝 중 한 곳에 흰 점을 두고 그 옆의 점의 색을 반전시키거나 (2) 삽입 시행과 같은 시행을 통해 흰 점 1개에서 흰 점 개로 변형시킬 수 있는 이 무엇인지를 묻는 것과 같게 된다. 시도하다보면 주어진 조건을 만족하는 것은 일 때에 가능하고, 일 때 가능하면 일 때도 가능함을 보일 수 있기 때문에 mod 3으로 일 때에는 -chain을 만들 수 있음을 알 수 있다. 실제로 문제의 답은 이고, 이를 증명하기 위해서는 일 때에는 불가능함을 보여야 한다. 이렇게 주어진 시행으로 무언가가 불가능함을 보이는 문제는 지금까지의 constructive한 방향이 아니라 수학적 장치를 고안해서 증명해야 하기 때문에 그 성격도 다르고, 단순한 직관을 넘어 수학적 센스를 필요로하기 때문에 고등학교 수준 시험 문제로는 꽤 어려운 편에 속할 수밖에 없다. 해당 영상에서는 이 문제가 일본 수학 올림피아드 본선(한국으로 치면 KMO) 중에서도 꽤 어려운 포지션 급의 문제라고 소개하고 있다. (후술하겠지만 이는 그럭저럭 맞는 표현임이 다른 방식으로 증명된다) 보통 이런 유형의 문제의 경우 그 해결책으로 자주 등장하는게 앞에서 주어진 시행을 적용시켜도 변하지 않는 적절한 불변량의 설정인데, 해당 영상에서는 다음과 같은 불변량을 설정하는 것이 자연스러운 것임을 설명하고 실제로도 불변량으로 잘 작용한다는 것을 보이고 있다. 먼저 검은 점의 개수를 라 하고, 번째 검은 점과 번째 검은 점 사이에 있는 흰 점의 개수를 라 한다. (은 1번째 검은 점보다 왼쪽에 있는 흰 점의 개수, 는 번째 검은 점보다 오른쪽에 있는 흰 점의 개수가 되며 이다) 그리고 주어져있는 chain 에 대해 로 정의한다. 그러면 에서 부가 시행이나 삽입 시행을 행한 후의 chain 에 대해, 는 mod 3으로 혹은 와 같음을 보일 수 있다. 즉 를 3으로 나눈 나머지가 0 혹은 1이었다면 을 3으로 나눈 나머지 역시 0 혹은 1이 되고, 2였다면 2가 됨을 알 수 있다. 따라서 이라면 1개의 흰 점이 있는 상태의 값은 1이라 시행을 아무리 하더라도 의 값은 mod 3으로 0 혹은 1이어야 하지만 -chain의 값은 mod 3으로 2라서 불가능함을 알 수 있다. 앞서 이게 올림피아드 문제급임을 이야기했는데, 실은 사실상 IMO 수준의 문제 그 자체라고도 볼 수 있는게.. 영상에서는 소개되지 않았지만 이 문제와 매우 흡사한 문제가 2005년 IMO Shortlist로 나온 적이 있었다. 이 (만약 IMO에 출제됐다면 2번/5번 급으로 출제됐을 법한) C5 문제는 다음과 같이 기술되어있다. 한 쪽은 흰 면, 다른 한 쪽은 검은 면인 동전(오셀로 말이라고 생각하면 좋음) 개가 일렬로 나열되어 있는데, 여기서 양 끝에 있지는 않은 흰 동전 하나를 택해 없애고 그 동전의 양 옆에 있는 두 동전을 각각 뒤집는 시행을 했을 때 최종적으로 2개의 동전이 남기게 할 수 있음은 이 mod 3으로 1이 아님과 동치임을 보이라는 것. 사실 이 문제는 앞서 소개한 1998년 도쿄대 문제와 동치이다. C5 문제에서 시행을 거꾸로 진행하고 양 끝에 있는 동전을 없애면 도쿄대 문제의 configuration과 일치하고, 반대로 도쿄대 문제에서 시행을 거꾸로 진행하고 개의 점 양 옆에 흰 점을 두어 부가 시행의 역시행이 있을 때마다 그에 해당하는 끝쪽 점의 색을 반전시키면 C5 문제의 configuration과 일치하기 때문. 따라서 개에 대한 도쿄대 문제와 개에 대한 C5 문제가 대응된다. 이 C5 문제의 경우 앞에서 잡은 불변량과 비슷하지만 더 강력한 불변량을 잡아서 증명한다. 번째 검은 동전에 대해 그보다 왼쪽에 있는 흰 동전의 개수를 라 하면 가 mod 3으로 아예 유지가 된다는 것. 그래서 원래 문제에서도 맨 왼쪽에 대해 부가 시행을 하는 것만 주의해서 이 불변량을 살짝 변경하는 식으로 해결할 수 있다. 더 덧붙여서 가장 좋아하는 C5의 풀이는 다음과 같다. Symmetry group 의 두 generator , 를 잡으면 , latex x^2y=yx$, , 가 성립하기 때문에 흰 동전을 , 검은 동전을 로 바꾸고 순서대로 그대로 곱한 값은 불변량이 된다. 검은 동전의 개수의 기우성 또한 유지되기 때문에 마지막에 2개의 동전이 남으면 그건 흰 동전 2개 혹은 검은 동전 2개여야 하므로 이 불변량의 값은 혹은 가 되므로 이 이와 같아지려면 여야 한다는 것. 트윗 타래를 정리. (2020/04/13) |
일본 본고사 수학 pdf - ilbon bongosa suhag pdf
관련 게시물
저작권 © 2024 ihoctot Inc.
