Questions: Invariants and Monovariants

Question 1

You start with a pile of 100 coins. At each step, you split any pile into two smaller piles and write down the product of the two pile sizes. After all splits, you have 100 piles of 1 coin each. What is the sum of all the products you wrote down?

• A. 99
• B. 100
• C. 4950
• D. 5050

Answer: (C)

The invariant is the sum of the squares of all pile sizes minus the sum of the products recorded. Or more directly: consider that the sum of all products always equals (100 choose 2) = 4950, regardless of how you split. You can verify with a small example: 3 coins, split into 2+1 (product 2), then split 2 into 1+1 (product 1). Total: 3. And (3 choose 2) = 3. The invariant ensures the answer is always 4950.

Question 2

A monovariant is a quantity that can increase or decrease, but not both, during a process.

• T. True
• F. False

Answer: True

A monovariant changes in only one direction. If it can only decrease, each step reduces it. If it can only increase, each step raises it. Combined with a bound (a floor for decreasing, a ceiling for increasing), this guarantees the process terminates — the monovariant can only change finitely many times before hitting the bound.

Question 3

A 3×3 grid is filled with +1 and -1. At each step, you choose a row or column and flip all signs in it. Can you reach a grid where all entries are +1, starting from a grid with exactly one -1?

Model answer: No. The invariant is the product of all nine entries. Initially, the product is -1 (eight +1s and one -1). Flipping a row or column flips 3 entries, which multiplies the product by (-1)³ = -1. So each step multiplies the total product by -1, alternating between -1 and +1. The all-+1 grid has product +1. Starting from -1, after any even number of steps the product is -1, and after any odd number it is +1. But we need the grid to be all +1s, which requires the product to be +1 AND all entries to be +1. However, having the right product does not guarantee the right configuration. The deeper invariant is that the product changes between -1 and +1, but reaching all +1s from a single -1 is impossible because the parity of the number of -1s changes by an odd number each step (1 or 3 entries flip), so the parity of the count of -1s changes at each step. Starting with 1 (odd), after one step you have 0 or 2 or 4 (even) negative entries, then odd again, etc. You need 0 (even) -1s. After an odd number of steps you have odd count, after even you have even. So it is possible after an even number of steps to have 0 negative entries — but the product invariant shows this is impossible since the product after an even number of steps is -1, which means an odd number of -1s. Contradiction. Therefore it is impossible.

The product of all entries is the key invariant. Each row/column flip changes exactly 3 signs, multiplying the total product by (-1)³ = -1. Starting at -1, the product alternates -1, +1, -1, +1, ... The target (all +1s) has product +1, achievable only after an odd number of steps. But to get all +1s, we also need every entry individually to be +1. The invariant narrows the search space and, combined with more detailed analysis, proves impossibility.