척척박사 연구소

척척박사 연구소과학이야기제목별로 보기모두의 수학

모두의 수학

우리 생활 속 수학 원리를 알아 봅시다.

그 어떤 ‘행’과 ‘열’에도 단 2개의 칸만 색칠하는 방법은 모두 몇 가지일까?

로직

 

‘2칸씩 채우는 네모로직’ 게임*

 

가로×세로가 N×N인 바둑판에서
그 어떤 ‘행’과 ‘열’에도 단 2개의 칸만 색칠하는 방법은 모두 몇 가지인지 찾아보자!


* ‘2칸씩 채우는 네모로직’ 게임의 정식 명칭은 ‘No 3 in Line Problem’이다. 1917년 Dudeney에 의해 처음 소개된 문제로, N X N개의 바둑판에서 모든 행과 열에 단 2개의 칸만 색칠하는 방법을 찾는 문제이다.

 

 

 

 


❙3×3 네모로직 게임

 

게임규칙은 간단하다.
예로, 크기가 3×3인 바둑판으로 ‘2칸씩 채우는 네모로직’ 게임을 해보면 아래와 같다.

 

 

네모로직1

 

 

보는 바와 같이 한가지의 정답을 찾는 것은 그리 어렵지 않다.
하지만 정답이 한 개만 있는 것은 아니다.

 

그렇다면, 모두 몇 가지 방법을 완성할 수 있을까?

 


【정답】 6가지

 

3*3로직 정답

 

 

 

 

 

 


❙4×4 빙고 게임

 

이번에는 크기가 4×4인 ‘2칸씩 채우는 네모로직’ 게임을 해보자. 모두 몇 가지 종류의 방법으로 완성할 수 있을까?

 

 

【정답】90가지

 

4*4로직 정답


크기가 3×3 바둑판의 풀이 개수는 불과 6개인데 반하여, 4×4 바둑판의 풀이 개수는 무려 90개로 늘어난다.

 

어떻게 이 많은 개수를 다 셀 수 있었을까?

 

이 문제는 언뜻 생각하면 ‘경우의 수(순열·조합)’로 계산할 수 있을 듯하지만, 실제는 그렇지 못하다. 가로와 세로가 모두 2칸씩만 유지되어야 하기에 가로나 세로 한 측면으로만 생각할 수 없기 때문이다. 따라서 아래와 같이 방정식으로 풀어야 한다. 
 

로직2

 

 

크기가 4×4인 바둑판의 각 성분을 a11∼a44라고 하면, 이 값은 0일 때 흰색, 1일 때 회색으로 대응시킬 수 있다. 즉, aij 는 0과 1만을 가질 수 있다.

 

이제, 각 행의 색을 2개씩만 칠할 수 있다는 조건을 식으로 세워보면 아래와 같다.

 

a11+ a12+ a13+ a14= 2
a21+ a22+ a23+ a24= 2
a31+ a32+ a33+ a34= 2
a41+ a42+ a43+ a44= 2

 

 

다음, 각 열의 색을 2개씩만 칠할 수 있다는 조건을 식으로 세워보면 아래와 같다.

 

a11 + a21 + a31 + a41 = 2
a12 + a22 + a32 + a42 = 2
a13 + a23 + a33 + a43 = 2
a14 + a24 + a34 + a44 = 2

 


이렇게 16개의 미지수(a11∼a44)에 대하여, 총 8개의 연립방정식을 세울 수 있다. 하지만 이처럼 복잡한 연립방정식을 손으로 풀기에는 어려움이 따른다. 하여, 공학용 소프트웨어를 이용하여 풀어보면 아래와 같이 90개의 해를 모두 찾을 수 있다.

 

4*4 해설

 


위의 결과에서 「a[1,2]→0」 은 「a12」에 해당하는 위치가 흰색, 「a[1,2]→1」 은 「a12」에 해당하는 위치가 회색을 의미한다. 이를 크기가4×4인 바둑판에 옮겨 90가지 종류의 해법을 모두 찾은 것이다.

 

4x4


이처럼 크기가 N×N인 바둑판에 게임을 할 수 있는 경우의 수는 N의 크기가 커질수록 더욱 많아진다.

 

예로, 공학용 소프트웨어를 이용하여 풀어본, 바둑판의 크기가 5×5인 게임은 2,040가지의 해법이 존재하고, 6×6인 게임은 67,950가지의 해법이 존재하며,7×7인 게임은 무려 3,110,940가지의 해법이 존재한다. 특히, 7×7인 게임의 모든 해법을 찾아내는데 약 20분의 시간이 소요되었다. 따라서 일반 PC로 크기가 10×10이상인 게임의 모든 해법을 찾기는 무리다. 현재까지 컴퓨터를 이용하여 모든 해법을 찾아낸 바둑판의 크기는 52×52인 것으로 알려져 있다.

 

30*30


컴퓨터로 찾아낸 「3×3」 부터 「30×30」 까지 빙고 해법의 일부

 

 

 

[더 알아보기]

이 글에서 소개한 내용은 세계적으로 유명한 Mathematica 소프트웨어로 구현한 것이며, 이는 작가의 홈페이지 수학생각(http://www.mathought.com)의 수학실험실에서 Dynamic한 실험과 조작을 통하여 더욱 즐겁게 관찰할 수 있다. 단, 공개프로그램인 Wolfram CDF Player를 설치하고 데스크탑PC(혹은 노트북)의 Microsoft Internet Explore 환경에서 작동이 가능하다.  


[바로가기]
No 3 in Line Problem : 42×42까지의 해법 탐색


 

관련주제가 없습니다.
내과학상자담기  E-MAIL 프린트 RSS
관련 콘텐츠가 없습니다.

나도 한마디 1개의 댓글이 있습니다.

등록하기

목록


내 당근 보러가기

내 뱃지 보러가기

TOP