Invariants Math Example 2
Follow the full solution, then compare it with the other examples linked below.
Example 2
hardIn a game, you can add 3 or subtract 5 from a number. Starting at 0, can you reach 1? Use an invariant (parity or modular) argument.
Solution
- 1 Operations: \(+3\) or \(-5\). Both change the number by an odd amount.
- 2 Check modulo 2: starting at 0 (even). Adding 3 (odd) → odd. Subtracting 5 (odd) → even or odd.
- 3 Better: use mod 8. \(+3\) or \(-5 \equiv +3 \pmod{8}\).
- 4 So all reachable numbers are \(3k \pmod{8}\) for integer \(k\): \(\{0, 3, 6, 1, 4, 7, 2, 5\}\) — actually all residues are reachable since \(\gcd(3,8)=1\).
- 5 Since \(\gcd(3,8)=1\), 1 IS reachable: e.g., \(0 \xrightarrow{+3} 3 \xrightarrow{+3} 6 \xrightarrow{-5} 1\).
Answer
Yes, 1 is reachable: \(0 \to 3 \to 6 \to 1\)
Invariant arguments check if a property is preserved by all allowed operations. Here GCD analysis shows all integers mod 8 are reachable.
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 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
Example 5 hardA 2×n grid of squares is colored with 2 colors. You repeatedly flip all colors in any row or column.