← Back to the programme
    OlympiadMediumProofs7–9

    Invariant Principle

    Princípio do Invariante

    On a board, numbers 1 through 20 are written. In each step, you erase two numbers aa and bb, and write ∣a−b∣|a - b|. Can the last remaining number be 0?

    Consider the sum of all numbers modulo 2.

    Solution

    Step 1 of 6

    1. 1.Invariant: replacing aa and bb by ∣a−b∣|a - b| never changes the parity of the total sum, because ∣a−b∣≡a+b(mod2)|a - b| \equiv a + b \pmod{2}.