2016 AMC 10A Problem 14
How many ways are there to write as the sum of twos and threes, ignoring order? (For example, and are two such ways.)
Show solution without answering
Key insight
The number of threes must be even, so it can be 0, 2, 4, up to 672. That is 337 choices.
Solution
A way to make is fixed once you know how many threes are used; the twos then fill the rest. So count the possible numbers of threes.
- Let be the number of threes. The threes add up to , and the twos must make up the rest, .
- The twos always add up to an even number, so must be even. Since is even, must be even, and that happens exactly when is even.
- Look at the first few cases:
| threes | total from threes | twos needed |
|---|---|---|
Each even works, as long as the threes do not go past .
4. The largest is when threes make the whole : , which is even, with twos.
5. So can be . Dividing each by gives , which is numbers (remember to count the ).
The answer is .
Why this works
When one amount decides everything else, count the choices for that amount. An even/odd check told us which values of are allowed, and the allowed values go up in steps of . The example in the problem, with threes, hints that is even. When counting a list like , watch for the off-by-one: include both ends.
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
A way to write is a pair of nonnegative integers with
where is the number of twos and the number of threes.
Since and are even, must be even, so is even. Write . Then , i.e. . This is a nonnegative integer exactly when .
Each in that range gives one valid pair, so the number of ways is .
The answer is .
Review in the AoPS books
- Introduction to Number Theory, Chapter 7: Algebra With Integers
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Introduction to Algebra, Chapter 11: Special Factorizations (§11.5)
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques
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.