It’s all done with matrices.
Let’s solve a slightly easier problem where n philosophers are in a line. If there is one philospher, there are two possibilities, he can either eat or not eat:
\begin{pmatrix}1 \\ 1\end{pmatrix}
The top number in each vector is how many ways a philosopher can refrain from eating. The bottom number is how many ways they can eat. If we add a second philosopher, there are three possibilities, neither philosopher eats, the first philosopher eats, and the second philosopher eats. So there are two ways the second philosopher can not eat and one way he can eat:
\begin{pmatrix} 2 \\ 1\end{pmatrix}
We can work this out by looking at the previous vector. A third philosopher will be able to not eat in the 2 cases where the second philosopher is not eating, and will also be able to eat in the 1 case where the second philosopher eats, so 3 in total. But he will only be able to eat in the 2 cases where the second philosopher does not eat:
\begin{pmatrix} 3 \\ 2 \end{pmatrix}
In general, if there are x ways the rightmost philosopher can not eat, and y ways he can eat, there are x+y ways that an additional philosopher can sit down next to him and not eat, and x ways this additional philosopher can eat.
\begin{pmatrix} x \\ y \end{pmatrix}
\to
\begin{pmatrix} x+y \\ x \end{pmatrix}
You might notice that iterating this produces the Fibonacci sequence. This is because the formula we are using is the same.
Of course, the philosophers are not really in a line and the rightmost philosopher is actually sitting next to the leftmost philosopher. However, we can account for this by calculating twice, once where the leftmost philosopher does not eat and once where he does.
Let’s solve the problem for n=7:
\begin{pmatrix}1 \\ 0\end{pmatrix}
\begin{pmatrix}1 \\ 1\end{pmatrix}
\begin{pmatrix}2 \\ 1\end{pmatrix}
\begin{pmatrix}3 \\ 2\end{pmatrix}
\begin{pmatrix}5 \\ 3\end{pmatrix}
\begin{pmatrix}8 \\ 5\end{pmatrix}
\begin{pmatrix}13 \\ 8\end{pmatrix}
\begin{pmatrix}0 \\ 1\end{pmatrix}
\begin{pmatrix}1 \\ 0\end{pmatrix}
\begin{pmatrix}1 \\ 1\end{pmatrix}
\begin{pmatrix}2 \\ 1\end{pmatrix}
\begin{pmatrix}3 \\ 2\end{pmatrix}
\begin{pmatrix}5 \\ 3\end{pmatrix}
\begin{pmatrix}8 \\ 5\end{pmatrix}
Again, the top number in each vector is how many ways a philosopher can refrain from eating. The bottom number is how many ways they can eat. Each vector is calculated from the vector to it’s left.
I’ve done this twice, once where the first philosopher doesn’t eat and once where he does. Our answers are on the right hand side:
- There are 13 ways for the 1st and 7th philosophers to not eat
- There are 8 ways for the 1st philosopher to not eat and the 7th philosopher to eat.
- There are 8 ways for the 1st philosopher to eat and the 7th philosopher not to eat.
- There are 5 ways for the 1st and 7th philosophers to eat, if we forget for a moment that they are sitting next to each other.
Since the last case does not count, the answer is 13 + 8 + 8 = 29. Armed with this knowledge, you can score 44.53 points.
Can we do better? You’ve probably figured out how to calculate one vector from another, but you probably haven’t thought of doing it with matrices. You probably don’t know how matrices work either, so let me try to explain. This is how you multiply a matrix by a vector:
\begin{pmatrix}a & b \\ c & d\end{pmatrix}
*\begin{pmatrix}e \\ f\end{pmatrix}
=\begin{pmatrix}ae+bf \\ ce+df\end{pmatrix}
The matrix below can be used to calculate the next vector:
\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}
*\begin{pmatrix}5 \\ 3\end{pmatrix}
=\begin{pmatrix}5+3 \\ 5\end{pmatrix}
=\begin{pmatrix}8 \\ 5\end{pmatrix}
Armed with your newfound knowledge of matrix-vector products, you can once again score 44.53 points. But you can also multiply matrices by matrices:
\begin{pmatrix}a & b \\ c & d\end{pmatrix}
*\begin{pmatrix}e & f \\ g & h\end{pmatrix}
=\begin{pmatrix}ae+bg, & af+bh \\ ce+dg, & cf+dh\end{pmatrix}
Note that you can treat the second matrix as two vectors
\begin{pmatrix}e \\ g\end{pmatrix} and $\begin{pmatrix}f \ h\end{pmatrix}$and multiply both by the first matrix to get the same result.
The big secret is that multiplying this matrix product by a vector has the same effect as multiplying both vectors in turn by the matrix:
\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}
*\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}
=\begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix}
\begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix}
*\begin{pmatrix}5 \\ 3\end{pmatrix}
=\begin{pmatrix}10+3 \\ 5+3\end{pmatrix}
=\begin{pmatrix}13 \\ 8\end{pmatrix}
So now we have a matrix that does what we want twice as fast. But why stop there? We can have a matrix that is four times as fast, eight times as fast, sixteen times as fast, and if we keep multiplying matrices by themselves we can quickly obtain vectors that are millions, billions, or even trillions of times faster than the one we started with.
What we do is called matrix exponentiation, and it can be done the same way as exponentiation on numbers. We start like this:
answer = \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix},
base = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}
,power = 6
answer is initialized to the identity matrix, which does nothing. Ostensibly, we want to multiply it by base six times. However, this is the same as multiplying by base^2 three times:
answer = \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix},
base = \begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix}
,power = 3
Now power is odd, so we multiply answer by base:
answer = \begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix},
base = \begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}
,power = 2
Once again, power is even, so we square base and halve power:
answer = \begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix},
base = \begin{pmatrix}5 & 3 \\ 3 & 2\end{pmatrix}
,power = 1
And finally we multiply answer by base for the last time:
answer = \begin{pmatrix}13 & 8 \\ 8 & 5\end{pmatrix},
base = \begin{pmatrix}5 & 3 \\ 3 & 2\end{pmatrix}
,power = 0
Now we can solve the problem easily:
$ \begin{pmatrix}13 & 8 \ 8 & 5\end{pmatrix}
- \begin{pmatrix}1 \ 0\end{pmatrix}
= \begin{pmatrix}13 \ 8 \end{pmatrix}$
$ \begin{pmatrix}13 & 8 \ 8 & 5\end{pmatrix}
- \begin{pmatrix}0 \ 1\end{pmatrix}
= \begin{pmatrix}8 \ 5 \end{pmatrix}$
With this matrix exponentiation approach, you should be able to solve even n=10^{18} in milliseconds.
my code