본문바로가기
[KPP의 퍼즐라이프] 술술 넘겨봐! 페그 솔리테어
수학동아 2020.05.26 14:55

 

 

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일 때 pd를 적습니다.

 

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

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

 

조건을 성립하는 p의 최솟값 \frac{\sqrt{5}-1}{2}을 고르면

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

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

 

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

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

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

 

 

 

 

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

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

 

 

 

 

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

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

 

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

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

 

 

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

 

 

 

함 께 풀 어 보 세 요

 

1.

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

 

 

2.

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

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

 

 

3.

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

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

 

 

 

-끝-

 

 

 

  •  
    MathlabJ Lv.8 2020.06.01 12:40 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      KPP Lv.2 2020.06.08 15:29

      정답입니다~~ 다른 문제들의 답도 한번 생각해 보세요!

      좋아요0
  •  
    은총알 Lv.11 2020.09.27 14:41 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      KPP Lv.2 2021.01.13 18:55

      1,2번 정답입니다!!

      좋아요0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911