보드게임 수학적 원리 - bodeugeim suhagjeog wonli

대학원에서 '조합론'을 공부하면서 게임속에서 발전한 과목이 바로 이 조합론이지 않나라는 생각을 했다. 우리가 흔히 즐겨하는 보드게임 속에는 수학의 원리가 숨어있었다.

​

1) 도블

도블은 55장의 동그란 카드로 이뤄져 있다. 카드마다 서로 다른 8개의 그림이 있는데 그림의 종류는 눈송이, 고양이, 하트, 거미줄, 물음표, 이글루 등 총 57가지이다. (사실 57개의 그림으로 총 57장의 카드를 만들 수 있는데, 게임회사에서는 55장의 카드를 만들었다.)

도블의 놀라운 특징은 어떤 카드 두 개를 비교해도 꼭 한 쌍의 같은 그림이 있다는 것이다. 그렇다면 그렇게 만들 수 있는 원리는 무엇일까?

​

설명을 위해 좀 간단한 문제를 생각해 보자. 7명의 사람이 있다. 이 사람들로 팀원이 3명인 여러 개의 팀을 만들려고 한다. 어떤 두 팀을 택해도 꼭 한 명만 두 팀에 동시에 속하도록 해야 한다. 그러면 몇 개의 팀이 필요할까?

​

7명의 사람은 집합 {1,2,3,4,5,6,7}이라 두자.

팀을 {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6} 이라 두면 어느 두 집합도 한 원소만 공통으로 가지게 된다. 이를 그림으로 표현하면 아래와 같다.

이 때 사람은 점이고, 팀은 선분이다. 선분위의 점들이 팀을 이루는 원소들이다. 또한 어느 두 팀이라도 한 명만 동시에 속하여야 하므로 어느 두선분이라서 한 점에서 만난다. 따라서 정답은 7개이다. 이처럼 생긴 그림은 파노평면(Fano Plane)이라 한다.

파노 평면을 일반화한 이론이 n차 사영 평면(projective plane of order n)이다. 이 때 order는 (한 선분안의 점의 수) -1이라 생각하면 된다. 이는 수학 증명 과정에서 계산의 편리성을 위해 약속한 것이다. 파노 평면은 2차 사영 평면이라고 할 수 있다. 도블에 적용하면 한 선분 안의 점의 수 즉, 한 카드안의 그림의 수가 8이므로 order는 7이다. 도블은 order가 7인 7차 사영평면이다.

projective plane은 점의 총개수와 선의 총 개수가 같다는 성질이 있고, 그 공식은

n*(n+1)+1이다. (이 공식을 유도하기 위하여는 projective plane 이 나온 배경인 combinational designs의 개념이 필요하다.) 따라서 7차 사영 평면에서 n=7을 대입하면 모든 점의 개수와 모든 선의 개수는 57이다. 그래서 도블은 총 57개의 그림이 있고, 도블은 수학 원리대로라면 57개의 카드가 필요하다. 그런데 어떤 이유인지 도블 제작사는 두 개의 카드를 생략해 버렸다.

사실 57개의 그림으로 총 57장의 카드를 만들 수 있는데, 도블게임회사에서는 55장의 카드를 만들었다. 이유가 뭘까 미스터리하다. 게임의 용이성이라는 측면에서 생각해 봐도 55-1=54=2*3*3*3 어서 2명, 3명, 6명이 함께 즐길 수 있는 반면에 57-1=56=2*2*2*7 2명, 4명, 7명, 8명이 즐길 수 있다. (도블은 2~8인용 게임이다.) 그렇다면 57장이 더 용이하다.

​

파노 평면을 이용해 카드의 그림 수가 3개인 도블 게임을 만들어 봤다. 어느 두 카드를 비교해도 한 그림만 겹치게 된다.

​

​

2) 세트 게임(SET Game)

​

게임은 4가지 유형의 81개의 카드로 이뤄져 있는데 각 유형별로 3가지의 특징이 있다. 개수(1, 2, 3), 모양(다이아몬드, 물결, 타원), 음영(채워진 것, 빗금, 채워지지 않은 것), 그리고 색(빨간색, 녹색, 보라색) 등이 각각 다른 것이다. 이에 따라 모두 81개의 카드가 생성된다.

​

게임의 룰은 간단하다. 딜러가 잘 섞어 놓은 81개의 카드에서 12개를 늘어 놓는다. 세 장의 카드가 4개의 각 유형에 대하여 모두 같은 특징을 갖거나 또는 서로 다른 특징을 가질 때, 이 세 카드를 ‘세트’라고 한다.

​

여기에 숨겨진 수학은 도블과 비슷하다. 아무거나 카드 두 장을 선택하면 세트를 만족시키는 나머지 한 장의 카드가 어딘가에 있다. 이것은‘ 81차 스타이너 삼중계(Steiner triple system of order 81)’에 해당한다.

​

Steiner triple system을 알아보기 전에 Steiner triple system과 projective plane의 밑바탕의 개념인 (b, v, r, k, i)-Design을 알아보자. 사실 i 대신에 기호 람다를 사용해야 하지만 후에 이 람다를 index라 하므로 여기에서는 i라 하겠다.

(b, v, r, k, i)-Design 은 balanced incomplete block design이라고 불리기도 한다.

(b, v, r, k, i)-Design 아래의 5개의 문장을 만족한다.

​

1) 전체 집합은 v개의 원소로 이루어져 있다. 이 때 전체 집합을 variety라 하며, v는 variety의 약자이다.

2) 전체 집합 중 부분집합은 b개가 있다. 이 때 부분집합을 block이라 하며 b는 block의 약자이다.

3) 전체 block은 모두 k개의 원소(variety)로 이루어져 있다.

4) 모든 각각의 variety는 전체 block에서 똑같이 r번 나타난다.

5) 어느 두 개의 variety도 똑같이 i개의 block에서 나타난다.

​

대표적인 예로는 파노 평면이 있다. 파노평면은 (7,7,3,3,1)-design이다.

1) 집합 (variety) {1,2,3,4,5,6,7}이 있다. v=7

2) block을 {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6} 이다. (b=7)

3) 모든 block에는 3개의 variety가 있다. (k=3)

4) 각각의 variety는 3번씩 나온다. (r=3)

5) 어느 두 개의 variety도 똑같이 1개의 block에서 나타난다. (i=1)

'어느 두 집합도 한 원소만 공통으로 가지게 된다.' 도블의 성질과는 차이가 있다.

5)를 해설하면 이 그림에서 어느 두 점을 지나는 선분은 하나만 존재한다는 뜻이다.

​

이 분야에서 유명한 문제는 커크맨의 여학생 문제(kirkman's schoolgirl problem)이 있다.

​

열다섯 명의 여학생들이 연달아 칠일 동안 세 명씩 산책을 한다. 같은 학생과 두 번 이상 산책하지 않게 산책 일정을 정하라.

​

1) 열 다섯 명의 여학생을 대상으로 하므로, variety는 15이다. (v=15)

{01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15}

3) 세 명씩 산책을 하므로 한 block에는 3개의 variety가 있다. (k=3)

2) 하 루에 열 다섯명이 세 명씩 산책을 하므로, 하루에 block이 5개가 있으며, 일주일동안 산책을 하므로, 총 block의 개수는 35개 이다.

5) 같은 학생과 두 번 이상 산책하지 않게 산책 일정을 정하라라는 뜻은 이 때 한 block에서 같이 나온 두 개의 variety는 전체에서 딱 한 번만 나온다는 뜻이며, 즉, 다른 집합에서는 나오지 않는다는 뜻이다. (i=1)

​

이 해를 직접 구해서 표로 만들어 보면 아래와 같다.

​

열다섯 여학생들에게 01부터 15 까지 번호를 매기면, 아래의 배열은 하나의 해가 된다.

이와 동형인 해는 7개의 해가 더 있다고 한다.

​

참고로 4)의 r의 값은 b, v, k의 값이 정해지면 저절로 정해지는 값이다. bk=rv 라는 공식을 가지며 이 문제에서는 35*3=15*7이므로 r=7이다. 모든 번호가 7번씩 나왔음을 확인할 수 있다.

​

이 때, (b, v, r, k, i)-Design 에서 k=3인 경우를 Steiner triple system이라 하며, i는 index라 한다.

​

세트카드에 적용해보자.

1) 4가지 속성(색, 음영, 모양, 개수)으로 각각 3개의 성질을 가지고 있으므로 3^4=81개의 모양이 있다. v= 81 (한 장의 카드에 그림이 하나씩 있으므로 카드가 variety이다. )

3) 한 set에는 3장의 카드를 선택하므로, set는 block이고 k=3 이다.

5) 서로 다른 두 장을 선택하면, set를 만족하는 나머지 한 장의 카드는 이미 정해져 있다. 즉, 서로 다른 두 장이 들어가는 block은 1개 뿐이다. 즉, i=1이다.

세트카드는 k=3 이므로 Steiner triple system에 해당한다.

​

(그러나 set카드에서는 r값과 b의 값이 정확히 나올 수 없다. 카드게임 자체가 set을 만들면 그 카드를 게임 중에 없애기 때문인데, 그러면 r=1의 값을 가진다. 그렇게 되면 block을 만들 수 없는 카드들이 마지막에 6장 또는 9장 남게 된다. )

​

https://news.joins.com/article/18613173