단짝 친구인 지상이와 병요는 평소 주말마다 함께 등산을 합니다. 여느 때와 마찬가지로 쉬는 날을 이용해 산을 찾은 지상이와 병요가 열심히
산을 오르고 있었습니다. 한참을 올라가던 두 사람은 시원한 나무 그늘 아래서 잠시 쉬었다 가기로 하였습니다. 그런데 목이 말랐던 지상이가 물을
마시려고 배낭을 아무리 뒤져 보아도 물병이 보이지 않는 것이 아닙니까? 옆에 있던 병요에게 물어보았더니 이미 한 시간
전에 텅 빈 물병을 보여 주며 역시 목이 마른 표정을 하고 있었습니다. 두 사람은 5분 전에 지나온 곳에 물을 받을 수 있는 곳이 있었다는 것을
알고 있었지만 지쳐 있었기 때문에 서로 눈치만 보고 있었습니다.
물이 너무 마시고 싶었지만 지나온 곳을 되돌아가기는 싫었던 지상이는 한 가지 꾀를 생각해내고는 병요에게
다음과 같은 제안을 하였습니다. “서로 아카시아 잎을 주워 와서 잎을 따는 거야. 한 번에 한쪽 줄기에서만 잎을 딸 수 있고, 한 번에 몇 개를
따더라도 상관없어. 마지막 잎사귀를 따는 사람이 이기는 걸로 하고, 진 사람이 물을 받아오는 게 어때? 먼저 시작할지 나중에 시작할지는
가위바위보를 해서 이긴 사람 마음대로 하자.” 가위바위보는 늘 지상이에게 지던 병요였지만 게임에는 어느 정도 자신이 있었기 때문에 흔쾌히
동의하였고, 각자 아카시아 줄기를 주워 왔습니다. 지상이가 가져온 줄기에는 17개, 병요가 가져온 줄기에는 11개의 잎이 달려 있었습니다.
가위바위보에서 이긴 지상이가 먼저 시작하더니 게임에서 이겼습니다. 게임에서 진 병요가 억지를 부려 똑같은 줄기를 더 주워 와서 다시 게임을
하였지만 먼저 시작한 지상이에게 내리 두 번을 지고 말았습니다. 지상이는 어떻게 계속 이길 수 있었을까요?
수련회나 엠티를 갔을 때, 여러 명이 둘러앉아 순서대로 한 번에 2개 또는 3개 이하의 수를 말하여 마지막에 목표 수를 말하는 사람이 술래가 되는 단순한 게임을 해본 기억이 한 번쯤은 있을 것입니다. 이와 비슷한 게임으로 여러 개의 구슬이나 동전 등 개수를 셀 수 있는 물건을 놓고 번갈아가며 한 번에 몇 개 이하의 개수를 가져가 마지막 한 개를 가져간 사람이 지거나 이기는 게임도 자주 하곤 합니다. 이와 같은 유형의 게임을 님(Nim) 게임이라고 합니다. 매우 오래된 기원을 가지고 있는 님(Nim) 게임은 규칙의 간단함에 비해 만만치 않은 전략적 사고를 요구하여, 수학에서의 중요한 분야일 뿐만 아니라 컴퓨터 프로그래밍을 연습하는데 훌륭한 소재로 사용되고 있습니다.
위 게임에서는 먼저 하는 사람이 무조건 이길 수 있는 방법이 있습니다. 양쪽 줄기에 남아 있는 잎의 개수가 같으면 상대방이 떼어버린 개수만큼 떼어낼 수 있으므로 항상 마지막 잎을 떼어낼 수 있습니다. 따라서 먼저 시작한 지상이가 17개짜리 줄기에서 6개의 잎을 떼어낸 다음, 병요가 떼어낸 개수만큼 반대쪽 줄기에서 떼어냈기 때문에 항상 이길 수 있었던 것입니다.
님(Nim) 게임의 기본 해결 전략은 ‘거꾸로 문제를 해결하기’입니다. 처음부터 몇 개를 가져갈까 고민을 하게 되면 상대방이 가져가는 개수에 따라 경우의 수가 너무 많아져 일일이 따지기가 쉽지 않습니다. 반면 마지막 결과부터 생각하여 반드시 이기는 개수를 차근차근 거꾸로 따져 나가면 필승의 해결 전략을 찾을 수 있습니다. 이 때 승부에 영향을 미치는 조건은 ‘전체의 개수’, ‘한 번에 가져갈 수 있는 최대 개수’, ‘마지막 한 개의 승패 조건’, ‘먼저 하느냐, 나중에 하느냐’가 있습니다.
<1> 모두 13개의 구슬이 있습니다. 성준이와 재식이가 번갈아가며 한 번에 1개, 2개 또는 3개의 구슬을 가져갑니다. 맨 마지막 구슬을 가져가는 사람이 이긴다고 할 때, 성준이가 항상 이길 수 있는 방법이 있습니까? 만일 그렇다면 처음에 몇 개의 구슬을 가져가야 합니까?
<2> 사탕이 7개씩 두 바구니에 담겨 있습니다. 두 명이 차례로 사탕을 원하는 만큼 가져올 수 있습니다. 그런데 한쪽 바구니에서만 가져와야 합니다. 사탕을 가져올 수 없게 된 사람이 진다면, 먼저 한 사람과 나중에 한 사람 중 누가 이기겠습니까?
<3> 2006개의 바둑돌이 있습니다. 병준이와 승택이가 번갈아 가면서 바둑돌을 가지고 갑니다. 한 번에 2개, 4개 또는 6개의 바둑돌을 가지고 갈 수 있고, 마지막 바둑돌을 가지고 가는 사람이 이긴다고 합니다. 병준이가 먼저 시작한다면 처음에 몇 개를 가지고 가야 반드시 이길 수 있습니까?
<4> 신영이와 유리가 동전 쌓기 놀이를 합니다. 서로 번갈아가며 동전을 쌓는데, 마지막 동전을 쌓는 사람이 이깁니다. 처음에 전부를 쌓을 수는 없습니다. 자기 차례에 반드시 한 개 이상의 동전을 쌓아야 하고, 바로 앞 사람이 쌓은 개수의 2배까지 쌓을 수 있습니다. 10개의 동전 쌓기 놀이를 할 때 만일 신영이가 먼저 한다면 유리한 사람은 누구입니까? 그 사람은 처음에 몇 개의 동전을 쌓아야 합니까?
경향신문
수련회나 엠티를 갔을 때, 여러 명이 둘러앉아 순서대로 한 번에 2개 또는 3개 이하의 수를 말하여 마지막에 목표 수를 말하는 사람이 술래가 되는 단순한 게임을 해본 기억이 한 번쯤은 있을 것입니다. 이와 비슷한 게임으로 여러 개의 구슬이나 동전 등 개수를 셀 수 있는 물건을 놓고 번갈아가며 한 번에 몇 개 이하의 개수를 가져가 마지막 한 개를 가져간 사람이 지거나 이기는 게임도 자주 하곤 합니다. 이와 같은 유형의 게임을 님(Nim) 게임이라고 합니다. 매우 오래된 기원을 가지고 있는 님(Nim) 게임은 규칙의 간단함에 비해 만만치 않은 전략적 사고를 요구하여, 수학에서의 중요한 분야일 뿐만 아니라 컴퓨터 프로그래밍을 연습하는데 훌륭한 소재로 사용되고 있습니다.
위 게임에서는 먼저 하는 사람이 무조건 이길 수 있는 방법이 있습니다. 양쪽 줄기에 남아 있는 잎의 개수가 같으면 상대방이 떼어버린 개수만큼 떼어낼 수 있으므로 항상 마지막 잎을 떼어낼 수 있습니다. 따라서 먼저 시작한 지상이가 17개짜리 줄기에서 6개의 잎을 떼어낸 다음, 병요가 떼어낸 개수만큼 반대쪽 줄기에서 떼어냈기 때문에 항상 이길 수 있었던 것입니다.
님(Nim) 게임의 기본 해결 전략은 ‘거꾸로 문제를 해결하기’입니다. 처음부터 몇 개를 가져갈까 고민을 하게 되면 상대방이 가져가는 개수에 따라 경우의 수가 너무 많아져 일일이 따지기가 쉽지 않습니다. 반면 마지막 결과부터 생각하여 반드시 이기는 개수를 차근차근 거꾸로 따져 나가면 필승의 해결 전략을 찾을 수 있습니다. 이 때 승부에 영향을 미치는 조건은 ‘전체의 개수’, ‘한 번에 가져갈 수 있는 최대 개수’, ‘마지막 한 개의 승패 조건’, ‘먼저 하느냐, 나중에 하느냐’가 있습니다.
<1> 모두 13개의 구슬이 있습니다. 성준이와 재식이가 번갈아가며 한 번에 1개, 2개 또는 3개의 구슬을 가져갑니다. 맨 마지막 구슬을 가져가는 사람이 이긴다고 할 때, 성준이가 항상 이길 수 있는 방법이 있습니까? 만일 그렇다면 처음에 몇 개의 구슬을 가져가야 합니까?
<2> 사탕이 7개씩 두 바구니에 담겨 있습니다. 두 명이 차례로 사탕을 원하는 만큼 가져올 수 있습니다. 그런데 한쪽 바구니에서만 가져와야 합니다. 사탕을 가져올 수 없게 된 사람이 진다면, 먼저 한 사람과 나중에 한 사람 중 누가 이기겠습니까?
<3> 2006개의 바둑돌이 있습니다. 병준이와 승택이가 번갈아 가면서 바둑돌을 가지고 갑니다. 한 번에 2개, 4개 또는 6개의 바둑돌을 가지고 갈 수 있고, 마지막 바둑돌을 가지고 가는 사람이 이긴다고 합니다. 병준이가 먼저 시작한다면 처음에 몇 개를 가지고 가야 반드시 이길 수 있습니까?
<4> 신영이와 유리가 동전 쌓기 놀이를 합니다. 서로 번갈아가며 동전을 쌓는데, 마지막 동전을 쌓는 사람이 이깁니다. 처음에 전부를 쌓을 수는 없습니다. 자기 차례에 반드시 한 개 이상의 동전을 쌓아야 하고, 바로 앞 사람이 쌓은 개수의 2배까지 쌓을 수 있습니다. 10개의 동전 쌓기 놀이를 할 때 만일 신영이가 먼저 한다면 유리한 사람은 누구입니까? 그 사람은 처음에 몇 개의 동전을 쌓아야 합니까?
경향신문
댓글 없음:
댓글 쓰기