d라이브러리

촘프는 미국의 수학자이자 경제학자인 데이비드 게일이 만든 게임이에요. 게일은 게임이론, 램지이론 등을 연구하면서 촘프, 브릿짓 같은 보드게임도 만들었어요. 촘프는 ‘음식을 쩝쩝 먹는다’는 의미 그대로 초콜릿을 먹으면서 하는 게임이지만, 모양이 비슷한 블록이나 바둑돌같이 간단한 도구만 있어도 즐길 수 있어요.

규칙도 간단합니다. 격자 모양 사각형 초콜릿을 준비하고 왼쪽 맨 아래 조각을 독이 든 조각으로 정합니다. 이제 상대와 번갈아 가며 초콜릿 조각을 선택한 뒤 선택한 조각을 포함해 오른쪽과 위에 있는 모든 초콜릿 조각, 그리고 이 초콜릿으로 둘러싸인 영역에 있는 초콜릿을 모두 먹어치웁니다. 이렇게 상대와 번갈아 가며 초콜릿을 먹다가 독이 든 초콜릿 조각을 먹는 사람이 지는 게임입니다. 아래와 같이 세로가 4조각, 가로가 5조각인 초콜릿으로 하는 촘프 게임을 살펴보고, 친구와 함께 다양한 크기의 초콜릿으로 게임을 해보세요.

초콜릿 크기를 바꿔가며 촘프 게임을 해봤나요? 보드게임 페스타를 즐겨보는 독자라면 슬슬 ‘승
리할 수 있는 전략은 무엇일까?’라는 궁금증이 들 거예요. 이 질문에 답하기 위해 우선 몇 가지 용
어를 정하도록 하죠. 먼저 세로 m칸, 가로 n칸인 초콜릿에서 하는 촘프 게임을 ‘m×n 촘프’라고 하
고 각 조각의 위치는 왼쪽 맨 아래 조각을 기준으로 가로와 세로로 몇 번째 칸에 있는지 세어 좌표
로 나타낼 거예요. 예를 들어 아래 표시된 조각은 가로로 3번째, 세로로 2번째에 있으니 (3, 2)고
독이 든 조각은 (1, 1)이에요. 그러면 ( p, q) 조각을 선택했을 때 p보다 크거나 같은 r, q보다 크거나 같은 s, 즉 (r, s) 조각을 모두 먹어야 해요.

1974년 게일은 초콜릿 크기와 관계없이 먼저 먹는 사람이 이기는 전략이 있음을 증명했어요. 증명을 위해 처음에 내가 (m, n) 조각을 선택하고 상대는 (i, j) 조각을 선택했다고 가정해 볼게요. 또 매번 최선의 선택을 했다고 가정해요. 즉 실수로 지는 일은 없어요.

게일의 아이디어는 이렇습니다. 처음에 (m, n) 조각을 선택해서 지면, 다시 처음으로 돌아가 (m, n) 조각 대신 상대가 택한 (i, j) 조각을 선택해버리는 겁니다. 그러면 순서가 하나씩 밀려 내가 먹은 조각이 상대가 먹은 것이 되고, 상대가 먹은 조각은 내가 먹은 조각이 돼서 독이 든 조각도 상대가 먹게 되지요. 예를 들어 143쪽 게임 상황을 보면 가장 먼저 (4, 2)를 선택해서 졌어요. 따라서 상대가 고른 (3, 3)을 먼저 택해요. 그럼 상대는 내가 골랐던 (3, 1)을 고르겠죠. 그 순간 남은 초콜릿은 앞 상황과 같고 순서만 바뀐 걸 알 수 있어요. 이대로 가면 내가 이기겠죠? 즉, 이 방법을 이용하면 게임 결과에 상관없이 이기는 전략을 만들어 낼 수 있어요.

종이와 펜만 있어도 OK!

촘프 게임을 부분순서집합이나 약수 같은 수학 개념으로 바꿔서 즐길 수 있어요. 부분순서집합은
집합에 포함된 원소 중 일부만 크기를 비교할 수 있는 집합을 말해요. 아래 두 집합을 보세요.

첫 번째 집합은 어떤 두 수를 택해도 크기를 비교할 수 있어요. 그런데 두 번째 집합은 a와 1의 크
기를 비교할 수 없으니 부분순서집합입니다.

간단하게 2×3 촘프를 부분순서집합으로 바꿔 보도록 하죠. 우선 모든 조각을 좌표로 나타낸 뒤 한데 모아 집합 {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)}를 만듭니다. 이 집합에서는 좌표의 가로와 세로가 모두 크거나 같은 좌표를 ‘크다’고 할 거예요. 따라서 (2, 2)는 (2, 1)보다 크지만 (3, 1)과는 크기를 비교할 수 없으니 이 집합은 부분순서집합입니다. 이제 초콜릿 조각을 선택하는 대신 좌표를 선택하고, 초콜릿을 먹는 대신 좌표보다 ‘큰’ 좌표를 모두 지워 가며 게임을 즐깁니다. 그러면 (1, 1)을 지우는 사람이 지는 촘프 게임이 됩니다.

3차원 촘프도 있다!

직육면체에서도 촘프 게임을 할 수 있습니다. 직육면체는 가로, 세로에 높이까지 있으니 좌표의 수를 하나 늘려 높이도 표시해 줘야 합니다. 그러면 독이 든 초콜릿은 (1, 1, 1)이 되고, 플레이어가 (i, j, k) 조각을 선택하면 i≤p, j≤q, k≤r인 (p,q, r) 조각을 모두 지우면 됩니다. 3×3×3 촘프는 꼭 루빅스 큐브와 비슷한 모습이겠죠?

촘프 게임과 비슷한 ‘님’ 게임도 함께 즐겨보세요. 님은 초콜릿을 먹는 대신 판에 달린 끈 중의 하나를 골라 끈에 걸려 있는 돌을 원하는 만큼 움직이는 게임입니다. 상대와 번갈아 가며 돌을 옮기다 마지막 하나 남은 돌을 움직이는 사람이 지는 게임입니다. 잘 알려진 배스킨라빈스 게임★은 끈이 하나에 돌이 31개인 님 게임으로 볼 수 있습니다. 여러분이 직접 촘프 게임과 님 게임, 배스킨 라빈스 게임의 승리 전략을 찾아보세요!