직관 — 상대의 선택에 맞춰 짝을 채운다
두 사람이 번갈아 상자에서 물건을 꺼낸다. 상대가 적게 꺼내면 나는 많이, 상대가 많이 꺼내면 나는 적게 꺼내어 두 차례의 합을 맞춘다. 끝까지 같은 짝을 만들 수 있는지가 승리를 가른다.
상자 속 물건은 남은 돌, 짝을 채우는 방법은 상대 행동에 대한 전략이다. 이 글에서는 돌과 종이만으로 규칙을 시험하고, 작은 경우의 표에서 발견한 규칙이 왜 끝까지 성립하는지 설명한다. 마지막에는 실제 수학 게임 하나를 같은 방법으로 분석하고, 규칙을 바꾼 자기 게임의 규칙서를 쓴다.
게임 전략은 상대의 모든 행동에 대한 대응을 정해 둔 것이다
게임 전략은 자신에게 올 수 있는 상황마다 어떤 행동을 할지 정한 방법이다. 필승 전략은 정해진 시작 조건에서 상대가 허용된 어떤 행동을 하더라도 승리하도록 하는 전략이다. 몇 번 이긴 기록만으로 필승을 증명하지는 못한다.
NRICH의 실제 교육 활동 Got It은 합계 0에서 시작해 1부터 4까지 더하며 목표 23을 먼저 만드는 게임이다. 아래는 그 규칙을 그대로 옮긴 것이 아니라, 대응 수를 찾는 생각을 연습하도록 구성한 12돌 변형 게임이다. Got It 자체는 뒤의 ‘실제 게임 Got It’ 절에서 같은 방법으로 분석한다.
| 규칙 항목 | 이 활동의 약속 |
|---|---|
| 준비 | 돌 12개, 두 참가자, 차례 기록표 |
| 시작 | 갑이 먼저, 을이 다음 차례 |
| 한 차례 | 남은 돌 안에서 1개·2개·3개 중 하나를 가져감 |
| 종료·승리 | 마지막 돌을 가져간 사람이 승리 |
| 금지 | 건너뛰기, 남은 수보다 많이 가져가기, 중간 규칙 변경 |
승패표는 작은 경우부터 거꾸로 채운다
승패표는 남은 돌의 수마다 ‘지금 차례인 사람’이 이기는지 지는지를 적은 표다. 큰 수의 판정은 한 차례 뒤에 남는 작은 수의 판정으로 정해지므로, 0개부터 거꾸로 채운다.
승리 상태는 지금 차례인 사람이 올바르게 두면 상대가 어떻게 하든 이기는 상태, 패배 상태는 상대가 올바르게 두면 무엇을 해도 지는 상태다. 남은 돌이 0개인 종료 상태는 마지막 돌을 이미 상대가 가져갔으므로 패배로 표시한다. 1·2·3개이면 전부 가져가 이기고, 4개이면 1·2·3개 중 무엇을 가져가도 상대에게 1·2·3개가 남는다.
| 남은 돌 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 올바르게 대응한 상대에 대한 판정 | 패 | 승 | 승 | 승 | 패 | 승 | 승 | 승 | 패 |
| 이기는 첫 행동의 예 | — | 1 | 2 | 3 | 없음 | 1 | 2 | 3 | 없음 |
판정 규칙은 두 줄이다. 상대의 패배 상태로 가는 합법적 행동이 하나라도 있으면 승리 상태다. 모든 합법적 행동이 상대의 승리 상태로 가면 패배 상태다.
figures/state_graph.py그림 1에서 5·6·7은 각각 1·2·3개를 가져가 4로 가는 파란 화살표가 있다. 4와 8에서 나가는 회색 화살표 셋은 모두 칠하지 않은 점, 곧 상대의 승리 상태에 닿는다. 작은 입력의 답으로 큰 입력의 답을 만드는 이 방법은 재귀적 알고리즘과 같은 생각이다.
이 게임은 비김 없이 반드시 끝난다. 한 차례에 돌이 1개 이상 줄어드므로 돌 12개 게임은 많아야 12차례 안에 끝나기 때문이다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 남은 돌의 수 | remaining stones | 0 이상의 정수 | |
| 상대가 가져간 수 | opponent's take | 허용된 수 중 하나 | |
| 대응하여 가져갈 수 | response | 두 차례 합을 4로 만드는 수 | |
| 최대 허용 수 | maximum take | 한 번에 1개부터 개까지 가져갈 수 있다 | |
| 몫과 나머지 | quotient, remainder | 을 로 나눈 몫과 나머지 |
12돌 게임에서 후공은 왜 반드시 이길까?
후공은 상대가 개를 가져가면 개를 가져가 두 차례의 합을 4로 만든다. 그러면 남은 돌이 12, 8, 4, 0으로 줄어 마지막 돌을 후공이 가져간다. 일 때 대응은 차례로 3·2·1개여서 모두 허용된다.
남은 수가 양의 4의 배수 일 때 상대가 개를 가져간 뒤에는 개가 있다. 이므로 대응할 돌도 충분하다. 두 차례 뒤에는 개가 남는다. 매번 4개씩 줄어 마지막 4개에서도 후공이 대응하며 끝내므로, 이 주장은 특정 대국 한 번에만 의존하지 않는다.
그림 2는 가능한 세 대응과 한 모의 대국을 보여 준다. 아래 기록의 갑은 2·1·3개를 선택했고, 을은 2·3·1개로 대응했다. 다른 갑의 선택도 식 (1)의 같은 이유로 처리된다.
figures/response_pairs.py| 차례 | 참가자 | 가져간 수 | 남은 수 |
|---|---|---|---|
| 시작 | — | — | 12 |
| 1 | 갑 | 2 | 10 |
| 2 | 을 | 2 | 8 |
| 3 | 갑 | 1 | 7 |
| 4 | 을 | 3 | 4 |
| 5 | 갑 | 3 | 1 |
| 6 | 을 | 1 | 0, 을 승리 |
돌 가져가기 게임은 먼저 시작하면 유리한가요?
돌 가져가기 게임에서 선공이 유리한지는 시작 수와 규칙에 따라 다르다. 1~3개씩 가져가는 12돌 게임은 후공이 필승 전략을 갖지만, 13개에서 시작하면 선공이 1개를 가져가 12개를 넘긴 뒤 같은 대응을 맡는다. 선공이라는 사실만으로 승패를 정하지 않는다.
허용 수가 1부터 m까지면 패배 상태는 m+1의 배수다
한 번에 1개부터 개까지 가져가고 마지막 돌을 가져가면 이기는 게임에서는, 남은 돌이 의 배수일 때 지금 차례인 사람이 진다. 상대가 개를 가져가면 개로 대응해 두 차례 합을 로 맞출 수 있기 때문이다. 12돌 게임은 인 경우다.
남은 돌 을 로 나누어 몫 와 나머지 로 쓴다.
이면 패배 상태다. 이면 먼저 개를 가져가 상대에게 의 배수를 넘기면 이긴다. 예를 들어 돌 22개·1~3개 게임은 이므로 선공이 2개를 가져가면 된다. 대응 수 는 1 이상 이하여서 늘 허용된다.
figures/rule_strips.py그림 3의 위 세 줄에서 칠한 칸의 간격은 과 같다. 두 차례씩 묶어 를 하나씩 줄이는 이 논증을 모든 자연수에 대해 엄밀하게 쓰면 수학적 귀납법이 된다. 단, 이 일반식은 1부터 까지가 빠짐없이 허용될 때의 결론이다.
실제 게임 Got It은 돌 가져가기와 같은 구조다
NRICH의 Got It은 목표 23, 한 번에 1~4를 더하는 게임이다. 합계가 일 때 목표까지 남은 양 를 ‘남은 돌’로 보면, 더하기는 돌 가져가기와 같고 목표를 만드는 사람은 마지막 돌을 가져가는 사람이다. 따라서 인 식 (2)를 그대로 쓴다.
이므로 이다. 선공은 처음에 3을 더해 남은 양을 20으로 만들고, 이후 상대가 를 더하면 를 더한다. 그림 4처럼 선공이 만드는 합계는 3, 8, 13, 18, 23이다.
figures/got_it_line.py실제 게임의 규칙을 이미 분석한 게임의 꼴로 바꾸어 보는 것이 게임 속 수학을 조사하는 한 방법이다. NRICH 원문도 목표나 더하는 수의 범위를 바꾸어 전략을 다시 시험해 보라고 제안한다. 목표를 바꾸면 이 바뀌어 선공과 후공 중 유리한 쪽도 바뀐다.
님 게임과 돌 가져가기 게임은 같은 게임인가요?
아니다. 님(Nim)은 여러 무더기 중 하나를 골라 그 무더기에서 1개 이상 원하는 만큼 가져가는 게임이고, 이 글의 게임은 한 무더기에서 1~3개처럼 가져갈 수를 제한한다. NRICH는 Got It을 님의 한 변형으로 소개하지만, 여러 무더기 님의 필승 전략은 진법의 이진수 계산이 필요해 이 글의 범위 밖이다.
마지막 돌의 승패를 바꾸면 작은 표부터 다시 만든다
마지막 돌을 가져가면 지는 게임에서는 1개가 남은 사람이 진다. 2·3·4개에서는 각각 1·2·3개를 가져가 상대에게 1개를 남기면 이긴다. 앞의 ‘4개는 패배 상태’ 결론이 바뀐다.
| 남은 돌 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 마지막 돌을 가져가면 패배 | 패 | 승 | 승 | 승 | 패 |
5개에서는 상대에게 4·3·2개 중 하나를 넘길 수밖에 없다. 이 표에는 돌이 0개인 상태에서 새 차례를 시작하는 판정을 넣지 않았다. 마지막을 가져가는 즉시 승패가 결정된다는 새 규칙을 적용한 것이다.
허용 수가 1부터 까지면 이 규칙의 패배 상태는 로 나눈 나머지가 1인 수다.
이유는 식 (2)와 같다. 상대에게 개를 넘기면, 상대가 개를 가져갈 때마다 개로 대응해 마지막에 1개를 상대에게 남긴다. 그림 3의 맨 아래 줄에서 1·5·9가 칠해진 이유다.
게임을 세 번 이기면 필승 전략을 찾은 건가요?
아니다. 세 번의 승리 기록만으로는 상대의 모든 가능한 선택을 확인하지 못할 수 있다. 12돌 게임의 증명은 상대가 1·2·3개 중 무엇을 가져가도 합법적인 대응이 있고 같은 조건이 이어진다는 데 있다. 기록은 전략을 발견하고 반례를 찾는 자료로 사용한다.
좋은 게임 규칙은 어떤 조건을 갖춰야 할까?
규칙서는 누구나 같은 방식으로 실행할 수 있어야 한다. 그래서 자기 게임을 만들 때 다음 네 가지를 확인한다.
- 완결성 — 모든 상태에서 할 수 있는 행동과 금지 행동이 정해져 있다.
- 종료성 — 반드시 끝난다. 돌 게임은 한 차례에 1개 이상 줄어든다.
- 공정성 — 선공을 정하는 방법이 있다. 전략을 아는 두 사람이면 12돌 게임은 시작 전에 후공의 승리가 정해진다.
- 전략의 여지 — 참가자의 선택이 결과를 바꿀 수 있다.
넷째 조건이 깨지는 예가 ‘돌 6개, 한 번에 1개나 3개, 마지막을 가져가면 승리’다. 1과 3은 모두 홀수라 한 차례마다 남은 돌의 홀짝이 바뀐다. 짝수 6에서 시작하면 선공은 늘 짝수를, 후공은 늘 홀수를 받는다. 0은 짝수이므로 두 사람이 무엇을 골라도 후공이 마지막 돌을 가져간다.
완성 산출물의 예는 위의 12돌 규칙서·승패표·모의 대국 기록·식 (1)의 이유다. 여기에 변형 규칙서 한 장을 더한다. 예를 들어 ‘돌 9개, 한 번에 1개나 2개, 마지막을 가져가면 승리’로 바꾸면 이므로 후공이 합 3 대응으로 9→6→3→0을 만든다.
직접 활동할 때는 한 사람이 규칙을 설명하고 다른 사람은 전략을 깨는 행동을 찾는다. 역할을 바꾸어 기록한 뒤, 처음 규칙서에 남은 돌이 부족할 때의 처리나 종료 조건이 빠졌는지 확인한다. 실제로 대국하지 않았다면 기록을 ‘모의’라고 쓰고, 어떤 조건을 바꾸자 전략이 왜 달라졌는지를 마지막 문장으로 남긴다. 규칙을 결과 전에 정하는 원칙은 투표 방식 비교의 규칙서와 같다.
게임 전략과 규칙 만들기에서는 승패표를 작은 수부터 거꾸로 채워 패배 상태를 찾는다. 1~m개씩 가져가고 마지막을 가져가면 이기는 게임은 m+1의 배수가 패배 상태다.
게임 전략과 규칙 만들기의 흔한 오해
- 4를 만드는 대응이면 어느 규칙에서도 된다. — 1·2개만 허용하면 상대의 1개에 대응하는 3개는 금지된다. 그 규칙은 이므로 식 (2)에 따라 합을 3으로 맞춘다.
- 불리한 상태에서는 실제로 누구에게나 진다. — ‘패배 상태’는 상대가 올바른 전략을 쓸 때의 판정이다. 4개에서 선공이 1개를 가져간 뒤 상대가 실수로 1개만 가져가면 선공이 남은 2개를 가져가 이길 수 있다.
직접 해보기
- 마지막을 가져가면 이기는 17돌·1~3개 게임에서 선공의 첫 행동과 그 뒤 전략을 설명하자.
- 마지막을 가져가면 이기는 10돌·1~2개 게임에서 선공은 어떻게 시작해야 할까? 대응이 허용되는지도 확인하자.
- 마지막을 가져가면 지는 7돌·1~3개 게임에서 5개를 남기는 첫 행동을 찾고, 그 뒤 상대의 세 선택에 각각 대응하자.
- ‘돌 12개, 한 번에 1개나 4개, 마지막을 가져가면 승리’ 규칙의 승패표를 0부터 12까지 만들자. 12가 5의 배수가 아닌데도 누가 이기는지, 그 사람의 전략은 무엇인지 설명하자.
- Got It의 목표를 30, 더하는 수를 1~5로 바꾸었다. 선공과 후공 중 누가 필승 전략을 갖는지와 그 사람이 만들 합계를 적자.
답
- 이므로 1개를 가져가 16개를 넘긴다. 이후 상대가 개를 가져가면 개를 가져가 12·8·4·0개를 차례로 남긴다. 각 대응은 1·2·3개이고 돌도 충분하다.
- 이므로 1개를 가져가 9개를 넘긴다. 상대가 1개이면 2개, 2개이면 1개로 대응해 두 차례마다 3개를 줄인다. 9→6→3→0이 되어 선공이 마지막을 가져간다.
- 이고 식 (3)의 패배 상태 5를 넘기려면 2개를 가져간다. 상대가 1·2·3개를 가져가면 남은 수는 4·3·2개다. 각각 3·2·1개를 가져가 상대에게 1개만 남기면 상대가 마지막을 가져가 패배한다.
- 0부터 차례로 패·승·패·승·승·패·승·패·승·승·패·승·패다. 패배 상태는 0, 2, 5, 7, 10, 12로 5로 나눈 나머지가 0 또는 2다. 12가 패배 상태이므로 후공이 이긴다. 후공은 상대가 1개를 가져가면 4개, 4개를 가져가면 1개를 가져가 12→7→2로 나머지 2를 유지한다. 2개에서는 상대가 1개만 가져갈 수 있어 후공이 남은 1개를 가져간다. 허용 수가 1부터 까지 이어지지 않으면 식 (2)를 그대로 쓰지 말고 승패표부터 만든다.
- 로 나머지가 0이므로 후공이 필승 전략을 갖는다. 선공이 를 더할 때마다 후공은 를 더해 합계를 6, 12, 18, 24, 30으로 맞춘다.
더 읽기
- 교육부, 2022 개정 수학과 교육과정 — 교육부, 2022. 별책 8 12수문02-02. 게임 속 수학적 원리를 탐구하고 게임을 만드는 활동 범위다.
- University of Cambridge NRICH, Got It — NRICH. 실제 목표 23·증가량 1~4의 규칙, 님의 한 변형이라는 소개, 목표와 범위를 바꾸어 보라는 전략 질문을 읽었다. 본문의 12돌 게임과 새 연습은 규칙을 바꾸어 직접 구성했다.
영상 노트
- 00:00 돌 12개를 먼저 가져가면 유리한지 질문한다.
- 00:40 규칙서와 0~8개 승패표를 만들고 그림 1의 상태 그래프로 판정 규칙을 설명한다.
- 01:50 그림 2와 식 (1)로 모든 상대 선택의 대응을 확인한다.
- 02:50 식 (2)와 그림 3으로 1~m 규칙의 일반식을 세운다.
- 03:40 그림 4로 Got It이 같은 구조임을 보인다.
- 04:30 마지막 돌을 가져가면 지는 규칙과 식 (3)을 비교한다.
- 05:20 좋은 규칙의 네 조건, 홀짝 규칙, 새 다섯 문제를 검토한다.
지도에서의 위치
- 2026-11-17 · GME1 검수에서 식 (1)의 간격 명령 역슬래시를 복원
- 2026-11-17 · 원자료와 자체 활동을 구별하고 계산·새 연습·산출물 예시를 작성
- 2026-11-17 · 전수 검수 반영 — 거꾸로 채우는 승패표의 판정 규칙과 종료성, 허용 수 1~m의 일반식과 마지막 패배 규칙의 일반식, 실제 게임 Got It 분석, 좋은 규칙의 조건과 홀짝 규칙 예, 님과의 차이 질문, 해보기 5문항으로 보강 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림