Three mirrors are arranged in the shape of an equilateral triangle, with their reflective surfaces pointing inwards. There is an infinitesimal gap at each vertex of the triangle through which a laser beam may pass.
Label the vertices $A$, $B$ and $C$. There are $2$ ways in which a laser beam may enter vertex $C$, bounce off $11$ surfaces, then exit through the same vertex: one way is shown below; the other is the reverse of that.
There are $80840$ ways in which a laser beam may enter vertex $C$, bounce off $1000001$ surfaces, then exit through the same vertex.
In how many ways can a laser beam enter at vertex $C$, bounce off $12017639147$ surfaces, then exit through the same vertex?
The problem can be solved using linear algebra, by setting up a system of recurrence relations and transforming it into a matrix problem.
First, it’s useful to restate the problem in terms of states. Each time the laser hits a mirror, it changes its state. There are 3 states which are: heading towards mirror A, mirror B and mirror C from inside the triangle.
Let’s denote the number of sequences with n reflections ending in a state ‘A’ as a_n, with n reflections ending in state B as b_n, and with n reflections ending in state C as c_n. We can estimate these sequences based on the position of the previous reflection. If the last but one reflection resulted in state ‘A’, then the last reflection could lead to states ‘B’ or ‘C’. Therefore: a_n = b_{n-1} + c_{n-1}.
Similarly, for the other two states, we get: b_n = a_{n-1} + c_{n-1} and c_n = a_{n-1} + b_{n-1}.
Combining these three variables in one column vector v_n = [a_n, b_n, c_n], we can express the system of equations in a matrix form as:
v_n = M * v_{n-1}, where M is a matrix of the form:
0 1 1
1 0 1
1 1 0
Considering v_0 = [0,0,1], we can compute the number of ways the laser beam can leave through vertex C after n reflections using matrix power: v_n = M^n * v_0.
And since M is a simple symmetric matrix, its eigenvalues can be found easily, which makes calculating M^n easy (using diagonalization), so that calculating v_{12,017,639,147} becomes feasible.
However, the numbers involved will be very large, and therefore we would likely need to implement this in a programming language that supports large integers, since the result will not fit in a standard 32-bit or even a 64-bit integer variable. So the answer will be c_{12,017,639,147} which is the 3rd element in vector v_{12,017,639,147}.
Just to emphasize – to find that number, one will need to program the implementation to handle large integers and compute matrix powers efficiently.
More Answers:
Iterative Circle PackingPrime-proof Squbes
Subsets with a Unique Sum