Monday, February 4, 2013

Counting II : Practice Counting Systematically

Counting Coins
Lots of similar questions appear on Mathcounts tests. Be careful when there are limits, for example, the sum of the coins do not exceed ___ or you have to have at least one for each type, etc...

Partition

The Hockey Stick Identity from Art of Problem Solving
Same as "Sticks and Stones", or "Stars and Bars" methods

Applicable question: Mathcounts 2008 Chapter #9--During football season, 25 teams are ranked by three reporters (Alice, Bob and Cecil). Each reporter assigned all 25 integers (1 through 25) when ranking the twenty-five teams. A team earns 25 points for each first-place ranking, 24 points for each second-place ranking, and so on, getting one point for a 25th place ranking. The Hedgehogs earned 27 total points from the three reporters. How many different ways could the three reporters have assigned their rankings for the Hedgehogs? One such way to be included is Alice - 14th place, Bob - 17th place and Cecil - 20th place.

Solution I :
Let's see how it could be ranked for Hedgehogs to get 27 points from the three reporters.
A          B         C
1           1        25     1 way for C to get 25 points and the other two combined to get 2 points
1           2        24
2           1        24    2 ways for C to get 24 points and the other two combined to get 3 points.
1           3        23
3           1        23
2           2        23    3 ways for C to get 23 and the other two combined to get 4 points.
.
.
25        1         1     25 ways for C to get 1 point and the other two combined to get 26 points.
1 + 2 + 3 + ...25 = $$\dfrac {25\times 26} {2}=325$$
Solution II:
Use 26C2. Look at this questions as A + B + C = 27 and A, B C are natural numbers. To split the objects into three groups (for Alice, Bob, and Cecil), we must put 2 dividers between the 27 objects. (You can't grant "0" point.) There are 26 places to put the dividers, so 26C2 and the answer is $$\dfrac {26\times 25} {2}=325$$