01 · Challenge AMC 10/12 · Cayley · early COMC
DifficultyThe last number on the board
The numbers are written on a board. In one move you erase any two numbers and and write in their place. After nine moves a single number is left.
Show that it cannot be , and determine exactly which values it can be.
02 · ExploreStop tracking the board
You cannot follow the board itself — after three moves there are far too many possibilities to track, and the order of moves is not fixed.
So look instead for something computed from the board that a move cannot disturb. Start with the total, and try a couple of moves on a smaller set to see what happens to it.
03 · StrategyName the thing that never changes
This is the invariance principle. Rather than following the process, find a quantity the process is incapable of altering.
The total on the board does change with every move — so ask a coarser question about it. What happens to its parity?
04 · SolveWrite the argument end to end
For any two numbers and , the quantity equals either or , so it is always even. A move therefore changes the total on the board by an even amount, which means the parity of the total is an invariant.
At the start the total is , which is odd. After nine moves one number remains and that number is the total, so it is odd. In particular it cannot be .
That settles the first half. For the second, note that , so no move ever produces a number larger than the largest already on the board. The largest starting number is , so the final number is at most ; and it is non-negative, being an absolute value.
The final number is therefore odd and lies between and , so it is one of — and every one of those is genuinely reachable.
To finish at : erase and to write . Pair the remaining eight numbers as , each giving . Combine those four s in pairs to get two s, combine those to get a single , and finish with . That is nine moves exactly. Replacing the first move with , or leaves eight numbers that again split into four consecutive pairs, so the same ending produces , and .
To finish at : pair to get five s, reduce four of them to a single , and finish with .
So the last number is odd, and the complete set of possible values is .
End of proof.
05 · ExtendWhere this goes next
Three questions, in rising order of difficulty. We do not post the answers.
- Start from to instead of to . Which values can the last number take?
- Replace with . What is invariant now, and why is the problem suddenly boring?
- Replace it with but start from copies of the same number. What changes?
Any time a problem says "repeat this operation in any order until one thing is left", it is almost certainly asking what the operation cannot change.
We do not post the answers to 05. That is the part the student brings back.
