별과 정리 · 제77장 · 1부 · 누구나 손댈 수 있는 것

펜토미노

Pentominoes

정사각형 다섯 개로 만드는 열두 모양

정사각형 다섯 개로 온 세상을 채웁니다

정사각형 다섯 개를 변끼리 맞붙여 만들 수 있는 모양은 몇 가지일까요? 돌리거나 뒤집어 겹치는 것을 하나로 치면 정확히 열두 가지입니다. 알파벳을 닮아 펜토미노라 부릅니다.

열두 조각을 다 쓰면 칸이 예순입니다. 그렇다면 6×10 직사각형을 빈틈없이 채울 수 있을까요? 된다면 방법은 몇 가지일까요?

이야기

솔로몬 골롬 초상 — 솔로몬 골롬
National Science Foundation
Public domain · 위키미디어 공용

1953년, 하버드 대학원생 솔로몬 골롬이 수학 동아리에서 발표를 하다 「폴리오미노」라는 말을 지어냅니다. 스물두 살이었습니다. 그는 나중에 우주선과 지구 사이의 통신에 쓰이는 신호를 설계한 공학자가 됩니다.

그런데 이 놀이의 진짜 재미는 「몇 가지로 채울 수 있나」에 있습니다. 6×10은 2339가지인데, 3×20은 단 두 가지뿐입니다. 칸 수는 똑같이 예순인데 말입니다.

왜 이렇게 차이가 날까요. 폭이 좁을수록 조각을 놓을 자리가 급하게 줄기 때문입니다. 폭이 3이면 십자 모양이나 T자 모양은 놓을 수 있는 자세가 몇 안 됩니다.

게다가 좁은 통로에서는 한 조각을 놓는 순간 옆에 메울 수 없는 홈이 생기기 쉽습니다. 그래서 길이 급격히 막히고, 끝까지 살아남는 배열이 둘밖에 안 남는 것입니다.

오늘 이것이 하는 일

재단에서 재료를 아끼는 문제입니다. 철판·유리·천을 어떻게 배치해 잘라야 버리는 것이 가장 적은가.

화물 적재, 반도체 칩 배치, 창고 선반 채우기가 모두 같은 꼴이고, 컴퓨터가 되짚어 가기로 풉니다.

계단 넷 — 같은 사실을 네 깊이로

초4 · 초5 — 손으로 해 본다

모양을 모두 찾아본다

모눈종이에 정사각형 5개를 이어 붙여 만들 수 있는 모양들을 하나씩 그려 봅니다. 일자 모양(I), 십자가 모양(X), 계단 모양(W) 등을 찾다 보면 12가지가 모입니다.

조각들을 가위로 오려내어 3×20, 4×15, 5×12, 6×10 직사각형 틀 안에 퍼즐 맞추듯 끼워 넣으며 공간이 딱 들어맞는 손맛을 직접 경험해 보세요.

다섯 칸 조각을 세어 보세요

칸 수를 밀어 보세요.

조각의 수 —칸 수 —차지하는 칸 —

견줄 자리에서는 —몇 배 —

칸 수 n — 5

견줄 자리 nb — 8

5 칸이면 12 가지 — 이것이 펜토미노입니다.
12×5 = 60 칸이라 6×10 · 5×12 · 4×15 · 3×20 직사각형을 채웁니다.

중1 · 중2 — 까닭을 찾는다

직사각형을 채우기

12개 조각의 칸 수를 모두 더하면 칸입니다. 따라서 6×10, 5×12, 4×15, 3×20 직사각형을 만들 수 있습니다.

8×8 체스판(64칸)에서 한가운데 2×2 정사각형 4칸을 비워두고 나머지 60칸을 12개 펜토미노로 채우는 퍼즐도 가능합니다. 조각마다 차지하는 모서리 형태와 흑백 격자 칸 수의 짝홀성 제약을 고려하며 논리적으로 빈칸을 채워나갑니다.

직사각형을 채워 보세요

가로를 밀어 보세요.

채우는 방법 —칸 수 —60 인가 —

가로 — 6

세로 — 10

6×10 은 2,339 가지, 3×20 은 딱 2 가지뿐입니다.
좁아질수록 답이 급격히 줄어듭니다.

고1 · 고2 — 넓혀 본다

채우기 문제의 경우 수

펜토미노 채우기 문제는 조합론에서 정확한 덮개 문제(Exact Cover Problem)의 대표적 본보기입니다.

6×10 직사각형 채우기는 2339가지의 해가 존재하며, 3×20은 단 2가지 해만 존재합니다. 체스판의 흑백 착색 불변량을 적용하면 십자 모양(X) 펜토미노는 항상 한 가지 색 4개와 다른 색 1개를 덮는 성질 등을 이용해 불가능한 배치를 수학적으로 배제할 수 있습니다.

8×8 에 구멍 넷

구멍을 밀어 보세요.

남는 칸 —펜토미노로 채우려면 —맞나 —

구멍 수 — 4

구멍 4 개를 두면 60 칸 — 펜토미노 12 개로 딱 채워집니다.
구멍을 가운데 2×2 로 두면 65 가지 방법이 있습니다.

대학 — 어디까지 가나

완전 덮개 알고리즘

컴퓨터 과학의 거장 도널드 커누스는 펜토미노와 스도쿠 같은 완전 덮개 문제를 초고속으로 해결하기 위해 댄싱 링크(Dancing Links)를 활용한 DLX 알고리즘(Algorithm X)을 고안했습니다.

이차원 및 삼차원 폴리오미노 포장 문제는 NP-완전 문제에 속하며, 현대 물류 적재 최적화(Bin Packing), 집적회로 반도체 소자 평면 배치(VLSI Floorplanning), DNA 타일 자기조립 시뮬레이션의 기반이 됩니다.

NP-완전 문제입니다

칸 수를 밀어 보세요.

걸음 수 —칸 수 —조각 수 —

견줄 자리에서는 —몇 배 —

판 크기 n — 10

견줄 자리 nb — 32

폴리오미노 채우기는 NP-완전입니다.
판이 조금만 커져도 다 뒤지는 것이 불가능해집니다.

풀어 보기

중학교 · 고등학교 수준 · 답은 검산을 마쳤습니다

펜토미노의 조합. 회전과 대칭을 허용할 때 서로 다른 12개의 펜토미노 조각이 있다.

(1) 12개의 펜토미노 조각 전체의 넓이(단위 정사각형 개수)의 총합을 구하시오.
(2) 12개 조각을 모두 사용하여 직사각형을 만들 때, 가능한 직사각형의 가로×세로 크기 4가지를 모두 쓰시오.
(3) 회전이나 대칭을 해도 모양이 변하지 않는 유일한 펜토미노 조각의 알파벳 이름(모양)을 쓰시오.

(2) 총 칸수가 60이므로 6×10, 5×12, 4×15, 3×20입니다. (3) 십자가 모양인 X 펜토미노입니다.

답과 풀이 보기

(1) 칸입니다.
펜토미노는 이름 그대로 정사각형 다섯 개로 이루어진 조각이고, 그것이 12 가지입니다.

(2) 60 을 두 수의 곱으로 가르되 가로세로 모두 3 이상이어야 하므로
· · · 네 가지입니다.
은 폭이 너무 좁아 넣을 수 없는 조각이 생깁니다.
⭐ 넓이는 다 60 인데 답의 개수는 딴판입니다 — 은 2,339 가지, 은 단 2 가지뿐입니다.

(3) X 펜토미노(십자가 모양)입니다.
돌려도 뒤집어도 늘 같은 십자가입니다. 다른 열한 조각은 모두 모양이 달라집니다.
그래서 X 는 가장 넣기 까다로운 조각이기도 합니다 — 사방으로 삐죽해서 구석에 못 들어갑니다.

1953 년 솔로몬 골롬이 하버드 강연에서 이 조각들을 소개했습니다. 그 강연을 들은 학생 하나가 훗날 테트리스를 떠올리게 됩니다.
지금도 의 답 두 가지를 손으로 찾아내는 사람은 드뭅니다.

만지는 수학으로 손에 쥐어 보기

이 장과 이어지는 「만지는 수학」 칼럼입니다. 손끝으로 직접 끌고 눌러 보며 같은 생각을 몸으로 겪을 수 있습니다.

평면도형이동초4 다각형초4

더 멀리

조각으로 채우는 문제는 컴퓨터에게도 어렵습니다.

완전 덮개 문제 — 스도쿠와 같은 방식으로 풀 수 있습니다
재단과 적재 — 자투리를 줄이는 실제 문제입니다
직접 만들기 — 종이에 열두 조각을 그려 오려 보세요. 6×10을 채우는 데 한참 걸립니다

이어지는 장

정사각형 5개를 붙여 만든 12가지 서로 다른 모양의 조각으로 판을 빈틈없이 채우는 펜토미노 퍼즐은, 체스판에서 모서리 두 칸을 잘라냈을 때 도미노로 덮을 수 있는지를 따졌던 제58장 과 함께 도형의 분할과 타일링 속에 담긴 조합론적 깊이를 만끽하게 해 줍니다.

영감을 받은 곳

미국의 수학자 솔로몬 골롬(Solomon W. Golomb)이 1953년 하버드 수학클럽 강연에서 처음 소개하고 1954년 『미국수학월보』(American Mathematical Monthly)에 논문으로 발표한 폴리오미노(Polyominoes) 이론에서 왔습니다.