2024 AMC 10B Problem 16
Jerry likes to play with numbers. One day, he wrote all the integers from to on the whiteboard. Then he repeatedly chose four numbers on the whiteboard, erased them, and replaced them by either their sum or their product. (For example, Jerry's first step might have been to erase , , , and , and then write either , their sum, or , their product, on the whiteboard.) After repeatedly performing this operation, Jerry noticed that all the remaining numbers on the whiteboard were odd. What is the maximum possible number of integers on the whiteboard at that time?
Show solution without answering
Key insight
Each move removes three numbers, so the count always leaves remainder 2 when divided by 3. The odd numbers never grow past 1012. Only 1010 fits both.
Solution
This is a "maximum" question, so there are two halves: find limits that no strategy can beat, then show a strategy that reaches the limit.
Limit 1: how the count changes.
- Each move erases numbers and writes , so the board loses exactly numbers every time.
- The board starts with numbers, and . Taking away at a time, the count always leaves remainder when divided by :
- Check the choices: and fit. , and do not.
Limit 2: the number of odd numbers never goes up.
- Recall the rules: a sum is odd only when it has an odd number of odd terms, and a product is odd only when every factor is odd.
- So a move can create an odd number only if at least one of the four erased numbers was odd. A move erases at least one odd and writes at most one odd, so the number of odds on the board never goes up.
- From to there are odd numbers. At the end everything is odd, so there are at most numbers. That rules out .
So the answer is at most .
Reaching .
- Take three even numbers and one odd number and replace them with their sum. Even even even odd is odd. This removes three evens and keeps the number of odds at .
- There are evens. Doing step 7 times removes evens, leaving even.
- Now take that last even number with three odd numbers and replace them with their sum: even odd odd odd is odd. This uses up three odds and writes one, so odds remain.
- The board now holds numbers, all odd.
The limit is and it can be reached.
The answer is .
Why this works
For a process that repeats a move, look for things the move cannot change (the remainder of the count when divided by ) or can only change in one direction (the number of odds, which never grows). Each gives a limit, and together they leave a single possible answer. Then build an actual sequence of moves that reaches it.
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Two observations bound the answer.
Count mod 3. Every operation erases four numbers and writes one, a net loss of three. Starting from , the count is always . Among the choices only and qualify.
Odd numbers never increase. An operation produces at most one odd number, and to produce an odd result it must consume at least one odd input (a sum is odd only if an odd number of its terms are odd; a product is odd only if all four are). So the number of odd numbers on the board never goes up. It starts at , so the final count is at most , ruling out .
Construction for . Repeatedly replace three evens and one odd by their sum, which is odd; this keeps the odd count at and removes three evens each time. After such moves, evens are gone and one even remains. Absorb it with the sum of that even and three odds, which is odd. The board now holds numbers, all odd.
The answer is .
Review in the AoPS books
- Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
- Introduction to Number Theory, Chapter 1: Integers: The Basics
- Introduction to Algebra, Chapter 20: Special Functions (§20.3)
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.