Marq's Website

Math

Solving that 5×5 light grid puzzle

Notes on notation

• =	"is equal to"
  ≠	"is not equal to"
  +	"plus", but not in the tradition sense
  ×	"times", but not in the tradition sense; it will be defined
  ()	"quantity", these enclose an operation to be done before those not enclosed

• For the most part, small letters are elements of matrices.
• For the most part, big letters are matrices.
• Order of operations proceed from left to right, regardless of which operations are performed; parentheses may used to clarify even when not necessary.

General notes

• For those of you familiar with algebra but not abstract algebra, some of the operations and properties here may seem strange or wrong. This is because I am using different number systems and defintions for operands. For example, the only cardinals used here are 0 and 1, and only symbolically at that. Thus 1 + 1 = 0 won't seem right, but remember that there is no 2. Similarly, A + A = Z and A + Z = A don't seem to agree, but they follow directly from 1 + 1 = 0. Good luck.

Definition of "button-status" (a₁, b₂, etc.)

• a1 = 0	button 1 of button-grid is either off or unpressed
  b2 = 1	button 2 of button-grid is either on or pressed

Nature of = for button-status

• a₁ = a₁
• a₁ = b₂ if and only if b₂ = a₁
• if a₁ = b₂ and b₂ = c₃ then a₁ = c₃

Definition of + for button-status

• 0 + 0 = 0
• 1 + 0 = 1
• 0 + 1 = 1
• 1 + 1 = 0

Nature of + for button-status

• a + 0 = a
• a + b = b + a
• (a + b) + c = a + (b + c)

Definition of "button-grid" (A, B, etc.)

• A =	a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a17 a18 a19 a20 a21 a22 a23 a24 a25

Nature of = for button-grid

• A = A
• A = B if and only if B = A
• if A = B and B = C then A = C

Definition of + for button-grid

• if C = A + B then

  • C =	a1+b1 a2+b2 a3+b3 a4+b4 a5+b5 a6+b6 a7+b7 a8+b8 a9+b9 a10+b10 a11+b11 a12+b12 a13+b13 a14+b14 a15+b15 a16+b16 a17+b17 a18+b18 a19+b19 a20+b20 a21+b21 a22+b22 a23+b23 a24+b24 a25+b25

Defintion of Z

• Z =	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Definition of E_n

Definition of M_n

Defintion of × for button-grid

• A × E_n = A + M_n
• A × (E_n1 + E_n2) = A + M_n1 + M_n2
• A × (E_n1 + E_n2 + …) = A + M_n1 + M_n2 + …

Nature of + and × for button-grid

• Nature of +
  • A + Z = A
  • A + A = Z
  • A + B = B + A
  • (A + B) + C = A + (B + C)
• Nature of ×
  • A × Z = A
  • Z × E_n = M_n
  • A × B ≠ B × A
• Nature of + and × mixed
  • (A × B) × C = A × (B + C)
  • (A × B) + (C × D) = (A + C) × (B + D)

Representation of the puzzle with our new algebra

• Let A be a puzzle; in this case a₁, a₂, etc. represent whether the buttons are on or off at the beginning of the game.
• Let B be a solution; in this case b₁, b₂, etc. represent whether the buttons are pressed or remain unpressed during the solution to the puzzle.
• Note that since 1 + 1 = 0, if a button is pressed an even number of times, the result is the same as if the button remains unpressed.
• Note that A × B = Z, I purposedly defined × as I did for this result.

Proof that repeating the solution on a solved grid will produce the original puzzle

• A × B = Z
• (A × B) × B = Z × B
• A × (B + B) = Z × B
• A × Z = Z × B
• A = Z × B

Reasoning to the method for solving the puzzle

• In order to obtain a solution for any puzzle, we can solve the following system of equations:
  • a₁ = b₁ + b₂ + b₆
  • a₂ = b₁ + b₂ + b₃ + b₇
  • a₃ = b₂ + b₃ + b₄ + b₈
  • a₄ = b₃ + b₄ + b₅ + b₉
  • a₅ = b₄ + b₅ + b₁₀
  • a₆ = b₁ + b₆ + b₇ + b₁₁
  • a₇ = b₂ + b₆ + b₇ + b₈ + b₁₂
  • a₈ = b₃ + b₇ + b₈ + b₉ + b₁₃
  • a₉ = b₄ + b₈ + b₉ + b₁₀ + b₁₄
  • a₁₀ = b₅ + b₉ + b₁₀ + b₁₅
  • a₁₁ = b₆ + b₁₁ + b₁₂ + b₁₆
  • a₁₂ = b₇ + b₁₁ + b₁₂ + b₁₃ + b₁₇
  • a₁₃ = b₈ + b₁₂ + b₁₃ + b₁₄ + b₁₈
  • a₁₄ = b₉ + b₁₃ + b₁₄ + b₁₅ + b₁₉
  • a₁₅ = b₁₀ + b₁₄ + b₁₅ + b₂₀
  • a₁₆ = b₁₁ + b₁₆ + b₁₇ + b₂₁
  • a₁₇ = b₁₂ + b₁₆ + b₁₇ + b₁₈ + b₂₂
  • a₁₈ = b₁₃ + b₁₇ + b₁₈ + b₁₉ + b₂₃
  • a₁₉ = b₁₄ + b₁₈ + b₁₉ + b₂₀ + b₂₄
  • a₂₀ = b₁₅ + b₁₉ + b₂₀ + b₂₅
  • a₂₁ = b₁₆ + b₂₁ + b₂₂
  • a₂₂ = b₁₇ + b₂₁ + b₂₂ + b₂₃
  • a₂₃ = b₁₈ + b₂₂ + b₂₃ + b₂₄
  • a₂₄ = b₁₉ + b₂₃ + b₂₄ + b₂₅
  • a₂₅ = b₂₀ + b₂₄ + b₂₅
• How would you like to solve this every time you wanted to solve a puzzle? No way! It's way too messy. However, we don't need it for every puzzle. We don't even need to solve it over and over again. If we solve it for b_n then we get the following:
  • b₁ = a₆ + a₁₁ + a₁₂ + a₁₆ + a₁₈ + a₂₂ + a₂₃ + a₂₄ + b₂₅
  • b₂ = a₇ + a₁₁ + a₁₂ + a₁₃ + a₁₉ + a₂₁ + a₂₂ + a₂₄ + a₂₅ + b₂₄
  • b₃ = a₂ + a₃ + a₆ + a₈ + a₉ + a₁₁ + a₁₂ + a₁₃ + a₁₅ + a₁₆ + a₁₇ + a₁₈ + a₁₉ + a₂₀ + a₂₁ + a₂₄ + a₂₅ + b₂₄ + b₂₅
  • b₄ = a₁ + a₂ + a₃ + a₇ + a₁₇ + a₂₁ + a₂₂ + a₂₃ + b₂₄
  • b₅ = a₁ + a₂ + a₈ + a₁₀ + a₁₁ + a₁₃ + a₁₅ + a₁₆ + a₂₂ + a₂₃ + a₂₅ + b₂₅
  • b₆ = a₁ + a₆ + a₇ + a₁₃ + a₁₆ + a₁₈ + a₁₉ + a₂₁ + a₂₃ + a₂₅ + b₂₄ + b₂₅
  • b₇ = a₃ + a₇ + a₈ + a₉ + a₁₁ + a₁₂ + a₁₅ + a₁₇ + a₂₀ + a₂₃ + a₂₄
  • b₈ = a₁ + a₃ + a₆ + a₈ + a₉ + a₁₅ + a₁₆ + a₁₈ + a₂₀ + a₂₁ + a₂₃ + b₂₄ + b₂₅
  • b₉ = a₃ + a₇ + a₈ + a₉ + a₁₁ + a₁₄ + a₁₅ + a₁₆ + a₁₉ + a₂₂ + a₂₃
  • b₁₀ = a₁ + a₆ + a₇ + a₁₁ + a₁₃ + a₁₅ + a₁₇ + a₁₈ + a₂₀ + a₂₃ + b₂₄ + b₂₅
  • b₁₁ = a₁ + a₃ + a₆ + a₈ + a₉ + a₁₃ + a₁₅ + a₁₇ + a₁₉ + a₂₀ + a₂₁ + a₂₂ + a₂₃ + a₂₅ + b₂₄
  • b₁₂ = a₁₇ + a₂₁ + a₂₂ + a₂₃ + b₂₄
  • b₁₃ = a₁ + a₂ + a₈ + a₁₁ + a₁₃ + a₁₄ + a₁₆ + a₂₀ + a₂₂ + a₂₃ + a₂₅
  • b₁₄ = a₁ + a₂ + a₃ + a₇ + a₉ + a₁₃ + a₁₄ + a₁₅ + a₁₉ + b₂₄
  • b₁₅ = a₂ + a₃ + a₆ + a₉ + a₁₁ + a₁₄ + a₁₅ + a₁₇ + a₁₈ + a₁₉ + a₂₀ + a₂₃ + a₂₅ + b₂₄
  • b₁₆ = a₃ + a₇ + a₈ + a₉ + a₁₁ + a₁₅ + a₁₆ + a₁₈ + a₂₀ + a₂₁ + a₂₃ + b₂₄ + b₂₅
  • b₁₇ = a₂ + a₆ + a₇ + a₈ + a₁₄ + a₁₆ + a₁₇ + a₁₉ + a₂₀ + a₂₂ + a₂₄
  • b₁₈ = a₁ + a₆ + a₇ + a₁₁ + a₁₃ + a₁₇ + a₁₈ + a₁₉ + a₂₃ + a₂₅ + b₂₄ + b₂₅
  • b₁₉ = a₂ + a₃ + a₆ + a₉ + a₁₁ + a₁₄ + a₁₅ + a₁₇ + a₁₈ + a₁₉ + a₂₃
  • b₂₀ = a₂₅ + b₂₄ + b₂₅
  • b₂₁ = a₁ + a₂ + a₈ + a₁₁ + a₁₃ + a₁₄ + a₁₆ + a₁₈ + a₂₀ + a₂₄ + a₂₅ + b₂₅
  • b₂₂ = a₁ + a₂ + a₃ + a₇ + a₉ + a₁₃ + a₁₄ + a₁₅ + a₂₃ + a₂₄ + a₂₅ + b₂₄
  • b₂₃ = a₂ + a₃ + a₆ + a₉ + a₁₁ + a₁₄ + a₁₅ + a₁₇ + a₁₈ + a₁₉ + a₂₃ + a₂₄ + b₂₄ + b₂₅
  • 0 = a₂ + a₃ + a₄ + a₆ + a₈ + a₁₀ + a₁₁ + a₁₂ + a₁₄ + a₁₅ + a₁₆ + a₁₈ + a₂₀ + a₂₂ + a₂₃ + a₂₄
  • 0 = a₁ + a₃ + a₅ + a₆ + a₈ + a₁₀ + a₁₆ + a₁₈ + a₂₀ + a₂₁ + a₂₃ + a₂₅
• First, notice that the last two lines don't include any b_n at all. This means that puzzles must conform to certain conditions in order to be solvable. Second, notice that some b_n are expressed in terms of an, b₂₄, and/or b₂₅. This means that we may choose our own values for b₂₄ and b₂₅ (pressed or unpressed) and thus solvable puzzles have 4 solutions each.
• If you are wondering how I got the system of equations: I noted that for any button which is off, the total number of buttons pressed in the solution which affect the button must be even. For any button which is on, the total pressed which affect the button must be odd. This is why I defined + and button-status as I did, eg. 1 + 1 = 0, on = pressed and off = unpressed.

Definition of P and Q

• P =	0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0

• Q =	1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1

• P + Q =

  1 1 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 1

Defintion of & for button-status

• 0 & 0 = 0
• 1 & 0 = 0
• 0 & 1 = 0
• 1 & 1 = 1

Definition of & for button-grid

• if C = A & B then

  • C =	a1&b1 a2&b2 a3&b3 a4&b4 a5&b5 a6&b6 a7&b7 a8&b8 a9&b9 a10&b10 a11&b11 a12&b12 a13&b13 a14&b14 a15&b15 a16&b16 a17&b17 a18&b18 a19&b19 a20&b20 a21&b21 a22&b22 a23&b23 a24&b24 a25&b25

Nature of & for button-grid

• A & A = A
• A & Z = Z
• A & B = B & A
• (A & B) & C = A & (B & C)
• A & (B + C) = (A & B) + (A & C)

Defintion of real() for button-grid

• real(A) = a₁ + a₂ + a₃ + a₄ + a₅ + a₆ + a₇ + a₈ + a₉ + a₁₀ + a₁₁ + a₁₂ + a₁₃ + a₁₄ + a₁₅ + a₁₆ + a₁₇ + a₁₈ + a₁₉ + a₂₀ + a₂₁ + a₂₂ + a₂₃ + a₂₄ + a₂₅

Defintion of abs() for button-grid

• For the purpose of this definition, + means what it does everyday arthmetic, ie. 1 + 1 = 2
  • abs(A) = a₁ + a₂ + a₃ + a₄ + a₅ + a₆ + a₇ + a₈ + a₉ + a₁₀ + a₁₁ + a₁₂ + a₁₃ + a₁₄ + a₁₅ + a₁₆ + a₁₇ + a₁₈ + a₁₉ + a₂₀ + a₂₁ + a₂₂ + a₂₃ + a₂₄ + a₂₅

Continuing to reason to the method for solving the puzzle

• Now we have some more symbolic language to use. Let A be the puzzle to solve. From the two "0 =" lines in the solution of the system of equations, we can determine that if real(A & P) ≠ 0 or real(A & Q) ≠ 0 then A does not have a solution. If real(A & P) = real(A & Q) = 0 then A has 4 solutions which may be found with the solved system of equations. If fact, if you're fine with formulae, you can stop reading here.
• But if you don't want to deal with formulae, then read on.
• Let B be the solution of A in which b₂₄ = 0 and b₂₅ = 0. From the solved system of equations, we determine that the other solutions of the puzzle, A, are B + P, B + Q, and B + (P + Q). The best solution(s) to the puzzle, B′, is/are the solution(s) for which abs(B′) is least.
• Of all the nature of + and ×, the most important equivalence is that (A × B) + (C × D) = (A + C) × (B + D). This means that the solution for the sum of multiple puzzles is the sum of their respective solutions. For example, let A₁ be puzzle 1 and A₂ be puzzle 2. We superimpose puzzle 2 on puzzle 1; in the process of superimposing, any light that is on in both puzzles is off in the resulting puzzle, since 1 + 1 = 0. We'll call the resulting puzzle simply A. (A = A₁ + A₂). The solution, B, to our new puzzle, A, is B₁ + B₂. (B = B₁ + B₂) Again, if a certain button is pressed in both solutions, then it remains unpressed in the solution to the resulting puzzle.
• We can take this knowledge to create a series of elementry puzzles, i.e. a (comparatively) small number simple puzzles that we can easily add together in order to form the puzzle that we wish to solve. Then we can simply add the solutions of the elementary puzzles together in order to get the solution to the puzzle we want. The elementary puzzles and respective solutions may be memorized or written on a cheat sheet. Noting symmetry will be a very useful aid to memorization.

Possible solutions for each elementry puzzle

Q.E.D.
Marq Thompson

Last Updated: 2009-05-02

The author, Marq Thompson, wished the content of this website to be uncopyrighted after his death.