Invariants Math Example 5
Follow the full solution, then compare it with the other examples linked below.
Example 5
hardA 2×n grid of squares is colored with 2 colors. You repeatedly flip all colors in any row or column. Show that the parity of the number of black squares is an invariant.
Solution
- 1 Let \(B\) = number of black squares in the 2×n grid (total \(2n\) squares).
- 2 Flip a column of 2 squares: if both were black, \(B\) decreases by 2 (even change). If both white, \(B\) increases by 2. If one each, \(B\) changes by 0.
- 3 Flip a row of \(n\) squares: \(B\) changes by \(\pm n\) or by an integer with the same parity as \(n\).
- 4 If \(n\) is even, row flips change \(B\) by an even amount. Column flips always change \(B\) by 0 or ±2.
- 5 So the parity of \(B\) is invariant under all allowed operations.
Answer
The parity of \(B\) (number of black squares) is invariant
Invariants in combinatorics often involve parity (odd/even). Each allowed operation changes the count by an even number, so the parity of black squares never changes.
About Invariants
Quantities or properties that remain unchanged during a process, operation, or transformation—values that stay the same no matter how the system is rearranged or acted upon.
Learn more about Invariants →More Invariants Examples
Example 1 medium
A sequence starts at 1 and each term is 3 times the previous minus 2: (a_{n+1} = 3a_n - 2). Show tha
Example 2 hardIn a game, you can add 3 or subtract 5 from a number. Starting at 0, can you reach 1? Use an invaria
Example 3 mediumThe sum of digits of a number doesn't change modulo 9 when you add 9. Verify: 47 → 47+9=56. Is the d
Example 4 mediumShow that for any right triangle with legs (a, b) and hypotenuse (c), the quantity (a^2 + b^2 - c^2