Friday, November 1, 2013

Counting I : Ways to Avoid Over Counting or Under Counting

Check out Mathcounts here, the best competition math program for middle school students.
Download this year's Mathcounts handbook here.

Question #1: How many ways to count a triple of natural numbers whose sum adds up to 12 
if  A. order doesn't matter? B. if order matters?

Solution I:
A. Find a systematic way to solve this type of problem in an organized manner.
We can start with the smallest natural number "1".
(1, 1, 10), (1, 2, 9), (1, 3, 8), (1, 4, 7), (1, 5, 6)  Since (1, 5, 6) is the same as (1, 6, 5) so stop.
(2, 2, 8), (2, 3, 7), (2, 4, 6), (2, 5, 5)
(3, 3, 6), (3, 4, 5)
(4, 4, 4) so total there are 12 ways.

B. Since in this case order matters so if you add up all the possible ways, for example, there are "3" ways to arrange (1, 1, 10) -- 3!/2! = 3
This is similar to "how many ways to arrange the letters 'odd'.
If all letters/numbers are different, you have 3! ways to arrange them; however, in this case, the two numbers 1, 1 are indistinguishable and there are 2! ways to arrange them, thus 3!/2! = 3

There are 3! or 6 ways to arrange triples such as (1, 2, 9).
Add all the possible ways and there are total 55 ways.

Solution II:
B.There is a much easier way to tackle this question, using bars and stars or sticks and stones method.
There are 11 spaces between 12 stones. @__@__@__@__@__@__@__@__@__@__@__@
If you places the two sticks on two of the spaces, you'll split the stones into three groups.
For example, if you have @ | @@@@@ | @@@@@@
The triples are 1, 5, and 6.
If it's @@@@@@@@ | @@ | @@ , the triples are 8, 2, and 2.
So 11C2 = 55 ways

Let me know if you are still confused.  Have fun problem solving !!