d라이브러리

# 김종락 서강대학교 수학과 교수는 포스텍 수학과를 졸업하고, 서울대학교에서 석사 학위, 미국 일리노이주립대학교 시카고캠퍼스에서 박사 학위를 받았습니다. 주요 연구 분야는 부호론과 암호론, 산업수학, 인공지능입니다. 2004년 캐나다 조합론연구소에서 주는 커크만 메달을 한국인 최초로 받았습니다. 2016년부터 대한수학회 수학문화 앰배서더로 활동 중이며, ‘감성수학레드’라는 스타트업을 운영하고 있습니다.

오늘 소개할 ‘콰트레인먼트’를 즐기려면 딱 한 가지만 기억하세요. 앞면이 보이는 카드를 뒤집으면 뒷면이고 이걸 다시 뒤집으면 앞면이라는 사실만요. 단, 원하는 카드만 뒤집을 수 없다는 게 함정입니다!

‘콰트레인먼트’는 ‘4행시’라는 뜻이에요. 이런 이름이 붙은 이유는 콰트레인먼트가 가로세로 4칸씩 총 16칸으로 이뤄진 사각형 보드 위에서 하는 게임이기 때문입니다. 콰트레인먼트는 1984년 미국의 소프트웨어공학자 숀 퍼켓이 ‘계산!’이라는 잡지에 처음 소개하면서 유명해졌고, 1988년에 미국 데이턴대학교 수학과 교수인 톰 간트너가 수학적으로 분석해 해법을 찾아냈어요.

콰트레인먼트를 즐기려면 우선 16칸 보드 두 개가 필요합니다. 두 보드 중 하나를 ‘출발보드’, 다른 하나를 ‘도착보드’라고 해요. 두 보드의 빈칸 중 일부에 ×가 있는데, 게임의 목표는 시작보드에 있는 ×의 위치를 도착보드에 있는 ×의 위치와 똑같이 만드는 겁니다. ×와 빈칸은 동전의 앞뒷면과 같아서 ×를 뒤집으면 빈칸이고, 빈칸을 뒤집으면 ×입니다.

한 칸씩 골라서 뒤집을 수 있으면 누구나 쉽게 게임을 끝낼 수 있겠지만, 한 가지 조건이 있습니다. ×를 뒤집을 때는 미리 정해둔 세 가지 모양에 맞춰 각 모양에 속한 칸을 함께 뒤집어야 합니다. 16칸 중 어떤 칸을 고르냐에 따라 모양이 다르니 아래 그림을 보고 세 가지 모양이 무엇인지 확인해 보세요.

규칙은 간단하지만, 이 규칙 때문에 게임이 무척 어렵습니다. 내가 선택한 칸뿐 아니라 인접한 칸까지 한 번에 바뀌기 때문에 ×와 빈칸이 원하는 곳에 있도록 만들기가 쉽지 않거든요. 바닥보다 큰 카펫을 바닥에 딱 맞추려고 하는 것처럼, 한 곳을 맞추면 다른 한 곳이 맞지 않는 경우가 많이 생깁니다. 과연 도착보드로 만들 수 있는 방법이 있긴 있는 걸까요?

수학으로 나타낸 콰트레인먼트

시작보드를 도착보드로 만드는 방법을 찾기 전에 도착보드로 만드는 방법이 있는지부터 알아내야 합니다. 방법이 없다면 아무리 뒤집어봤자 밑 빠진 독에 물 붓기니까요. 방법이 있는지 증명하려면 먼저 콰트레인먼트를 수로 나타내야 합니다. 증명을 간단하게 하기 위해 16칸 보드가 아닌 가로세로 3칸씩 총 9칸이 있는 보드를 가지고 해볼게요.

먼저 보드의 칸 수가 줄었으니 규칙을 조금 바꾸겠습니다. 아래 그림처럼 구석에 있는 칸을 선택한 경우 인접한 2칸만 함께 뒤집고(❶), 변에 있는 칸을 선택하면 선택한 칸과 인접한 칸까지 모두 4칸을 뒤집습니다(❷). 정중앙에 있는 칸을 선택한 경우는 그대로 인접한 칸까지 5칸을 뒤집습니다(❸).

첫 번째 할 일은 시작보드와 도착보드에 있는 빈칸과 ×를 아래 그림처럼 각각 0과 1로 나타내는 겁니다. 칸을 ‘뒤집는 것’은 각 칸에 쓰인 수에 1을 ‘더하는 것’으로 나타낼 거예요. 이렇게 나타내려면 조금 독특한 덧셈이 필요합니다.

이유가 뭘까요? 빈칸을 뒤집는 건 0에 1을 더하는 거니까 0+1=1 이어서 ×가 됩니다. ×를 뒤집었을 때는 빈칸을 나타내는 0이 나와야 하는데, 수로 나타내면 1+1=2가 돼서 0이 나오지 않으므로 규칙에 맞지 않지요.

이 문제를 해결하는 방법은 0과 1을 이진수처럼 생각해서 1+1이 0이 된다고 생각하는 거예요. 이진수 1(2)에 1(2)을 더하면 1(2)+1(2)=10(2)이 되는데 합이 2가 되면 자릿수가 올라가고 0만 남는 것처럼요. 각 칸을 0과 1로 나타냈으면 구석, 변, 정중앙에 있는 칸을 선택해 뒤집는 9가지 경우를 시작, 도착보드와 마찬가지로 숫자가 적힌 ‘숫자 보드’로 나타낼 겁니다. 모양에 해당하는 칸에는 1을, 나머지 칸에는 0을 적어 보드로 만들면, 모양에 맞게 뒤집는 걸 숫자 보드를 더하는 걸로 나타낼 수 있습니다.

예를 들어 앞에 나온 시작보드의 첫 번째 칸을 선택했다고 합시다. 이 모양에 해당하는 보드는 오른쪽에 있는 M1입니다. 이제 M1과 시작보드의 같은 위치에 있는 숫자끼리 더하면 실제로 모양에 맞게 뒤집은 상태가 됩니다.

렬이 알려주는 해법!

이렇게 시작보드와 도착보드, 뒤집는 9가지 경우를 모두 숫자 보드로 나타낸 뒤 행렬의 덧셈을 이용하면 시작보드를 도착보드로 만드는 방법이 있음을 알 수 있을 뿐 아니라 구체적인 방법도 찾을 수 있습니다. 행렬은 숫자를 줄에 맞춰 나열한 것으로, 행렬을 더하는 건 두 행렬의 같은 위치에 있는 숫자를 더한다는 뜻이에요. 두 행렬을 더하려면 가로세로에 있는 숫자의 개수가 반드시 같아야 하지요.

편의상 앞에서 숫자로 나타낸 시작보드를 A, 도착보드를 B라고 합시다. 시작보드를 뒤집는 건 M1~M9 중 일부를 반복해서 더한다는 거예요. 행렬의 상수배를 이용하면 이 과정을 식으로 나타낼 수 있습니다. 만약 시작보드(A)를 첫 번째 모양(M1)에 맞춰 c1번 뒤집었으면 A+c1M1으로 나타낼 수 있어요. 결국 시작보드를 뒤집어서 도착보드로 만들 수 있으려면 A+c1M1+c2M2+…+c9M9=B가 되는 c1~c9이 있다는 뜻이에요. 이제 A와 B의 각 칸에 적힌 9개 숫자를 기준으로 써보면 아래와 같은 식을 얻을 수 있어요.

위 식을 만족하는 c1~c9을 모두 구해야 하기 때문에 복잡해 보일 거예요. 그런데 M1~M9은 모두 두 번 더하면 더하지 않은 것과 마찬가지니까 c1~c9은 0 또는 1만 될 수 있다는 사실을 기억하세요. 이 사실을 알면 위 식을 만족하는 c1~c9 값을 쉽게 찾을 수 있어요.

먼저 c1, c2, c3에 0 또는 1을 대입해 보세요. 각 값이 0 또는 1이 되는 경우는 총 8가지가 있는데, 각 경우에 나머지 값인 c4~c9의 값이 위 식을 다 만족하는지 검토하면 모든 값을 찾을 수 있지요. 이런 식으로 해보면 c1=0, c2=0, c3=1, c4=1, c5=0, c6=0, c7=1, c8=0, c9=0임을 알 수 있습니다. 즉, 어떤 모양에 맞춰 몇 번 뒤집어야 도착보드로 만들 수 있는지 알 수 있는 거지요.

16칸 보드에서 게임을 할 때도 비슷한 방법으로 해법을 찾아낼 수 있습니다. 뒤집는 모양이 16가지라 계산이 더 복잡하지만, 그래도 무작정 뒤집어 보는 것보다는 낫겠죠?