## Monday, February 4, 2013

### 2013 Mathcounts State Prep: Partition Questions

#24 2001 Mathcounts Sate Sprint Round: The number 4 can be written as a sum of one or more natural numbers in exactly five ways: 4, 3+1, 2 + 1 + 1, 2 +2 and 1 + 1 + 1 + 1; and so 4 is said to have five partitions. What is the number of partitions for the number 7?

#2: Extra: Try partition the number 5 and the number 8.

Solution:
#24: You can solve this problem using the same technique as counting coins:

7     6    5    4    3    2    1

1                                           1 way
1                                    1 way
1                 1           2 ways ( 5 + 2 or 5 + 1 + 1)
1    1                  1 way
1           1           2 ways ( 4 + 2 + 1 or 4 + 1 + 1 + 1)
2     0   1      1 ways
1     2           3 ways ( 3 + 2 + 2, 3 + 2 + 1 + 1 and 3 + 1 + 1 + 1 + 1)
3           4 ways (2 + 2 + 2 + 1, 2 + 2 + 3 ones, 2 + 5 ones and 7 ones.)

Total 15 ways.

The partitions of 5 are listed below (There are 7 ways total.):

5   4   3   2   1
1                           1 way
1                      1 way
1    1           2 ways  (3 + 2 and 3 + 1 + 1)
2           3 ways  (2 + 2 + 1, 2 + 1 + 1 + 1 and 1 + 1 + 1 + 1 + 1)

There are 22 ways to partition the number 8.