Definition: An invariant, logically defined, is simply something that stays the same after any possible transition, or move.
--------------------
Problem #1: (WOOT Lecture) $2005$ numbers are written on a board. On each move, two numbers are erased and the positive difference is written in place of them. Can the last remaining number be $2$?
Solution: What invariant can we find here? From any two numbers $a$ and $b$ with $a > b$, our move takes $(a,b)$ to $a-b$.
Let's try the parity of the sum of all the numbers on the board. Note that the parities of $a+b$ and $a-b$ are equivalent. Thus the parity of the sum of all numbers is invariant because our move does not change it.
Since the original sum is $1+2+\cdots+2005 = \frac{(2005)(2006)}{2} = 2005 \cdot 1003$ is odd and $2$ is even, it is impossible for the last number to be $2$. QED.
--------------------
Problem #2: (WOOT Lecture) Suppose you have a heap of $1001$ stones. On each move, you remove one stone from a heap and divide the remaining number of stones in the heap between two new heaps. Prove that you can never make all heaps have $3$ stones.
Solution: Note that on each move the number of heaps increases by $1$ and the number of stones decreases by $1$. So let's try the invariant of $heaps+stones = 1002$.
If all the heaps have $3$ stones, then we have $heaps = 3(stones)$. So $3(stones)+stones = 4(stones) = 1002$, but $1002$ is not divisible by $4$ so it is impossible. QED.
--------------------
Comment: Invariants are super cool and powerful; they just blow me away!
--------------------
Practice Problem #1: (WOOT Message Board) You have a coin machine. When you put a penny in, you get five nickels. When you put a nickel in, you get five pennies. If you start out with one penny, can you ever get an equal number of pennies and nickels?
Practice Problem #2: (WOOT Message Board) Is it possible to cover a $10 \times 10$ square with $25$ rectangles of size $1 \times 4$?
1. The invariant is (number of coins) mod 4 = 1, so we can never have an even number of coins. Q.E.D.
ReplyDelete2. I found a coloring proof =P
Color every other square on every other line. Then each 1x4 rectangle must cover either 0 or 2 such colored squares, but there are 25 of them. Hence, no covering is possible. Q.E.D.
Nice, #2 is indeed solved by coloring/numbering. Just have four different colors/numbers checkerboarded and you see that each 1x4 covers one of each, so the number of each color/number is always the same. But you start out with 26 of one of the colors/numbers, so it's impossible.
ReplyDelete1. Or the invariant is the difference in pennies and nickels, which is always 1 mod 2.
ReplyDelete