Q:

"Relatively Close" Soccer Game

A soccer game between 2 teams is "relatively close" if the scores never differ by more than 2. In how many ways can the game be "relatively close" for the first 12 goals?
Just to clear it up, the game would not be "relatively close" if team 1 scored the first six goals and team 2 scored the last six goals, because at some time in that game the scores differed by more than 2.
I found that the scores would have to end with: 

Both teams having six goals. 
Team 1 having 7 goals and team 2 having 5 goals.
Team 1 having 5 goals and team 2 having 7 goals.

Please excuse my lack of knowledge with combinatorics, I only know the very basic permutations/combinations.

A:

I like to do this by "walking on a graph." 
-2 -1 0 1 2
------------
      1
     / \
    1   1
   / \ / \
  1   2   1
   \ / \ /
    3   3
   / \ / \
  3   6   3
   \ / \ /
    9   9
   / \ / \
  9   18  9
   \ / \ /
    27  27
   / \ / \
 27  54   27
   \ / \ /
   81   81
   / \ / \
 81  162  81
   \ / \ / 
   243  243
   / \  / \
 243 486  243

The diagram effectively has five columns, which could be labeled -2, -1, 0, 1, 2.
The top row (row 0) shows the one starting position, where 0 goals have been scored so far. There is "one way" that this could happen.
The next row shows each possible game with one goal. The home team could be "down by one" in 1 way, and "up by one" in 1 way. 
The next row shows each way the game could be after two goals have been scored. The home team could be "down by two" in one way, the game could be "tied" in two different ways, and the home team could be "up by two" in one way. That is, there are 1+2+1 = 4 possible ways the game could have gone after two goals.
For all the following rows, we make the following observation:
Suppose that after k goals (k = total # goals for both teams) the home team is "winning" by t. (t is in {-2, -1, 0, 1, 2}.) This means that either 

they were "winning" by (t-1) after (k-1) goals and had just scored the kth goal, or 
they were "winning" by (t+1) after (k-1) goals and the other team had just scored the kth goal.

Thus, if we let g(k, t) be the number of ways the game could go for k total goals so that the home team is "winning" by t, then we have:
g(k, t) = g(k-1, t-1) + g(k-1, t+1).
And we have the special cases that g(0, 0) = 1, g(anything, 3) = 0, g(anything, -3) = 0.
So, to get the answer to your question, just add the three numbers at the bottom of that figure.

