The Grid Technique in Solving Harder Mathcounts Counting Problems : from Vinjai

The following notes are from Vinjai, a student I met online. He graciously shares and offers the tips here on how to tackle those harder Mathcounts counting problems. 

The point of the grid is to create a bijection in a problem that makes it easier to solve. Since the grid just represents a combination, it can be adapted to work with any problem whose answer is a combination.

For example, take an instance of the classic 'stars and bars' problem (also known as 'balls and urns', 'sticks and stones', etc.):

Q: How many ways are there to pick an ordered triple (a, b, c) of nonnegative integers such that a+b+c = 8? (The answer is 10C2 or 45 ways.)

Solution I: 

This problem is traditionally solved by thinking of ordering 8 stars and 2 bars. An example is:

* * * |    | * * * * *

  ^       ^       ^

  a       b       c

This corresponds to a = 3, b = 0, c = 5.

Solution II: 

But this can also be done using the grid technique:

The red path corresponds to the same arrangement: a = 3, b = 0, c = 5. The increase corresponds to the value: a goes from 0 to 3 (that is an increase of 3), b goes from 3 to 3 (that is an increase of 0), and c goes from 3 to 8 (that is an increase of 5). So a = 3, b = 0, c = 5.

Likewise, using a clever 1-1 correspondence, you can map practically any problem with an answer of nCk to fit the grid method. The major advantage of this is that it is an easier way to think about the problem (just like the example I gave may be easier to follow than the original stars and bars approach, and the example I gave in class with the dice can also be thought of in a more numerical sense).