KPP와 함께하는

퍼즐라이프

 퍼즐러가 사는 법 

퍼즐을 좋아하는 사람들이 모인 단체 KPP_Korean Puzzle Party 멤버들이

매달 재밌고 유익한 퍼즐 이야기를 들려드립니다. 

KPP와 함께 신기한 퍼즐을 살펴보고 그 속에 숨은 수학도 즐겨보세요!

*사진 출처: Shutterstock

--------------------------------

안녕하세요, KPP 멤버 한동규입니다.

혼자 먹고 혼자 노는 사람들이 늘어나는 요즘, 혼자 즐길 수 있는 퍼즐을 소개할게요.

무려 300년 동안 사랑받고 있는 고전 게임 페그 솔리테어입니다!

1

뜀틀 넘듯 말뚝 움직이기

페그는 ‘말뚝’, 솔리테어는 ‘혼자서 한다’는 뜻으로,

페그 솔리테어는 말뚝을 가지고 혼자 즐기는 게임이라고 볼 수 있어요.

실제로도 구슬을 놓을 수 있도록 움푹 패인 자리가 있는 게임판에서

말뚝 역할을 하는 구슬을 이리저리 옮기며 즐기는 방식이죠.

게임판은 자리의 수와 배열에 따라 종류가 다양한데요,

배열이 십자 모양인 영국식 게임판과 팔각형인 유럽식 게임판이 잘 알려져 있습니다.

영국식 게임판(왼쪽)과 유럽식 게임판(오른쪽).

게임판의 패인 곳 몇 군데를 골라 구슬을 놓으면

다양한 구슬 배열을 만들 수 있겠죠?

페그 솔리테어의 목표는

어떤 배열(처음 배열)에서 구슬을 옮겨 다른 배열(목표 배열)로 만드는 것

이에요.

그런데 구슬은 옮길 때는 아래 세 가지 규칙을 따라야 합니다.

그 규칙은 바로

① 뜀틀을 넘듯 이웃한 구슬을 뛰어넘을 것!

② 대각선을 뺀 가로 또는 세로로만 움직일 것! 

③ 뜀틀 역할을 한 구슬을 게임판에서 뺄 것!

입니다.

가로 또는 세로로 이웃한 구슬을 뛰어 넘어서 이동할 수 있다.

대각선 방향으로는 이동할 수 없다.

규칙은 단순하지만, 푸는 건 간단하지 않습니다.

구슬을 옮기다 보면 더는 구슬을 움직일 수 없는 상황이 생기거든요.

그렇다고 계획을 세워 움직이기엔

구슬을 움직일 수 있는 순서와 방향의 경우의 수가 무척 많죠.

실제로 처음 배열과 목표 배열이 주어졌을 때 이 퍼즐을 풀 수 있는지,

즉 처음 배열을 목표 배열로 만들 수 있는지 판단하는 문제는 

다항 시간 안에 푸는 방법이 밝혀지지 않은 NP-완전 문제임이 알려져 있습니다.

2

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

어떤 배열이 있을 때 목표 배열을 만들 방법이 없다면

구슬을 아무리 움직여도 헛수고일 거예요.

그래서 수학자들은 맞출 수 있는 퍼즐인지 알아내는 방법을 찾기 위해 노력했습니다.

그 결과 중 하나가 바로 파고다 함수입니다.

파고다 함수란

게임판의 각 자리에 수를 적은 뒤 어떤 배열이 주어지면

구슬이 있는 자리에 적힌 수를 모두 더한 값을 계산하는 함수입니다.

이때 자리에 아무 수나 적을 수 있는 것은 아닙니다.

가로 또는 세로 방향으로 연속한 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)

모두 부등식을 만족하죠.

파고다 함수가 유용한 이유는 구슬을 옮겨 배열이 바뀌어도

파고다 함숫값이 증가하지 않기 때문입니다.

이 성질을 이용하면

목표 배열의 파고다 함숫값이 처음 배열의 파고다 함숫값보다

클 때 퍼즐을 절대 풀 수 없다는 사실을 알 수 있거든요!

파고다 함수의 규칙에 맞게 게임판의 수를 적고, 처음 배열과 목표 배열의 파고다 함숫값을 계산한다.

목표 배열의 함숫값이 처음 배열의 함숫값보다 크면 풀 수 없다.

3

존 콘웨이와 '콘웨이의 병정들'

2020년 4월 세상을 떠난 미국의 수학자이자 퍼즐리스트 존 콘웨이는

페그 솔리테어의 규칙을 응용해 콘웨이의 병정들이라는 문제를 만들었습니다.

콘웨이의 병정들은

수평선이 그어진 무한한 격자에서

수평선 아래에 병정을 원하는 수만큼 원하는 위치에 놓고

페그 솔리테어의 규칙대로 병정을 움직일 때

병정이 수평선을 넘어 얼마나 멀리 갈 수 있는지 구하는 문제입니다.

얼핏 생각하면

아래쪽 반평면에 얼마든지 많은 병정들을 배치할 수 있기 때문에

위쪽으로 얼마든지 멀리 갈 수 있을 것 같습니다.

그런데 놀랍게도 병정들은 수평선 위로 다섯 칸 떨어진 곳조차 도달할 수 없습니다!

파고다 함수를 이용해 이 사실을 증명해 보죠.

도달하고 싶은 수평선 위 다섯 번째에 있는 칸 하나를 '중심'으로 지정하고,

각 칸에는 중심으로부터의 맨해튼 거리가 d일 때 p^d를 적습니다.

이제 양수 p의 값을 정해야 하는데, 파고다 함수의 조건을 만족하려면

p²+p≥1와 1+p≥p²이 성립해야 하죠.

조건을 성립하는 p의 최솟값 을 고르면

반평면 아래에 얼마나 많은 병정을 배치하든

파고다 함숫값이 1 이상이 될 수 없음을 보일 수 있습니다.

하지만 도달하고 싶은 위치에는 1이 적혀 있기 때문에

목표 상태의 파고다 함수값이 처음 상태의 파고다 함수값보다 크지요.

따라서 수평선 위 다섯 칸 떨어진 곳에는 도달할 수 없습니다!

각각의 수를 높이로 생각하면 불교의 사원처럼 보여서 불교 사원을 뜻하는 '파고다'라는 이름이 붙었다.

1:p가 황금비를 이루기 때문에 '황금 파고다 함수'라고도 부른다.  

간단한 파고다 함수가 페그 솔리테어를 풀 때 무척 유용하죠?

이제 여러분의 차례입니다.

오늘 들려준 내용을 모두 이해했으면,

아래 문제에 도전해보세요!

--------------------------------

함 께 풀 어 보 세 요

1.

구슬을 옮길 때 파고다 함숫값이 증가하지 않는 이유는 무엇인가요?

2.

영국식 게임판에서 파고다 함수 규칙에 따라 수를 적을 때,

음수를 적을 수 있는 자리는 어디일까요?

3.

콘웨이의 병정들에서 병정을 4칸 위로 보내려면

수평선 아래에 병정을 어떻게 배치해야 할까요?  

-끝-