[정보올림피아드 대비]23. 수학게임문제

수학게임 문제는 전략적인 상황에 대한 수학적인 모델로 활용이 되며 게임이론에 사용이 된다.

 

이러한 문제중 하나가 제로섬게임과 같은 문제가 있으며 이는 한 참가자가 승리하면 다른 참가자는 패배하게 되는 경우를 가르키는 수학적인 표현이다.

예를 들면 틱택토, 체스, 다양한 수.정수 게임 등이 있다.

 

수학게임 문제로는 두 사람이 경쟁적인 게임을 진행할때 먼저 시작한 사람이 승리하게 되는 수가 존재하는지를 묻는다.

 

 

결정트리)

알고리즘 문제로 풀어 나갈때 재귀적인 코드를 작성하여 게임의 결정트리, 혹은 게임 트리를 탐색하는 것이다. 만일 부분 문제가 중복되지 않는다면 모든 경우를 모두 방문해 보는 경우이다.

 

문제1)

유클리드 게임은 두명이서 하는게임이고 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, 큰 수는 음이 아닌 정수가 되어야 한다. 그런 다음 동규는 동혁이가 한것과 똑같이 큰 수를 작은 수의 배수만큼 뺀다. 이런식으로 두 플레이어는 서로 번갈아 가면서 게임을 한다. 이때, 큰 수를 0으로 만드는 사람이 게임을 승리하게 된다.(36,2 와 같은 수가 들어 왔다면 36-18*2 이므로 첫번째 사람이 큰수를 0 으로 만들 수 있는 경우이다.)

그렇다면 (34,12) 가 주어졌을때 둘이서 모두 최선을 다했을경우 누가 이기겠는가?

 

문제풀이)

다음과 같이 트리를 만들어 본다. 이렇게 그림을 그려서 모든 경우를 방문해 본다면 처음 시작하는 사람이 이기는 것을 확인 할 수 있다.

 

수학적 통찰)

위와 같은 경우 작은 수에서는 손으로 모두 계산이 가능하지만 경우의 수가 많아 지는 경우에는 트리의 갯수가 엄청 많아지는 단점이 생긴다. 예로 (11,2) 가 들어 온경우 (9,2)(7,2)(5,2)(3,2)(2,1) 과 같이 5개의 경우를 모두 생각해 주어야 한다.

이러한 부분을 어떤식으로 접근을 하면 좀더 유리할지 찾아 보는 방법으로 가지치기를 할 수 있다.

 

이러한 문제가 아니고 문제에서 다루는 대상이 수라면 약간의 수학적 통찰력을 동원하여 계산이 빨라지도록 할 수 있다.

다음과 같은 유형의 문제를 살펴 보자.

 

문제2)

동혁이와 동규는 곱셈게임을 하려고 한다. 이 게임은 정수 p에 2와 9를 포함하는 그 사이의 숫자 중 하나를 곱하면 되는 게임이다. 제일 처음에 p=1로 시작하고, 1<n<4294967295를 만족하는 n을 정해 놓는다.

게임은 항상 동혁이가 먼저 시작한다. 동혁이가 p에 2-9 숫자 중 하나를 곱한 뒤, 동혁이가 곱하고 다시 백준이가 곱하는 방식으로 서로 턴을 번갈아 가면서 게임을 한다.

이때, p>=n 에 먼저 도달하는 사람이 이기게 된다.

동혁이와 동규가 항상 완벽하게 게임을 할때 다음과 같은 수가 들어 오는 경우 이기는 사람은 누구인가?

 

n = 162

 

문제풀이)

이 문제를 단순하게 풀기 위해서는 1*2,1*3,1*4...1*9 까지의 수를 다음 사람에게 넘겨 주면 된다.

하지만 이렇게 계산을 하게 되면 계산을 해 보아야 할 숫자가 너무 많아 지는 것을 알 수 있다.

만약 숫자를 작은 수 17을 놓고 생각해 보자.

자신의 차례에 자신의 수 * 9 가 선택된 수보다 크거나 같다면 자신이 이기는 것이고~

만약 다음 차례에 넘겨주는 값 * 9 가 17을 넘지 않게 주어야 한다.

그렇다면 17일때 처음 시작하는 사람이 2를 선택해 주어야 할까? 2를 선택해 준다고 해도 그 다음 사람은 9를 선택하면서 반드시 이길 수 밖에 없다. 따라서 처음 사람은 9를 선택하든 2를 선택하든 동일한 결과값을 가질 수 밖에 없다.

숫자가 19 라고 하면 처음 시작하는 사람이 2를 선택한다고 하면 두번째 사람은 2를 선택하든 9를 선택하든 동일한 결과를 얻게 된다.

따라서 이러한 결과를 가지게 되면 자신의 차례에 2를 선택하거나 9를 선택하는 방법으로 압축을 해 볼 수가 있다.

 

이것을 그림을 그려 보면 다음과 같이 그려 볼 수가 있다.

 

이렇게 그림을 그려 보면 다음과 같은 결과를 확인 할 수 있다.

2부터 9 까지는 처음 사람이 이긴다. 

10부터 18까지는 두번째 사람이 이긴다.

19부터 162까지는 처음사람이 이긴다.(19 인 경우는 처음 사람이 2를 선택, 162인 경우는 처음사람이 9를 선택 후 두번째 사람이 어떤수를 선택해도 18 부터 162까지 만들 수 있다는 것을 알 수 있다.)

 

여기서 첫번째 사람은 9를 선택하고 두번째 사람은 2를 선택해서 자신의 수 안에 들어 온다고 하면 이기는 규칙을 찾아 낼 수 있다.

 

이렇게 하면 더 큰 수라고 해도 규칙을 찾아 해결이 가능하다.

 

님 게임)

님게임이란 수학적 전략 보드 게임이다.

몇개의 줄에 숫자나 자연수개의 돌을 두고 순서대로 돌아가면서 한 주에서 정해진 수의 숫자를 제거한다.

가져오는 숫자에는 상한이 있으며 무조건 1개는 가져와야 하며 마지막 돌을 가져오는 사람이 이기는 게임이다.

 

다음에 나오는 문제들을 풀어 보자.

 

문제1)

두 사람이 동전 놓기 게임을 한다. 큰 원판이 하나 있고, 그 위에 두 사람이 동전을 하나씩 번갈아 가며 놓는다.

이미 원판 위에 놓인 동전과는 겹치게 놓을 수 없고 원판 밖으로 동전의 일부가 나가도록 놓을 수도 없다. 더 이상 동전을 내려 놓을 수 없는 사람이 진다.

동전을 먼저 내려 놓는 첫번째 사람에게는 반드시 "이기는 전략"이 존재한다. 그것은 무엇일까?

 

문제풀이)

 

다음 그림과 같이 청색이 첫번째 사람이라고 하면 원판의 정 중앙에 돌을 놓는다.

그 후 다음 사람 노랑색 돌을 놓는 곳을 정 중앙 위치의 대각선의 같은 위치에 놓기만 하면 언젠가는 노랑색 돌이 놓을 수 없는 곳이 생긴다.

 

문제2)

동전 40개가 있다. A,B 두사람이 교대로 동전을 가져간다. 한번에 하나이상 5개 이하의 동전을 가져갈 수 있다. 마지막 동전을 가져가는 사람이 이긴다. A가 먼저 동전을 가져가기 시작한다면 A에게 이기는 전략이 있을까?

있다면 어떤 방법인지 설명하시오.

 

문제풀이)

A에게 이기는 전략이 있다.

동전이 5개 이하라고 하면 A가 이긴다.

동전이 6개라고 하면 B가 이긴다.

동전이 7개라고 하면 A가 1개만 가져오고 B에게 6개를 남겨주면 된다.

동전이 8개라고 하면 A가 2개만 가져오고 B에게 6개를 남겨주면 된다.

...

동전이 12개라고 하면 B가 이긴다. (A는 어떤 수를 가져와도 그 다음에는 B가 A에게 6개를 남겨 줄것이기 때문이다.)

 

결국은 6의 배수가 B가 이길수 있고 6의 배수가 아닌것은 A가 이길수 있는 전략이 있다는 것을 알 수 있다.

따라서 A는 처음 4개를 가져오고 6의 배수인 36개를 B에게 남겨 주면 되며 돌아 오는 수에서 6의 배수만큼을 B에게 남겨 주면 된다.

문제3)

두 개의 접시에 동전이 각각 20개, 30개가 놓여 있다. A,B 두 사람이 교대로 동전을 가져간다. 하나의 접시에서 동전을  하나 이상 원하는 만큼 가져갈 수 있다. 하지만 두 접시에서 섞어서 가져갈 수는 없다. 마지막 동전을 가져가는 사람이 이긴다. A가 먼저 가져간다면, A가 이기는 전략이 있을까? 만약 있다면 어떤 방법인지 설명하시오?

 

문제풀이)

A가 이기는 전략이 있다.

A가 먼저 두번째 접시에서 10개를 가져 가서 두 개의 접시를 동일한 갯수로 만들어 준다.

그 다음 B가 가져가는 갯수에 맞추어서 다른 접식에서 같은 갯수로 가져 가면 반드시 이길수 밖에 없다.

문제4)

두 개의 접시에 동전이 각각 22개, 40개가 놓여 있다. A,B 두 사람이 교대로 동전을 가져간다. 하나의 접시에서 동전을  하나 이상 원하는 만큼 가져갈 수 있다. 하지만 두 접시에서 가져갈때는 두개의 줄에서 동일한 갯수를 가져 갈 수 있다. 마지막 동전을 가져가는 사람이 지는게임이다. A가 먼저 가져간다면, A가 이기는 전략이 있을까? 만약 있다면 어떤 방법인지 설명하시오?

 

문제풀이)

A가 이기는 전략이 있다.

마지막에 (1,2) 를 남겨 주는 사람이 이긴다.

이렇게 하기 위해서는 (1,2),(3,5),(4.7),(6,10)(7,12)(9,15)(11,18)(12,20)(14.23)(15.25)(17,26)(18,29)(19.31)(21,34)(22,36)(24,41) 을 남겨 주는 사람이 이긴다.

여기서는 연속하는 두 순서쌍 (m,n)에서 m은 1,2,1,2,1,2 가 반복 되는 것을 알 수 있고 n-m 의 값이 1부터 증가되는 규칙을 찾을 수 있다.

(22,40) 에서 큰 수에서 4개를 가져가서 (22,36)을 넘겨 주면 된다.

 

문제5) 세개의 접시에 동전이 각각 8개,13개,20개가 놓여 있다. A,B 두사람이 교대로 동전을 가져간다. 하나의 접시에서 동전을 하나 이상 원하는 만큼 가져갈 수 있다. 하지만 두개 이상의 접시에서 섞어서 가져 갈 수는 없다. 마지막 동전을 가져가는 사람이 지는게임이다. A가 먼저 가져간다면, A가 이기는 전략이 있을까? 만약 있다면 어떤 방법인지 설명하시오?

 

문제풀이)

세개의 접시에 있는 경우를 생각하면 다음과 같다.

첫번째 사람이 이기기 위해서는 (1,1,0)일때 이긴다. 또한 (1,n,0)일때 항상 이길 수 있다.

따라서 이 수를 받는 사람이 이기기 때문에 다음과 같이 표를 그려보자.

(1,2,n)일때 자신은 (1,2,3)을 넘겨 주면 이긴다.

(1,2,3)->(1,2,2)->(0,2,2)

(1,2,3)->(1,2,1)->(1,1,1)

(1,2,3)->(1,1,3)->(1,1,1)

 

 

이러한 원리는 그 이전에 만들 수 있는 값이 없는 경우의 값을 찾아서 그것보다 하나 더 큰 수를 넘겨 주는 수를 찾아 주면 된다.

예) 첫번째 1, 두번째 4일때 세번째 5보다 작은 값을 넘겨 주는 순간 첫번째 1 부터 4 까지 지는 경우를 넘겨 받는 수가 있었기 때문에 상대방은 이 수를 넘겨 줄것이기 때문이다. 따라서 첫번째 1,두번째 4라고 하면 세번째 수는 반드시 5인 수만 넘겨 주어야 한다.

 

이렇게 이길 수 있는 경우를 표를 그려 보면 다음과 같다.

 

	1	2	3	4	5	6	7	8
1	0	3	2	5	4	7	6	9
2	3	0	1	6	7	4	5	10
3	2	1	0	7	6	5	4	11
4	5	6	7	0	1	2	3	12
5	4	7	6	1	0	3	2	13
6	7	4	5	2	3	0	1	14
7	6	5	4	3	2	1	0	15
8	9	10	11	12	13	14	15	0

첫번째 줄(행)과 두번째 줄(열)과 세번째 줄에 이길 수 있는 값

이렇게 테이블을 그리다 보면 복잡해 보이는데~ 이러한 원리의 표를 1901년 Charles L Bouton 교수가 다음과 같은 2진법 풀이로 해결할 수 있다.

위의 표의 값을 이진수로 나타내 보자

 

	0001	0010	0011	0100	0101	0110	0111	1000
0001	0000	0011	0010	0101	0100	0111	0110	1001
0010	0011	0000	0001	0110	0111	0100	0101	1010
0011	0010	0001	0000	0111	0110	0101	0100	1011
0100	0101	0110	0111	0000	0001	0010	0011	1100
0101	0100	0111	0110	0001	0000	0011	0010	1101
0110	0111	0100	0101	0010	0011	0000	0001	1110
0111	0110	0101	0100	0011	0010	0001	0000	1111
1000	1001	1010	1011	1100	1101	1110	1111	0000

 

이렇게 테이블로 정렬해 보니 첫번째 a 두번째 b 라고 하면 c = a^b 의 값임을 확인할 수 있다.

이러한 성질은 다음과 같은 규칙을 갖는 것을 확인 할 수 있다.

세개의 접시 동전의 개수를 2의 거듭제곱의 합으로 나타냈을때 2의 거듭제곱 들이 쌍으로 존재한다는 것을 알수 있다.

예를 들어 (3,5,6)을 살펴 보면

3=1+2, 5= 1+4, 6 = 2+4 가 된다

여기서 1이 두번 2가 두번 4가 두번 나타나는 것을 확인 할 수 있다.

이 성질은 같은 규칙으로 게임할 경우 4줄 이상에서도 성립하므로 일반적인 님게임에서 적용이 가능하다.

 

따라서 8개 13개 20개가 놓여 있다고 하면

c = 8 ^ 13 = 1000(2) ^ 1101(2) = 0101(2) = 5 임을 알수 있으므로

처음 시작하는 사람은 다음 사람에게 (8,13,5) 의 갯수를 넘겨 주면 된다.

 

문제6) 다섯개의 접시에 동전이 각각 3개,7개,8개,11개,12개 가 놓여 있다. A,B 두사람이 교대로 동전을 가져간다. 하나의 접시에서 동전을 하나 이상 원하는 만큼 가져갈 수 있다. 하지만 두개 이상의 접시에서 섞어서 가져 갈 수는 없다. 마지막 동전을 가져가는 사람이 지는게임이다. A가 먼저 가져간다면, A가 이기는 전략이 있을까? 만약 있다면 어떤 방법인지 설명하시오?

 

문제풀이)

위에서 설명한 방법과 동일하게

e = a^b^c^d 이므로 가장 많은 갯수를 줄이는 방법을 살펴 보면

e = 3^7^8^11 = 0011(2) ^ 0111(2) ^ 1000(2) ^ 1011(2) = 0111(2) = 7 이 되는것을 확인 할 수 있다.

따라서 다섯번째 접시에서 5개를 가져가면 된다.

 

※ 이와 같이 님게임의 기본적인 규칙은 균형상태와 불균형 상태를 관찰하여 균형상태를 만들어 주는 것이 핵심입니다.

 

 

님게임을 해 보자.

 

www.transience.com.au/pearl3.html

pearls before swine 3

 

정보올림피아드 기출유형)

 

docs.google.com/forms/d/e/1FAIpQLSdNaWzu86-HdK6jUSkZxt12Sjs1VvZRlShQJPN8bTdraFbozg/viewform

25-1. 수학게임문제