도미노 네 개로 2×4판 덮기, 두 방법이 같은 다섯 배치를 세어요

2×4판의 도미노 덮기는 5가지예요. 가로 묶음 수로 세는 풀이와 첫 열에서 갈라지는 풀이를 나란히 놓으면 점화 관계가 보여요.

바닥에 놓인 흰 도미노 조각들

사진: Dietmar Rabich · CC BY-SA 4.0 · 원본 출처

2×4 격자판을 1×2 도미노 네 개로 빈틈이나 겹침 없이 덮어요. 도미노는 가로 또는 세로로 놓을 수 있고, 판을 회전하거나 뒤집어 얻은 배치도 칸의 위치가 다르면 서로 다르게 세어요. 가능한 배치 수를 두 방법으로 구해 볼까요?

가로 도미노 하나가 나오면 위아래 두 줄을 함께 덮는 가로 두 개의 묶음이 생겨요. 한 줄만 가로로 뻗으면 옆의 칸을 완전히 덮을 수 없기 때문이에요. 따라서 가로 묶음이 없으면 세로 도미노 네 개인 1가지예요. 묶음이 하나라면 연속된 두 열의 시작 위치가 1,2,3열인 3가지예요. 묶음이 두 개라면 1~2열과 3~4열을 덮는 1가지예요. 합은 5가지예요.

두 번째 풀이는 맨 왼쪽 열에서 시작해요. 세로 도미노를 놓으면 남은 2×3판을 덮는 경우가 3가지예요. 가로 도미노 두 개를 놓으면 남은 2×2판을 덮는 경우가 2가지예요. 그래서 3+2=5입니다. 일반적으로 2×n판의 수를 Tₙ이라 할 때 Tₙ=Tₙ₋₁+Tₙ₋₂라는 관계도 얻어요. 빈 판은 아무것도 놓지 않는 1가지로 보아 T₀=1, T₁=1입니다.

교사 질문은 ‘첫 풀이에서 가로 도미노 수 대신 가로 묶음 수를 센 이유가 무엇인가’입니다. 개별 조각을 무작정 고르면 서로 겹치는 선택까지 세기 쉬워요. 완성된 배치를 빠짐없이 한 분류에 넣을 수 있는 단위를 고르는 일이 계산보다 먼저예요.

T0=T1=1,Tn=Tn−1+Tn−2(n≥2)T_0=T_1=1,\quad T_n=T_{n-1}+T_{n-2}\quad(n\ge2)
T4=1+3+1=3+2=5T_4=1+3+1=3+2=5

착안한 공개 원문: Deconstructing a Lesson Activity – Part 1. 원문의 수업 관점으로 새 문항을 구성했어요.

이 글 공유하기

개인정보 및 방문 통계 안내