"파트너의 옷 색깔은?" 표를 이용한 분석

우선 다음과 같이 표를 그리자.

 
 목표는 우리가 그린 표를 전부 O와 X로 알맞게 채우는 것이다.

알다싶이, 한 사람이 동시에 다른 두 이성과 짝이 될 수 없으므로 O표는 한 행(行) 당 하나, 또 한 열(列) 당 하나이다. 

   따라서,
 1. 어떤 칸이 O라면, 그 칸의 나머지 행과 나머지 열은 모두 X다.
 2. 어떤 행에서/어떤 열에서 한 칸을 제외하고 모두 X라면, 남은 빈 칸은 O다.

 표를 이용해 푸는 방법은 첫째로, 문제에서 주어진 정보를 표에 기재하고, 둘째로, 위의 두 추론법칙을 이용하여 연쇄적으로 남은 빈 칸들을 채워 나가는 것이다.
 
 
주어진 정보는 다음과 같이 둘이었다

 1. 똑같은 색의 옷을 입은 쌍은 없다.
 2. 노란색 옷의 남자와 초록색 옷의 여자는 서로 파트너가 아니다.

이것을 표에 적으면 다음과 같다.

 1번 조건은 주대각선(왼쪽 위에서 오른쪽 아래로 난 대각선)이 모두 X임을 말해주고, 2번 조건은 왼쪽 아래칸이 X임을 말해주고 있다.
그러면, 추론규칙 2에 의해 왼쪽 중간 칸과 중간 아래 칸을 O할 수 있다.

그리고나면, 추론규칙 1에 의해 중간 위칸과 오른쪽 중간 칸을 X로 적는다.

이제 남은 칸은 자연스레 O가 된다. (추론규칙 2에 의해)

 이것이 완성된 표이다. 문제에서 원하는 노랑색 옷을 입은 여자의 파트너는 완성된 표에서 알 수 있듯이 초록색 옷을 입은 남자가 된다. 따라서 답은 초록색이다.


 ...


 여기서부터는 좀더 수학적으로 접근하겠다. 문제의 표를 수학적으로 표기하려면 어떻게 해야 할까? 답은 행렬(行列, matrix)이다. O를 숫자 1로, X를 숫자 0으로 해석하고 표를 3×3행렬로 생각하자.

 O표는 한 행(行) 당 하나, 또 한 열(列) 당 하나라는 가정만 가지고 다른 조건없이 만들수 있는 행렬의 경우의 수를 3!=6개이다.

 ( 참고로 위의 여섯개의 행렬들은 3×3행렬의 Permutation matrix들이면서, 기본행렬(Elementary matrix)들이고, 동시에 S3 (Symmetric Group of order 3), 혹은 D3 (Dihedral Group of order 3) 군이다. )

 어떤 쌍이 똑같은 옷을 입었다면 주대각선의 어느 한 곳에 1이 있을 것이다. 조건 1은 이의 부정이므로, 주대각선이 모두 0인 행렬을 찾자. 찾으면 모두 2개가 될 것이다.

 그림에서 왼쪽 행렬이 우리가 찾은 답이다. 그렇다면 우리의 답과 오른쪽에 있는 행렬은 무슨 관계란 말인가? 어떻게 서로대칭이라고 말 할 수 있단 말인가? 

 구조적으로 보면, 오른쪽 행렬을 주대각선을 중심으로 뒤집으면 왼쪽 행렬이 됨을 알 수 있다. 이는 이 행렬이 다른 것의 전치행렬(Transpose matrix)이라는 것을 말한다.

 
 또한, 두 행렬을 곱해보면 주대각선만 모두 1인 단위행렬(Identity matrix)가 된다. 따라서 앞의 행렬은 다른 것의 역행렬(Inverse matrix)이 된다.

 이렇게 두 행렬은 서로에게 transpoxe matrix이자 Inverse matrix이므로 , 참으로 뗄래야 뗄 수 없는 깊고도 아름다운 관계임이 분명하다.
( 참고로 위와같이 Inverse가 Transpose이기도 한 행렬을 직교행렬(Orthogamal matrix)이라 한다. 모든 Permutation matrix는 Orthogomal matrix이다.)