1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Think about it this way: at the beginning, the score of the game is $0-0$, so the scores differ by $0$. Put a point at $(0,0)$ on a grid. At every goal ($+1$ in $x$), you can either go 'up' or 'down', but not below $0$ and not above $2$. This gives you something like a mountain range, which definitely has a name but I can't remember what it is. I think it can be counted by Stirling numbers. $\endgroup$ – Ian Coley Apr 7 '14 at 0:25
  • $\begingroup$ Thanks! I don't know what Stirling numbers are, but I am looking into it right now. $\endgroup$ – Joao Apr 7 '14 at 0:26
  • $\begingroup$ Stirling numbers maybe too strong for this situation, actually. But those diagrams are definitely more countable than the arbitrary scores. $\endgroup$ – Ian Coley Apr 7 '14 at 0:27
  • $\begingroup$ Ok, I'll try that $\endgroup$ – Joao Apr 7 '14 at 0:28
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ I think you have the wrong interpretation. OP wants the number of ways that the game could progress, and not the total number of end results. $\endgroup$ – Calvin Lin Apr 7 '14 at 0:48
  • $\begingroup$ @CalvinLin: Maybe you're right; maybe the OP could clear this up? $\endgroup$ – Contactoid Apr 7 '14 at 0:50
  • $\begingroup$ @CalvinLin: I think you're right, from the OP's 2nd paragraph. Let me rethink... $\endgroup$ – Contactoid Apr 7 '14 at 0:58
  • $\begingroup$ @Contactoid, Nice answer, but calvin lin is right, I want the total number of different ways the game could progress, not the end outcomes. $\endgroup$ – Joao Apr 7 '14 at 1:23
  • $\begingroup$ @Joao: I changed the answer to (try to )account for that; please see the edit and let me know if you're cool with that. $\endgroup$ – Contactoid Apr 7 '14 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.