| [ QuizWit ] in KIDS 글 쓴 이(By): pomp (위풍당당) 날 짜 (Date): 1997년06월27일(금) 03시36분09초 KDT 제 목(Title): [소개] "새싹"을 아세요? 두 사람이 종이와 연필만 있으면 할 수 있는 간단한 게임인 ``새싹(sprout)''을 소개합니다. 1960년대 후반 쯤, 영국 캠브리지 대학에서 크게 유행했던, 아주 오래된 게임이지만, 우리에겐 거의 알려져 있지 않습니다. 게임 방법을 설명하면, 먼저 종이에 몇 개의 점을 찍습니다. 두 사람이 번갈아 가면서 할 일은, 종이 위의 두 점을 잇는 곡선을 그리고, 그 곡선 위에 새로운 점을 하나 찍는 겁니다. 새싹이 자라나는 겁니다.(Sprout sprouts!) 물론, 조건이 있습니다. 두 점을 잇는 곡선은 아무렇게나 그려도 되지만, 절대로 자기 자신이나, 이미 그려져 있는 곡선과 만나선 안 되고, 기존의 점을 지나도 안 됩니다. 참, 그리고 한 점에서 나간 곡선이 다시 그 점으로 들어 가도 됩니다. 이 경우는 한 점에서 나가고 다시 그 점으로 들어 왔지만, 역시 두 점을 이은 것으로 생각합니다. 그리고, 중요한 것은, 어떤 점에서도 기껏해야 세 개의 선만이 뻗어 나갈 수 있다는 점입니다. 아래는 세 개의 점으로 시작한 예입니다. (그림을 그릴 수가 없으니 별 짓을 다 하는군요... ^^;) O O O-------O O---O---O O---O---O | --> --> --> / / O O O \_____O | v _____O_ _______ / \ / \ X---X---O | O---O---O | O---O---O O---O---O | | | | | | | | | | | | / O |<-- | / O | <-- / O <-- / | O | | | O | | O | O | \_____O | | \_____O | \_____O \_____O \_______/ \_______/ 왼쪽 아래 그림에서, X로 나타낸 두 점은 세 개의 선이 뻗어 나가 있으므로, 더 이상 이 점에서 나가는 곡선을 그릴 수 없습니다. 이제 ``새싹''의 승부를 정하는 방법을 설명합니다. 표준적인 경우(normal type)는, 계속 곡선을 그리다가 더 이상 그릴 수 없게 되었을 때, 마지막으로 곡선을 그린 사람이 이기는 것입니다. 반대로, 더 이상 곡선을 그릴 수 없게 된 사람이 이기는 경우(misere type)가 있습니다. normal type으로 할지 misere type으로 할지를 결정한 다음, 게임을 시작하면 된다 이겁니다. 몇 가지 문제를 생각할 수 있을 겁니다. 첫째, 과연 이 게임이 유한 번만에 끝날 것인가? 둘째, 선수 필승법이나 후수 필승법이 존재할 것인가? 이 게임을 만든 두 사람 가운데 하나인, 존 콘웨이(John Conway)는 간단한 방법으로, n 개의 점이 주어질 때 기껏해야 3n-1 번이면 게임이 끝이 난다는 걸 증명했습니다. (어떻게 했을지 생각해 보세요.) 참고로, 콘웨이는 ``생명(life)''이라는 게임을 만든 사람이고, ``새싹''의 공동 발명자 가운데 다른 한 명은 마이클 패터슨(Michael Paterson)입니다. 두 번 째 문제는 아직 일반적인 증명은 없습니다. 콘웨이가, normal type이고 점이 세 개인 경우, 선수 필승, misere type이고 점이 세 개인 경우, 후수 필승 이란 걸 보였고, (normal type이고 점이 세 개인 경우에 선수가 필승이라고 해서, 이게 꼭, misere type이고 점이 세 개인 경우에 후수가 필승이라 걸 뜻하진 않습니다. normal type이냐 misere type이냐에 따라, 게임의 내용이 전혀 달라집니다.) 몰리슨(Denis P. Mollison)이, normal type이고 점이 네 개인 경우, 선수 필승, normal type이고 점이 다섯 개인 경우, 선수 필승, normal type이고 점이 여섯 개인 경우, 후수 필승 이란 걸 보였습니다. 그 밖에, misere type이고 점이 네 개인 경우, 후수 필승 이란 게 알려져 있지만, misere type이고 점이 네 개보다 많은 경우, 전혀 알려진 게 없습니다. 비록 점이 세 개인 normal type 게임이, 먼저 하는 사람이 이길 수 있다고 밝혀져 있지만, 실제로 게임을 해 보면 이게 그렇게 쉽지 않습니다. 제가 후배랑 했을 때는, 제가 먼저 했는데도 거의 전패했고, 선배랑 했을 때는, 제가 뒤에 했는데도 거의 전승했습니다. 점 네 개도 필요없습니다. 종이에 점 세 개만 표시하고 ``새싹''을 한번 시작해 보시죠! ... & circumstance |