Saturday, December 17, 2005

Always Stays the Same. Topic: Invariants. Level: AIME.

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$?