1995년에 출시된 이 퍼즐은 선형대수로 분석할 수 있다. 규칙은 하나이다. 누르면 자신과 상하좌우가 반전된다. 목표는 모든 불을 끄는 것이다. 일부 배치는 어떤 순서로 버튼을 눌러도 모든 불을 끌 수 없다. 풀 수 없는 배치가 생기는 이유를 벡터공간과 차원으로 설명해 보자.
먼저 "새 게임"으로 몇 판 풀어 보자. 그다음 "함정 배치"에 시간 제한 없이 도전해 보자. 포기하고 싶어질 때 2번으로 내려올 것.
각 칸은 꺼짐(0) 또는 켜짐(1) — 보드 전체는 0과 1이 25개 늘어선 벡터다. 그런데 이 세계의 덧셈은 "반전": $1+1 = 0$. 이것이 Unit 1 공리 실험실에서 본 두 원소만 가진 체 $\mathbb{F}_2$ 이고, 보드는 $\mathbb{F}_2^{25}$ 의 벡터다.
세 가지 관찰로 퍼즐을 연립방정식으로 바꿀 수 있다.
$j$번 버튼을 누르면 보드에 고정된 패턴 벡터 $a_j$(자신+이웃)가 더해진다(mod 2).
덧셈은 교환·결합이 성립하고 $a_j + a_j = 0$. 그러므로 해는 "각 버튼을 누른다/안 누른다"의 선택, 즉 $\mathbb{F}_2^{25}$ 의 벡터 $x$ 하나다.
초기 배치 $b$를 전부 끄려면: $Ax = b$ — Unit 2의 가우스 소거법이 그대로 적용된다. 단, 산수는 전부 mod 2.
퍼즐 하나가 "벡터공간 + 연립방정식"으로 완전히 번역되었다. 이제 풀 수 없는 배치가 생기는 이유를 설명할 수 있다.
$Ax=b$를 mod 2 가우스 소거로 풀어 보자. 현재 1번 보드의 배치가 그대로 들어간다.
소거를 끝내면 계수행렬 $A$의 계수(rank)는 25가 아니라 23이다. 즉 25개의 버튼 패턴 벡터 중 독립인 것은 23개뿐 — 도달 가능한 배치들(가해공간)은 $\mathbb{F}_2^{25}$ 전체가 아니라 차원 23짜리 부분공간이다.
가능한 배치 $2^{25}$개 중 풀리는 것은 $2^{23}$개 — 정확히 4분의 1. 함정 배치는 그 부분공간 밖에 있었을 뿐이다. 아무리 눌러도 안 되는 게 당연했다 — 차원을 세면 풀 수 있는 배치의 비율을 알 수 있다.
랭크가 2 모자란 이유: 눌러도 보드가 그대로인 누름 조합(영공간의 벡터)이 존재하기 때문이다. 아래 두 패턴이 그 주인공 — 이 칸들을 전부 누르면 보드는 변하지 않는다! 1번 보드에서 직접 시험해 보자. 버튼을 누르면 자동으로 입력된다.
$\mathbb{F}_2^n$ 의 부분공간을 일부러 잘 설계하면 "훼손돼도 복구되는 데이터"가 된다 — 해밍(1950)의 오류 정정 부호. QR코드가 낙서로 더럽혀져도 읽히고, 심우주 탐사선의 사진이 수십억 km를 건너 무사히 도착하는 이유다. Lights Out을 부순 바로 그 수학이 디지털 문명의 안전망이다. (수행평가 1 소재 — Unit 2 탐구실의 Hamming 1950 참고.)
// n×n Lights Out의 rank를 세어 "풀리는 배치의 비율"을 구한다
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; // ★ 이웃 규칙 (d <= 1 을 바꿔 변형 게임!)
}));
// 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)}`);