Pearls (게임 / 해설)

Trivial Solution이라는 게임이 있나 봅니다. 아래 링크를 두들겨 보세요.

그리고 웬간하면 필승법을 알아내 보십사 합니다.

Pearls before Swine 

 

게임 룰은 간단합니다.

1. 자기가 먼저 할지, 상대에게 먼저 하게 할지 정할 수 있습니다.

2. 자기 차례가 되면, 어느 한 줄만 선택하여 그 줄에 남은 구슬 몇 개든 가져올 수 있습니다.

3. 다만 자기 차례에서 최소한 구슬 한 개는 가져와야 합니다.

4. 구슬을 가져 오면 상대에게 차례가 넘어가는데

5. 마지막으로 구슬을 가져가는 사람이 집니다. (마지막 1개를 상대에게 넘겨야 이기는 게임)

쉬운 두 줄부터 시작해서 점점 갈수록 구슬 수가 늘어나고
급기야 7줄에 한 줄 29개 까정 등장하는군요.
레벨27 언저리가 되면 한계가 옵니다. 비슷한 패턴이 반복 출제된다는 뜻.
그것과 씨름하며 하염없이 시행착오를 거친 끝에 제가 나름대로 찾은 해법을 올립니다.

***

[1줄]
게임의 룰에 따라, 구슬 수가 1이면 pass, 1보다 크면 1로 만들어 이김. (상태1)

[2줄]
(1,a)이면 a를 모두 가져와 이김. 1만 남김. (a>0) (상태2)
n<m일 때, (n,m)의 형태라면
(n,n)을 만들어 상대에게 넘기면 이김. 알고 보니 이 상태가 이 게임 원리의 핵심임. (상태3)

즉, (n,n)이 된 상태에서 상대가 응수하는 방법에 따라
1. (a,a)상태를 유지하거나, (a<n, 상대가 (n-a)를 줄인 만큼 다른 줄의 구슬을 줄임)
2. (0,a)의 상태가 되면 상태1이므로 이기고
3. (1,a)의 상태가 되면 상태2이므로 이김. 즉 어떤 경우에도 이기게 됨.

예를 들어 (5,8)이라면 (5,5)로 만듬.
그걸 상대가 (3,5)로 만들면 (3,3)으로 만듬.
그걸 상대가 (3,2)로 만들면 (2,2)로 만듬.
그걸 상대가 (1,2)로 만들면 이 때 주의! (1,1)을 만들면 짐. (1,0)으로 만들어야 함.

(2,2)가 기본형이므로 더 자세히 씀. 상대가 (2,2)를
(1,2)로 만들면 (1,0)으로 응수,
(0,2)로 만들면 (0,1)로 응수,
(2,1)로 만들면 (0,1)으로 응수,
(2,0)로 만들면 (1,0)으로 응수함. 즉, 상대가 어떻게 건드리든 이쪽은 1로 만들 수 있음.

[3줄]
(1,1,1)로 만들어 상대에게 차례를 넘기면 이김. (상태4)
참고로 (1,1)=0과 같음. 있으나 마나, 본질적으로(1,1,1)=1임.

그렇다면,
(1,1,2)는 어떨까? 상대가 (1,1,1)로 만들어 내가 짐.
(1,2,2)는 어떨까? 상대가 (0,2,2)로 만들어 지게 됨. 세 줄에서 (n,m,m)을 만들면 짐.

(1,2,3)은? 필승임. 이 게임의 알짜 기본형.

(1,2,3)으로 만들면 상대의 응수는 아래 6가지 뿐인데,
(0,2,3)은 (0,2,2)로 만들고
(1,1,3)은 (1,1,1)로
(1,0,3)은 (1,0,0)으로
(1,2,2)는 (0,2,2)로
(1,2,1)은 (1,1,1)로
(1,2,0)은 (1,0,0)으로 만듦으로써 어떤 경우이든 상대를 이길 수 있음.

그럼 (1,2,4)는? (1,2,3)으로 상대가 만들므로 짐. (1,2,n)은 안됨.
그럼 (1,3,4)는? (1,3,2)=(1,2,3)으로 상대가 만들므로 짐. (1,3,n)은 안됨.
즉, (1,2,3)에서 써먹은 2, 또는 3을 사용해서 (1,a,n)형태를 만들면 지게 됨.
그럼 (1,4,5)는? 필승임. (1,4,5)는 (1,2,3)과 본질적으로 같음. (추론과정은 위와 비슷하므로 생략함)
이런 식으로 진행하여 (1,1,1), (1,2,3), (1,4,5), (1,6,7), (1,8,9), (1,10,11)...의 필승형을 얻게 됨.

(2,a,n)형은 어떨까?
(2,2,n), (2,3,n)은 안됨. (2,4,5)역시 안됨. (상대가 (1,4,5)로 만듬)
따라서 (2,4,6)이 기본형이 됨.
이런 식으로 진행하여 (2,4,6), (2,5,7), (2,8,10), (2,9,11), (2,12,14), (2,13,15)...의 필승형을 얻게 됨.

(3,a,n)형은 (3,4,7)이 기본형이며 (3,4,7), (3,5,6), (3,8,11), (3,9,10)...을 얻음.

이런 식으로 노가다를 하염없이 하면 아래의 표를 얻을 수 있음.
(엑셀 따위로 (a,b,c)로 채워나갈 때, 가로는 a=1,2,3..., 세로는 b=1,2,4...식으로 표를 만들면 편리, 검산 작업에 무지 도움됨.)

(1,1,1), (1,2,3), (1,4,5), (1,6,7), (1,8,9), (1,10,11), (1,12,13), (1,14,15), (1,16,17), (1,18,19), (1,20,21), (1,22,23)...
(2,4,6), (2,5,7), (2,8,10), (2,9,11), (2,12,14), (2,13,15), (2,16,18), (2,17,19), (2,20,22), (2,21,23)...
(3,4,7), (3,5,6), (3,8,11), (3,9,10), (3,12,15), (3,13,14), (3,16,19), (3,17,18), (3,20,23), (3,21,22)...
(4,8,12), (4,9,13), (4,10,14), (4,11,15), (4,16,20), (4,17,21), (4,18,22), (4,19,23)...
(5,8,13), (5,9,12), (5,10,15), (5,11,14), (5,16,21), (5,17,20), (5,18,23), 5,19,22)...
(6,8,14), (6,9,15), (6,10,12), (6,11,13), (6,16,22), (6,17,23), (6,18,20), (6,19,21)...
(7,8,15), (7,9,14), (7,10,13), (7,11,12), (7,16,23), (7,17,22), (7,18,21), (7,19,20)...
(8,16,24), (8,17,25), (8,18,26), (8,19,27), (8,20,28), (8,21,29)...
(9,16,25), (9,17,24), (9,18,27), (9,19,26), (9,20,29), (9,21,28)...
(10,16,26), (10,17,27), (10,18,24), (10,19,25), (10,20,30), (10,21,31)...

들여다 보니 불규칙하지만 그래도 뭔가 규칙이 있을 듯 함.
이리저리 시행착오를 거듭하며 따지다가 아래의 사실에 주목할 수 있음.

(1,a,b)에서 (1,a+2,b+2)가 나옴. 즉 (1,2,3)→(1,4,5)→(1,6,7)...임.
(2,a,b)에서 (2,a+4,b+4)가 나옴. 즉 (2,4,6)→(2,8,10)→(2,12,14)..., (2,5,7)→(2,9,11)→(2,13,15)...임.
(3,a,b)에서 (3,a+4,b+4)가 나옴. 즉 (3,4,7)→(3,8,11)→(3,12,15)..., (3,5,6)→(3,9,10)→(3,13,14)...임.
(4,a,b)에서 (4,a+8,b+8)가 나옴. 즉 (4,8,12)→(4,16,20), (4,9,13)→(4,17,21)...임.

이걸 확장해 나가면, (a,b,c)의 필승형으로부터 (a,b+k,c+k)를 덩달아 얻음을 알 수 있음.
단, 이 때 k>a, k=2,4,8,16,32,64... 즉 k는 a보다 큰, 2의 거듭제곱 수임.
예를 들어 (6,10,12)→(6,10+8,12+8)=(6,18,20) 식으로 새로운 필승형을 얻어낼 수 있음.

이걸 더 확장하면 (a,b,c)→(a+k,b,c+k)도 성립함을 알 수 있음. k>b이며 k=2,4,8,16,32...
예를 들어 (1,2,3)→(1+4,2,3+4)=(5,2,7)=(2,5,7) 식으로 찾아낼 수 있음.

그렇다면 이걸 거꾸로 쓰면 (a,b,x)가 필승형이 되는 x를 찾아낼 수 있지 않을까? 를 따지게 됨.
(2,5,x)라면, 2보다 큰 k는 4임. (2,5,x)를 4로 분해하면 (2,1+4,x-4+4)=(2,1,x-4)
/x-4/ 자리에 3이 오면 (2,1,3)=(1,2,3)이 되므로 x-4=3, x=7. 즉 (2,5,7)을 완성할 수 있음.
(5,12,x)라면? (5, 4+8, x-8+8)=(5,4,x-8), x-8=1, x=9, 따라서 (5,12,9)=(5,9,12)가 답임.

이리 따지다 보면 (a,k,x)인 경우를 필연적으로 만나게 됨.
예를 들어 (5,8,13)이 그런 형태인데, (5,8,13)→(5,8-8,13-8)=(5,0,5)가 됨.
즉 본질적으로 (5,8,13)=(5,5)=0 이었던 것임. 이것은 (8,13)=5임을 뜻함.
조금 느닷없어서 일견 이해하기 어려울 수 있겠으나, 아래 4줄 설명에서 조금 더 풀어보겠음.

여하튼, 이 조견표와 설명으로 3줄 짜리 웬간한 것은 쉽게 풀 수 있음.
즉, 척 보고 필승형인지 아닌지, 필승형으로 만들려면 무엇을 건드려야 하는지 알게 됨.

[4줄]
(0,a,b,c)로 위 조견표 (a,b,c)를 만들거나 (n,n,m,m)의 형태로 만들면 이김.
근데 경우의 수가 너무 많음. 그래도 헤매면서 조견표를 만들어 보자면 아래와 같음.

(1,2,4,7), (1,2,5,6), (1,2,8,11), (1,2,9,10)...
(1,3,4,6), (1,3,5,7), (1,3,8,10), (1,3,9,11)...
(1,4,8,13), (1,4,9,12)...
(2,3,4,5), (2,3,6,7)...

뭔가 이상하다고 여겨지는 것이, 눈에 익은 형태임. 즉,

(1,2,4,7), (1,2,5,6), (1,2,8,11), (1,2,9,10)...=(3,4,7), (3,5,6), (3,8,11), (3,9,10)...
(1,3,4,6), (1,3,5,7), (1,3,8,10), (1,3,9,11)...=(2,4,6), (2,5,7), (2,8,10), (2,9,11)...
(1,4,8,13), (1,4,9,12)...=(5,8,13), (5,9,12)...
(2,3,4,5), (2,3,6,7)...=(1,4,5), (1,6,7)...

다시 말해, (1,2)=3, (1,3)=2, (1,4)=5, (2,3)=1인 셈임.

왜 그런지 따져보니,
이 게임에서 n을 정의하면, n이란

1. 건드렸을 때 0,1,..., n-1로 바꿀 수 있는 수
2. 그리고 상대가 건드려 n이상이 되었다 할지라도 내가 n으로 되돌릴 수 있는 수

이 두 가지 요건을 충족하는 수임. 이런 수라면 이 게임에서 n으로 간주할 수 있음.

예로써, 이 게임에서는 3을 건드리면 2 또는 1 또는 0을 얻게 됨.
근데 (1,2)를 건드리면 (0,2)=2 또는 (1,0)=1 또는 (1,1)=0을 얻을 수 있으므로
(1,2)는 3과 같은 역할을 하고 있음. 이 게임에서 본질적으로 (1,2)=3임.

그럼 (2,3)은? 건드려서 0=(2,2)은 얻을 수 있는데 1을 얻을 길이 없음.
2나 3을 얻을 수는 있지만 1을 창출할 수 없으므로 본질적으로 (2,3)=1인 것임.
(2,3)을 상대가 건드리면 0=(2,2)을 얻거나,
(1,3), (0,3), (2,1), (2,0) 따위가 되어 내가 다시 1을 만들어 돌려줄 수 있음. 즉,
1. 상대가 건드렸을 때 0이거나
2. 상대가 건드려 1 이상이 되었다 할지라도 내가 1로 되돌릴 수 있으므로
(2,3)=1인 것임.

(1,4)는 4=(0,4), 3=(1,2), 2=(1,3), 1=(1,0), 0=(1,1)을 모두 얻을 수 있으므로 (1,4)=5이며,
(1,5)는 3=(1,2), 2=(1,3), 1=(1,0), 0=(1,1)는 만들 수 있지만 4를 얻을 길이 없어 (1,5)=4임.
이런 식으로 추론을 진행하면 (a,b)=x의 조견표를 웬만큼 작성할 수 있음.(필수는 아님. 아래 참조)

4줄 게임인 (a,b,c,d)에서
(a,b)=x, (c,d)=y로 표현할 수 있다면 (x,y)의 2줄 게임으로 관리할 수 있어 보다 쉬움.
(하다 보면 (a,d)=x, (b,c)=y 식으로 손쉬워지는 조합을 취향대로 골라잡게 됨.)

바로 위의 (1,2)=3, (1,4)=5 식으로 (a,b)=x 조견표를 작성하다 보면
(1,2,3), (1,4,5) 식으로 3줄 조견표에서 작성한 것과 배열이 같음을 알 수 있음. 즉,
1=(2,3)=(4,5)=(6,7)...
2=(1,3)=(4,6)=(5,7)...
3=(1,2)=(4,7)=(5,6)...

따라서 (a,b)=x를 찾는 조견표는 필요가 없음. 3줄 조견표를 보면 됨.
심지어 익숙해지면 3줄 조견표도 필요 없음. 간단한 몇 가지만 체득하면
계산으로 (a,b,x)를 풀 수 있음. 그 단계가 되면 조견표는 계산이 맞는지 검산용이 됨.

위 설명 [3줄]에서 (a,b,x)의 x를 찾는 방법을 설명한 바,
그 예에서 (8,13)=5였음. 즉 (5,8,13)으로부터, (5,8)=13, (5,13)=8, (8,13)=5인 것임.
이것을 활용하면 몇 줄이 되더라도 둘씩 축약하고, 그 축약된 것을 또 둘씩 축약하여
간단한 형태로 변형하여 (1,1,1) 또는 (n,n)형을 향해 오류 없이 줄여나갈 수 있음.

이제는 위에 나열한 3줄의 모든 필승형이 본질적으로 (n,n)형태임을 알 수 있음.
예를 들면 (3,4,7)에서 (4,7)=3이므로 (3,4,7)=(3,3)=0인 것임.
그러므로 이 게임은 (n,n)형을 누가 먼저 만들고 유지하느냐 하는 문제가 되며,
어떤 식으로 몇 줄을 늘어놓든 필승형으로 만들 수 있는 길이 있음.

그런데 특정 배열마다 유일해가 있는 것은 아닌 것 같음.
예로써 4줄 게임 (3,4,5,6)이 제시되면 어떤 식으로 짝을 지어 축약하느냐에 따라
1. (3,4)=7, (5,6)=3이므로 (3,4,5,6)=(7,3), 그러므로 (3,4)를 3으로, 그러자면 4를 0으로 만듬.
2. (3,6)=5, (4,5)=1이므로 (3,6,4,5)=(5,1), 그러므로 (3,6)을 1로, 그러자면 6을 2로 만듬. (3,2)=1. (새로운 해법)
3. (3,5)=6, (4,6)=2이므로 (3,5,4,6)=(6,2), 그러므로
   a. (3,5,4,6)=(6,4,6)으로 보아 (6,0,6) 즉 4를 0으로 만들거나 (1과 동일해짐)
   b. (3,5,4,6)=(6,2)로부터 (3,5)를 2로 만들기 위해 (3,1)=2, 즉 5를 1로 바꿈. (또 다른 새로운 해법)

즉 (3,4,5,6)의 초기 공략은
* (3,0,5,6)이거나
* (3,4,5,2)이거나
* (3,4,1,6)이 됨. 경로에 따라 선택은 여럿으로 보임.
대신 어떤 필승형이든 고른 다음에는 어떤 식으로 짝을 짓든 (n,n)형이 됨.

예로써 (3,4,1,6)의 경우,
(3,4)=7, (1,6)=7, 따라서 (3,4,1,6)=(7,7)=0
(3,1)=2, (4,6)=2, 따라서 (3,1,4,6)=(2,2)=0
(3,6)=5, (4,1)=5, 따라서 (3,6,4,1)=(5,5)=0

이하 [5줄]~[7줄]은 위 패턴을 겹겹으로 반복할 따름이므로 설명을 생략함.
결론적으로, 이 게임은 전체 형태가 0이 되도록 만드는 게임이며,
위 개념을 갖고 풀어보니 초기설계만 고심하면 7줄이라도 시간 문제일 따름이 됨.

예를 들면,
6,10,13,17,20,25,28 로 배열된 7줄 게임에서,

(25,28)=5임. 16씩을 빼면 (9,12)이며 (5,9,12)로부터 (9,12)=5와 같음.
(17,20)=5임. 16씩을 빼면 (1,4)이며 (1,4,5)로부터 (1,4)=5와 같음.

그러면 (6,10,13),5,5 와 동일한 모양으로 볼 수 있고,
(5,5)=0이므로 (6,10,13)만 0의 형태로 만들면 됨. (6,10,x)를 풀면 (6,10,12)를 얻음.
따라서 6,10,13,17,20,25,28의 처음 공략은 13을 12로 바꾸는 것이 됨.
이후 (6,10,12), (17,20), (25,28)로 묶어 상대의 응수에 따라 대응하면 됨.

일례로 상대가 20을 움직여 (6,10,12), (17,18), (25,28)로 만들면,
(17,18)=3이므로 (25,28)을 3으로 만들어야 (6,10,12),3,3가 되어 계속 승리가 유효한 상태를 유지할 수 있음.
(25,28)=(9,12)인 바, 3을 만들려면 (3,9,10)을 활용, x-16=10, x=26
즉 28을 26으로 고쳐 (6,10,12), (17,18), (25,26)으로 만드는 것이 바른 대응임.

***

위에서 왜 하필 k=2,4,8,16,...이며 a<k여야 하는지는
뭔가 게임의 구슬 수로 나타나는 물리적인 의미가 있을 듯 합니다만,
아직 선명하지 않네요. 이건 숙제로 남겨 두겠습니다. 뉘든 풀어주시길~

끝.