1995년에 나온 퍼즐이지만, 선형대수로 풀 수 있어요. 버튼을 누르면 그 칸과 위·아래·왼쪽·오른쪽 칸의 불이 반대로 바뀌어요. 목표는 모든 불을 끄는 거예요. 그런데 어떤 배치는 아무리 눌러도 풀리지 않아요. 그 까닭을 벡터공간과 차원으로 알아보자.
먼저 ‘새 게임’으로 몇 판 풀어 보세요. 그다음 ‘풀 수 없는 배치’에 도전해 보세요. 규칙만으로 풀기 어렵다면 2번에서 방정식으로 바꾸어 볼게요.
각 칸을 꺼짐(0)과 켜짐(1)으로 적으면 보드 전체를 성분 25개인 벡터로 나타낼 수 있어요. 불을 두 번 바꾸면 원래 상태로 돌아오므로 이 계산에서는 $1+1=0$이에요. 0과 1만 쓰고 덧셈과 곱셈의 결과를 2로 나눈 나머지로 정하는 수 체계를 $\mathbb{F}_2$라고 해요. 따라서 보드는 $\mathbb{F}_2^{25}$의 벡터예요.
다음 세 가지를 관찰하면 퍼즐을 연립방정식으로 바꿀 수 있어요.
$j$번 버튼을 누르면 보드 벡터에 고정된 패턴 벡터 $a_j$(그 칸과 이웃 칸)를 더해요. 각 성분은 2로 나눈 나머지만 남겨요.
누르는 순서를 바꾸어도 결과가 같고 $a_j+a_j=0$이에요. 따라서 한 버튼은 많아도 한 번만 누르면 돼요. 누를 버튼은 $\mathbb{F}_2^{25}$의 벡터 $x$로 기록해요.
초기 배치를 $b$라고 하면 버튼을 누른 뒤의 배치는 $b+Ax$예요. 모두 끄려면 $b+Ax=0$, 즉 $Ax=b$를 풀면 돼요. 모든 계산은 2로 나눈 나머지로 해요.
퍼즐을 ‘벡터공간 + 연립방정식’으로 나타냈어요. 이제 풀 수 없는 배치가 생기는 까닭도 설명할 수 있어요.
‘가우스 소거’를 누르면 현재 1번 보드의 배치로 $Ax=b$를 계산해요.
소거를 끝내면 계수행렬 $A$의 랭크는 25가 아니라 23이에요. 즉 25개의 버튼 패턴 가운데 서로 선형 독립인 것은 23개뿐이에요. 도달 가능한 배치들은 $\mathbb{F}_2^{25}$ 전체가 아니라 차원 23인 부분공간을 이뤄요.
가능한 배치 $2^{25}$개 중 풀 수 있는 배치는 $2^{23}$개, 정확히 4분의 1이에요. 풀 수 없는 배치는 그 부분공간 밖에 있으므로 버튼을 어떤 순서로 눌러도 도달할 수 없어요. 차원을 세면 풀 수 있는 배치의 비율도 알 수 있어요.
랭크가 23이므로 영공간의 차원은 $25-23=2$예요. 따라서 모두 눌러도 보드가 그대로인 서로 독립적인 누름 조합이 두 개 있어요. 아래 두 패턴의 칸을 모두 눌러도 보드는 변하지 않아요. 1번 보드에서 ‘보드에 적용’을 눌러 확인해 보세요.
$\mathbb{F}_2^n$의 부분공간을 알맞게 설계하면 일부 비트가 훼손돼도 오류를 찾고 고칠 수 있는데, 이를 해밍(1950)의 오류 정정 부호라고 해요. QR코드와 통신 시스템도 유한체(정해진 개수의 수로 계산하는 수 체계) 위의 선형대수를 이용해 오류를 찾고 고쳐요. 쓰는 수 체계는 다를 수 있지만 Lights Out과 계산 구조가 이어져요.
// n×n Lights Out의 랭크를 세어 풀리는 배치의 비율을 구해 보세요.
const n = 5; // 보드 크기를 4, 6, 7로 바꿔 보세요.
const N = n * n;
// 버튼 j의 효과 패턴 = 행렬 A의 j열
const A = Array.from({length: N}, (_, i) => Array.from({length: N}, (_, j) => {
const [ri, ci] = [Math.floor(i / n), i % n];
const [rj, cj] = [Math.floor(j / n), j % n];
const d = Math.abs(ri - rj) + Math.abs(ci - cj);
return d <= 1 ? 1 : 0; // ★ 이웃 규칙을 바꾸어 변형 게임을 만들어 보세요.
}));
// mod 2 가우스 소거로 rank 계산
let rank = 0;
for (let col = 0; col < N && rank < N; col++) {
let piv = -1;
for (let r = rank; r < N; r++) if (A[r][col]) { piv = r; break; }
if (piv < 0) continue;
[A[rank], A[piv]] = [A[piv], A[rank]];
for (let r = 0; r < N; r++)
if (r !== rank && A[r][col])
for (let c = 0; c < N; c++) A[r][c] ^= A[rank][c];
rank++;
}
console.log(`${n}×${n}: rank = ${rank} / ${N}`);
console.log(`풀리는 배치 비율 = 1/${Math.pow(2, N - rank)}`);