d라이브러리

혼자 먹고 혼자 노는 사람들이 늘어나는 요즘, 혼자 즐길 수 있는 퍼즐을 소개할게요. 
무려 300년 동안 사랑받고 있는 고전 게임 ‘페그 솔리테어’입니다!

※ 편집자 주
KPP는 ‘퍼즐을 좋아하는 사람들의 모임’입니다. 저희들의 퍼즐 이야기를 통해 신기한 퍼즐과 그 속에 숨은 수학을 즐겨보세요!

페그는 ‘말뚝’, 솔리테어는 ‘혼자서 한다’는 뜻으로, 페그 솔리테어는 ‘말뚝을 가지고 혼자 즐기는 게임’이라고 볼 수 있어요. 페그 솔리테어는 원 모양으로 움푹 패인 자리가 있는 게임판과 말뚝 역할을 하는 구슬로 이뤄져 있습니다. 게임판은 자리의 수와 배열에 따라 다양한데, 배열이 십자 모양인 영국식과 팔각형인 유럽식 게임판이 잘 알려져 있죠.

페그 솔리테어의 목표는 구슬을 옮겨 처음 배열에서 목표 배열로 만드는 겁니다. 그런데 구슬을 옮기려면 규칙을 따라야 합니다. 뜀틀을 넘듯 인접한 구슬을 뛰어넘어야 하고, 뜀틀 역할을 한 구슬은 게임판에서 빼야 하죠. 또 인접한 구슬이 없으면 움직일 수 없고, 대각선을 뺀 가로 또는 세로 방향으로만 움직여야 합니다.

규칙은 단순하지만, 페그 솔리테어를 푸는 건 간단하지 않습니다. 구슬을 몇 개 옮기다 보면 구슬을 더는 움직일 수 없는 상황이 생기거든요. 게다가 구슬을 움직일 수 있는 순서와 방향의 경우의 수도 많습니다. 실제로 어떤 배열이 주어졌을 때 목표 배열로 만들 수 있는 방법이 있는지 판별하는 문제는 문제의 크기가 n일 때 n¹⁰⁰, n²+2n처럼 n에 관한 다항식 꼴로 표현된 횟수 안에 푸는 방법이 밝혀지지 않은 ‘NP-완전 문제’예요.

‘파고다 함수’로 분석한 페그 솔리테어

어떤 배열이 있을 때 목표 배열을 만들 방법이 없다면 구슬을 아무리 움직여도 헛수고일 거예요. 그래서 수학자들은 맞출 수 있는 퍼즐인지 알아내는 방법을 찾기 위해 노력했습니다. 그 결과 중 하나가 바로 ‘파고다 함수’입니다. 

파고다 함수란 게임판의 각 자리에 수를 적은 뒤 어떤 배열이 주어지면 구슬이 있는 자리에 적힌 수를 모두 더한 값을 계산하는 함수입니다. 이때 자리에 아무 수나 적을 수 있는 것은 아닙니다. 가로 또는 세로 방향으로 연속한 3개의 자리에 적힌 수가 각각 P, Q, R일 때, 부등식 P+Q≥R을 만족해야 하지요. 주의할 점은 방향에 상관없이 항상 부등식을 만족해야 한다는 겁니다.

예를 들어 가로 방향으로 연속한 3개의 자리에 왼쪽부터 2, 1, 1이 적혀 있다면 P=2, Q=1, R=1을 대입했을 때(2+1≥1)와 반대 방향으로 P=1, Q=1, R=2를 대입했을 때(1+1≥2) 모두 부등식을 만족하죠.   

파고다 함수가 유용한 이유는 무엇일까요? 바로 구슬을 옮겨 배열이 바뀌어도 파고다 함숫값이 증가하지 않기 때문입니다. 이 성질을 이용하면 목표 배열의 파고다 함숫값이 처음 배열의 파고다 함숫값보다 클 때 퍼즐을 절대 풀 수 없다는 사실을 알 수 있거든요.

2020년 4월 세상을 떠난 미국의 수학자이자 퍼즐리스트 존 콘웨이는 페그 솔리테어의 규칙을 응용해 ‘콘웨이의 병정들’이라는 재밌는 문제를 만들었습니다. 무한한 격자와 이를 반으로 가르는 수평선이 있을 때 수평선 아래에 병정을 원하는 수만큼, 원하는 위치에 배열할 경우, 페그 솔리테어와 똑같은 규칙으로 병정이 수평선을 넘어 얼마나 멀리 갈 수 있는지 구하는 문제입니다. 이 문제를 자세히 알고 싶으면 폴리매스 홈페이지를 참고하세요!