SMC 2012 Q12
12. The number 3 can be expressed as the sum of one or more positive integers in four different ways:
In how many ways can the number 5 be so expressed?
- A 8
- B 10
- C 12
- D 14
- E 16
Senior Mathematical Challenge 2012, Question 12. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: E 16
Two different ways of expressing 5 are 1 + 4 and 4 + 1. In the following list these are denoted as {1, 4: two ways}. The list of all possible ways is {5: one way}, {2, 3: two ways}, {1, 4: two ways}, {1, 2, 2: three ways}, {1, 1, 3: three ways}, {1, 1, 1, 2: four ways}, {1, 1, 1, 1, 1: one way}. So in total there are 16 ways.
{Different expressions of a positive integer in the above form are known as ‘partitions’. It may be shown that the number of distinct compositions of a positive integer n is \(2^{n-1}\).}
Solution © UK Mathematics Trust, from the SMC 2012 solutions. Longer versions with investigations: Solutions and investigations (PDF).