본문바로가기
[KPP의 퍼즐라이프] '스핀아웃'과 재귀적 퍼즐
수학동아 2020.01.02 14:31

 

 

 

 

 

KPP와 함께하는

퍼즐라이프

 퍼즐러가 사는 법 

 

 

 

퍼즐을 좋아하는 사람들이 모인 단체

KPP _Korean Puzzle Party 멤버들이 

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

KPP와 함께 신기한 퍼즐을 살펴보고

 속에 숨은 수학도 즐겨보세요!

 

 

 

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

 

 

 

안녕하세요!

첫 번째로 ‘퍼즐라이프’를 공개할 KPP 멤버 한동규입니다. 저는 지금 겨울방학을 맞아 방안을 뒹굴며

어떤 퍼즐을 '첫 주자'로 삼을까 고민하고 있습니다.

재미는 있으면서, 어려우면 안 되겠죠?

흠...

그러면 잘 알려진 하노이 탑과 원리가 비슷한

스핀아웃은 어떨까요?

 

 

 

 

 

 

1

천리길도 '재귀적 퍼즐'부터!

 

이런!

KPP 대화방에 ‘스핀아웃 있으신 분~’

하고 글을 남겼는데 아무도 대답이 없군요.

 

 

뭐, 예상했습니다!

1972년 미국의 전기공학자 윌리엄 케스터가 개발한 스핀아웃은

1985년 ‘수학적인 아이디어를 장난감으로 만들자’

는 목표를 가지고 설립한 미국의 장난감 회사 ‘씽크펀’이 제작했지만,

몇 년 전 생산을 중단해 구하기가 어려워졌거든요.

(사진을 제공해 준 제임스 스토러 미국 브랜다이스대학교 컴퓨터과학과 교수님 감사합니다ㅜㅜ)

 

 

 

 

 

 

 

스핀아웃을 개발한 장난감 회사 '바이너리 아츠(Binary Arts)'는 이후 이름을 '씽크펀'으로 변경했다. 

바이너리 아츠 시절 만든 스핀아웃(위)와 씽크펀으로 바꾼 뒤 만든 스핀아웃(아래).

출처: James A. Storer

 

 

 

 

 

그럼에도 불구하고 왜 골랐느냐!

스핀아웃이 흥미로운 재귀적 퍼즐이기 때문입니다.

재귀적 퍼즐이 뭐냐고요?

음~~~.

유명한 ‘하노이 탑’을 예로 들어 설명해보죠.

 

 

수학 퍼즐을 좋아하는 사람이라면

하노이 탑을 들어보았을 겁니다.

하노이 탑은

 

 

한 기둥에 큰 것부터 크기 순서대로 꽂혀 있는 원판을

그대로 다른 기둥에 옮기는 퍼즐

 

 

입니다.

 

 

원판을 하나씩 옮겨야 하고,

큰 원판이 작은 원판 위에 있으면 안된다

는 규칙 때문에 푸는 게 만만치 않죠.

(아래 그림 참고)

 

 

 

 

'원판 5개를 옮기겠다!'

고 마음 먹으면

필연적으로 4개를 먼저 옮겨야합니다.

 

 

즉, 어떤 수의 원판을 옮기려면

더 작은 수의 원판을 먼저 옮겨야 하는데,

이런 퍼즐이 바로 재귀적 퍼즐입니다.

 

 

수학하노이 탑과 더불어 오늘의 주인공인 스핀아웃,

수학동아 2018년 10월호 특집 기사(dl.dongascience.com/magazine/view/M201810N009)

에 소개된 적 있는 구연환도 비슷한 특징을 갖고 있죠.

 

 

이런 특징과 더불어 하노이 탑은 조각 하나가 늘어날 때마다

퍼즐을 푸는 데 두 배의 시간이 걸리는

퍼즐로 잘 알려져있는데요,

그 이유가 궁금하지 않나요?

 

 

자,

자세한 내용은 스핀아웃을 살펴보며 얘기하도록 하죠!

 

 

 

 

 

 

2

스핀아웃과, 재귀적 퍼즐과, 푸는 시간

(feat. 점화식)

 

 

 

 

스핀아웃의 구조.

 

 

 

 

먼저 스핀의 생김새부터 살펴보죠.

스핀아웃에는 직사각형의 긴 판,

그 위에 세 면이 오목하게 파인 회전 원판

7개 붙어있습니다.

 

 

긴 판은 레일에 갇혀 있는데,

레일에서 판을 빼려고 하면

원판의 볼록한 부분이 입구에 걸립니다.

 

 

눈치챘나요?

스핀아웃은 바로

 

 

모든 원판의 볼록한 부분을

왼쪽으로 향하게 돌려 판을 빼내는 퍼즐

 

 

입니다.

 

 

사람 가득한 지하철에서

옆 사람이 비켜주지 않으면 꼼짝할 수 없듯,

다닥다닥 붙어있는 회전 원판도

두 가지 조건을 충족해야 돌릴 수 있습니다.

 

 

하나는 돌 수 있을 만큼 공간이 넓은 레일의 파인 지점에 있어야 한다는 것,

다른 하나는 원판의 오목한 부분과 바로 오른쪽 원판의 볼록한 부분

닿지 않아야 한다는 거죠.

 

 

어려워 보인다고요? 걱정마세요!

재귀적 퍼즐이 재밌는 이유는 풀이법을

'수학적'으로 분석하기 좋기 때문입니다.

 

 

스핀아웃의 풀이를 수학적으로 바꿔보죠.

 

 

아까 판을 빼려면 모든 원판을 왼쪽으로 90° 돌려야한댔죠?

레일 입구에서 가까운 순서대로 번호를 매겼을 때

1번부터 n번까지만 먼저 돌리는 문제를 생각한 뒤,

모든 n에 대해서 문제를 풀면 퍼즐을 풀 수 있는 겁니다~.

 

 

이제 재귀라는 성질을 이용해 푸는 방법을 살펴볼까요?

풀이가 복잡하면,

아래 스핀아웃 풀이 맛보기를 참고하세요~

 

 

 

n번을 돌리려면 1번부터 n-2번까지가 왼쪽으로 돌아가 있어야 한다.

 

n-2개의 원판을 출구 밖으로 내보내야 n번을 파인 지점에 놓을 수 있기 때문!

 

n번을 돌리고 나면 n-1번을 왼쪽으로 돌려야 하는데,

이미 n-2번이 왼쪽을 향하고 있어서 n-1번을 돌릴 수가 없다.

 

그러므로 n-2개의 원판을 다시 원상복귀하고,

마지막으로 n-1개의 원판을 왼쪽으로 회전시킨다.

 

 

 

 

 

여기서 또다른 궁금증.

판을 뺄 때까지 원판을 총 몇 번 회전해야 할까요?

이제 재귀의 성질과 점화식_인접한 항 사이의 관계를 나타낸 식

을 이용하면 구할 수 있습니다.

(여기서부터 약간 더 수학!)

 

 

원판 n개를 돌릴 때 필요한 회전수가 Rn이면

재귀적 성질에 의해 점화식

R= 1 + 2 x Rn-2 Rn-1

로 나타낼 수 있어요.

 

 

이제 이 점화식을 풀면!

뾰로롱

 

R= [\frac{2^{n+1}}{3}]

 

임을 알 수 있죠.

 

 

이 식의 n에 수를 대입해 보면

원판이 1개 늘면 회전수가 2배 늘어난다

는 사실을 금새 알 수 있죠!

 

*[ ]는 괄호 안의 수를 넘지 않는 가장 큰 정수를 뜻해요!

 

 

 

 

이처럼 더 작은 부분 문제를 풀어야

원래의 문제를 풀 수 있는 구조

를 수학이나 컴퓨터 과학에서는 재귀라고 합니다.

 

 

n개의 원판을 돌리기 위해서는

n-1개나 n-2개의 원판을 돌릴 수 있어야 하듯이요.

 

 

그래서 우리는 하노이 탑, 구연환, 스핀아웃 같은 퍼즐을

재귀적 퍼즐이라고 부릅니다.

 

 

종종 'n진 퍼즐'이라고도 하는데,

각각의 상태를 n진수와 대응시킬 수 있기 때문이에요.

(구연환과 스핀아웃은 이진 퍼즐, 하노이 탑은 3진 퍼즐)

 

 

 

자, 더 말하면 퍼즐을 직접 풀 분들에게

TMI가 될 것 같으니 이만 마쳐야겠군요!

 

 

첫 번째 퍼즐 라이프는 어땠나요?

스핀아웃 뿐 아니라 재밌는 재귀적 퍼즐이 많으니 어서 도전해보세요! 

 

 

 

 

 

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

 

 

 

함 께 풀 어 보 세 요

 

스핀아웃과 재귀적 퍼즐이 뭔지 감이 잡히나요?

내용을 이해했으면 아래 문제를 풀어보세요.

 

문제를 풀 아이디어 및 정답을 댓글로 달면

KPP 멤버가 직접 답변해 줄 거예요!

 

 

 

 

1.

판을 레일에서 빼내려면 원판을 총 몇 번 돌려야 할까요?

점화식을 이용해 구해보세요!

 

2.

레일을 벗어난 원판은 마음껏 회전할 수 있으므로

회전수를 엄청나게 줄일 수 있어요.

제작자가 의도한 풀이는 아니지만,

이때 회전수의 최솟값을 찾아보세요!

 

3.

나만의 재귀적 퍼즐을 만들어 보세요!

 

 

 

-끝-

 

 

  •  
    21세기오일러 Lv.11 2020.01.10 14:52

    15퍼즐도 재귀적 퍼즐인가요?

    댓글 작성하기 좋아요0 댓글수2
    •  
      KPP Lv.1 2020.06.08 15:21

      결론부터 말하면, 15퍼즐은 재귀적 퍼즐이 아닙니다. 재귀적 퍼즐이 되려면 세 가지 조건을 만족해야 하거든요.

      1. "특별한 조각"들이 m개 반복되어 배치되고, 얼마든지 특별한 조각의 수를 늘려 퍼즐을 확장할 수 있다.

      2. 각 특별한 조각은 n개의 서로 다른 상태가 있다.

      3. 어떤 특별한 조각이 움직이기 위해서는 관련된 다른 특별한 조각들이 특정 상태에 있어야 하며, 이 조건은 모든 조각들에 동일하게 적용된다.

      하노이 탑을 예로 들어 봅시다. m개의 원판들이 특별한 조각이 되고, 각 원판은 세 개의 서로 다른 기둥에 위치할 수 있기 때문에 세 가지 상태를 가지지요. 원판을 작은 것부터 순서대로 1, 2, ..., k, ..., m번이라고 할 때, "k번 원판이 움직일 수 있는 조건"은 "1번부터 k-1번까지의 원판이 하나의 기둥에 있어야 하며, 그 기둥은 k번 원판의 기둥과 달라야 한다."가 됩니다.

      한편 15퍼즐은 동일한 조각 15개가 있긴 하지만, 판의 크기를 유지한 채 퍼즐 조각의 수를 얼마든지 늘릴 수는 없습니다. 조각을 늘리려면 판의 크기를 늘려야 하고, 그러면 각 조각이 가지는 상태의 수 역시 많아지게 되지요. 하노이 탑의 원판이 많아지더라도 기둥은 항상 세 개인 것과 상반됩니다.

      좋아요0
    •  
      21세기오일러 Lv.11 2020.07.01 20:43

      오오 답변 감사합니다.

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

  • ☎문의 02-6749-3911