Solution to "Final Score"


The answer is

{\small 343710265391227466495355064698842944459482614776876895261980070918126524,}

or approximately 3.4371\times 10^{71} ways.

I was inspired to solve this problem while sitting at Outback Steakhouse. The television at the bar displayed the final score for a basketball game: 83 to 74. Though I don't pay much attention to sports, I pretty well know the basic rules for the most popular ones. So I wondered how many ways there were for that game to have played out since I saw only the final score. Here is what I came up with:

There are two ways I know of to get the answer. One is a simple (though kinda ugly) counting function involving a few summations. The second is my professor's solution using a recursive formula.

For the first method, we will equate the problem to counting the number of ways to rearrange x_1 1-pointers, x_2 2-pointers, and x_3 3-pointers by team A with y_1 1-pointers, y_2 2-pointers, and y_3 3-pointers from team B. That is, if A and B are the final scores for team A and team B, respectively, then for each solution to the system

\begin{eqnarray*}x_1+2x_2+3x_3 & = & A\\ y_1+2y_2+3y_3 & = & B,\end{eqnarray*}

we want to count the number of ways to rearrange the total number of plays, (x_1+x_2+x_3+y_1+y_2+y_3), taking into account that x_i,y_i are identical elements. Then, we add the number of rearrangements of each solution over all solutions to get our answer. Well, for each solution we have  (x_1+x_2+x_3+y_1+y_2+y_3)! arrangements of the elements, then we need to divide out the different arrangements of each set of identical elements, obtaining the total number of unique arrangements for each solution to be

\frac{(x_1+x_2+x_3+y_1+y_2+y_3)!}{x_1!x_2!x_3!y_1!y_2!y_3!}.

Now we want to sum this over all possible solutions to the system of equations above. We achieve that with the following rather elementarily derived quadruple summation

\sum_{x_3=0}^{\lfloor\frac{A}{3}\rfloor}\sum_{x_2=0}^{\lfloor\frac{A-3x_3}{2}\rfloor}\sum_{y_3=0}^{\lfloor\frac{B}{3}\rfloor}\sum_{y_2=0}^{\lfloor\frac{B-3y_3}{2}\rfloor}.

This runs through all solutions to the given system where for any given x_2,x_3,y_2,y_3, x_1=A-3x_3-2x_2 and y_1=B-3y_3-2y_2. Substituting these expressions for x_1 and y_1 gives us the total number of ways f(A,B) a basketball game could have happened given final score A to B to be

f(A,B)=\sum_{x_3=0}^{\lfloor\frac{A}{3}\rfloor}\sum_{x_2=0}^{\lfloor\frac{A-3x_3}{2}\rfloor}\sum_{y_3=0}^{\lfloor\frac{B}{3}\rfloor}\sum_{y_2=0}^{\lfloor\frac{B-3y_3}{2}\rfloor}\frac{(A-2x_3-x_2+B-2y_3-y_2)!}{(A-3x_3-2x_2)!x_2!x_3!(B-3y_3-2y_2)!y_2!y_3!}.

Using (A,B)=(83,74) gives us the solution to the original question. To get that solution requires a math package that can deal with arbitrary size integers. I used PARI/GP as it is open source, handles arbitrary size integers, and I use it a lot, but other packages can be used such as Maple, Mathematica, etc. Some math packages will not be able to handle the size of the number, such as Matlab.

The recursive solution comes from the idea that given the score (A,B), the last score could have been a 1, 2, or 3 pointer by team A or team B. Thus,

f(A,B)=f(A-1,B)+f(A-2,B)+f(A-3,B)+f(A,B-1)

+f(A,B-2)+f(A,B-3),

for A and B\ge 0, where f(0,0)=1, and f(A,B)=0\text{ if }A\text{ or }B<0. This is like a two-dimensional version of the Tribonacci sequence. In fact, f(A,0) is the Tribonacci sequence.

The following table displays the values for A,B\le 7. Implemented in a computer program, one can very quickly build a matrix of all possible scores for any realistic basketball game. Of course, f(83,74) still gives us the same answer as above.

final_score