"Relatively Close" Soccer Game

Question

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:

1. Both teams having six goals.

2. Team 1 having 7 goals and team 2 having 5 goals.

3. 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.

Answer 1

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.

Answer 2

If you are only interested in this particular problem and not a general formular, you're looking for the set of integer solutions to $x-y \leq 2$, which has three subcases: $x-y=2; x-y=1; x-y=0$ , and then , if the two socres are indistinguishable, i.e., if the score $(a,b)$ is considered the same as $(b,a)$, you're done; if not, then just double the total and subtract $7$ ( to avoid counting scores of the type $(a,a)$ twice. So it all comes down to counting the pairs $(0,2), (1,3),...,(5,7) ; (0,1),(1,2),..,(5,6); (0,0), (1,1),(2,2),..,(6,6)$ (and, if these are considered different from $(0,2),(3,1)...$, i.e., if the score $(a,b)$ is considered different from $(b,a)$, double the total and subtract $7$; the $7$ pairs $(a,a)$).

EDIT: From Calvin Lin's comments and the OP's second paragraph, I think we want to count the total number of games where the difference at any stage is less-than-or-equal-to 2. Then we can just count the number of paths in a graph with vertices all pairs of numbers $(a,b)$where $a-b \leq 2$ ;we join $(a,b)$ with $(a',b')$ with a (one-directional) edge iff (def.) $a-a' =1 $ or if $b-b'=1$ (the vertex goes from (a',b') to (a,b) if a-a'=1 or if (b-b')=1). Then we have a directed graph, and all we need to do is to count the number of paths that go from $(0,0)$ to either of $(5,7), (7,5)$ or to $(6,6)$.