8
$\begingroup$

Consider a unconventional billiard board in the shape of an equilateral triangle (depicted below). An incredibly small ball (size in picture is increased for the sake of visibility on your screen) is put in the A corner.

Ett javla fint biljardbord, eller hur?

How many paths for the ball are there such that the ball bounces off the sides exactly 20160127 times, starting and ending in the A corner?

Note: the question is heavily inspired by a question on the Project Euler website, which I enjoyed very much solving.

Hint:

Case: 11 bounces, 2 paths; Case: 10001 bounces, 800 paths; Case: 1000001 bounces, 80840 paths.

Additional information: There is also a paper on the matter if you are interested in reading more.

$\endgroup$
  • $\begingroup$ Should a path be counted if on that path the ball visits A before the 20160127th bounce? (I assume the ball bounces off the corners as if it were bouncing off a line that makes 60 degrees with both of the triangle's sides at that corner.) $\endgroup$ – SpiritFryer Jan 26 '16 at 14:57
  • $\begingroup$ @SpiritFryer No $\endgroup$ – Carl Löndahl Jan 26 '16 at 15:18
  • $\begingroup$ Is my assumption about the way the ball bounces off the corners correct? (Under which assumption, a path heading from A to B would result in an infinite cycle of the ball going A -> B -> C -> A ...) If the assumption is wrong then we assume that a path stops once the ball reaches a corner. $\endgroup$ – SpiritFryer Jan 26 '16 at 15:23
  • 1
    $\begingroup$ I'd say the answer is 0, because you didn't stipulate that the ball's motion over the billiard table is frictionless or that the collisions are 100% elastic. Under realistic physics, the ball comes to a stop well before 20160127 impacts. Unless it's internally powered or something. $\endgroup$ – aroth Jan 27 '16 at 5:08
  • 1
    $\begingroup$ @aroth Clearly, it is a very special ball :-) $\endgroup$ – Carl Löndahl Jan 27 '16 at 8:57
1
$\begingroup$

Figured I might as well post my full resolution here. I will use a lot of @user3294068's reasoning here, so feel free to read on the initial part of his answer, with the mirror and virtual image thingies.

Mirror interpretation of bounces

Suppose the initial triangle has side length $1$. We will use a Cartesian coordinate system in which the initial vertex $A$ is the origin. We will say the level $l$ triangle is the equilateral triangle with side length $l$ that contains the initial vertex $A$, so for instance the big triangle in the image below is the level $3$ triangle:

The level 3 triangle

First, an important observation: a corner is hit in the top side of a level $l\geq 2$ triangle if and only if the ball crosses $2l-3$ black lines; in other words, if and only if it bounces $2l-3$ times. Thus, for the ball to reach a corner after bouncing $20160127$ times, the corner must lie on the top side of the level $n=10080065$ triangle. We will hereafter omit ‘the top side of’ for brevity and readability.

Now, because $n$ is odd, any corner on the level $n$ triangle will have $x$-coordinate in $\mathbb{Z}+\frac12$. Hence, any such corner that is hit belongs to the line $\gamma$ given by $y=a \cdot x$, where$$a = \frac{n\sqrt{3}}{2}\cdot\frac{1}{p+\frac12}$$for some $p \in \mathbb{Z}$ satisfying $p + \frac12 \leq \frac{n}{2}$.

We will make an analysis for the corners with positive $x$-coordinate without loss of generality; at the end, it suffices to double the result obtained. Notice that $x=0$ is always obscured except for the level $2$ triangle.

For a corner to be hit, it must not be obscured by some corner lying on a lower level triangle. If it is obscured, then there must be some integer $m < n$ and $q \leq \frac{m}{2}$ with $(q,m) \in \gamma$. Here, $q \in \mathbb{Z}$ if $m$ is even, and $q \in \mathbb{Z}+\frac12$ if $m$ is odd. Thus, if a corner is obscured the following equality must hold:$$m\cdot\left (p+\frac12\right)=n\cdot q$$

Case 1: $m$ is even

In this case, there is some $k \in \mathbb{Z}$ with $m=2k$, and $q \in \mathbb{Z}$. Our conditions are reduced to $k\leq \lfloor \frac{n}{2}\rfloor$ and $q \leq k$. We may also rewrite the equality as$$k \cdot (2p+1) = n \cdot x$$

We analyze the equality through prime decomposition. If $2p+1$ didn’t contain any of $n$’s factors, then they would all show up on $k$ and we’d have $k\geq n$, violating the first condition. Therefore, it must be that $2p+1$ contains one of $n$’s factors.

Now, say $2p+1$ contains factor $f$ of $n$, so we may write $2p+1 = c \cdot f$ for some integer $c$. In this case, we may take $m = \frac{n}{f}$ (notice it is an integer) and $q = c$. Observe that because $f > 2$, all conditions are met.

Thus, a corner $K$ (with $x$-coordinate $p + \frac12$) on the level $n$ triangle can be obscured by a corner in an even level triangle if and only if $2\cdot \left(p + \frac12 \right)$ contains a factor of $n$.

Case 2: $m$ is odd

In this case, there is some $r \in \mathbb{Z}$ with $q=r+\frac12$. Multiplying each side of the equality by $2$, we rewrite it as$$m \cdot (2p+1) = n \cdot (2r+1)$$

Once again, $2p+1$ must contain a factor of $n$, and we write $2p+1 = c \cdot f$. Then, we take $m = \frac{n}{f}$ and $q = \frac{c}{2}$. Notice that, since $2p+1$ is odd, so too must $c$ be odd, so $\frac{c}{2} \in \mathbb{Z}+\frac12$ as required. That the conditions are met is also easily checked.

Therefore, like in the even case, a corner $K$ on the level $n$ triangle can be obscured by a corner in an odd level triangle if and only if $2\cdot \left(p + \frac12 \right)$ contains a factor of $n$. We thus have the following:

Let $K$ be a corner on a level $l$ triangle, where $l>2$ is odd. Let $p+\frac12$ be $K$’s $x$-coordinate. Then $K$ is obscured if and only if $2\cdot \left(p +\frac12 \right)$ contains a factor of $l$.

Using this lemma it is easy to solve the problem. Of course, we are only interested in corners of type $A$; these corners have $x$-coordinates of the form $x =\frac12 + 1 + 3j$, $j \in \mathbb{Z}$. Remember it must be $x \leq \frac{n}{2}$, or $2x \leq n$. We are thus interested in finding all numbers of the form $6j+3$ that are $\leq n$ and that are coprime to $n$.

A computer search can solve this in no time, and finds $1264940$ solutions, so that the total is twice that much, or $2529880$. Using modular arithmethic and inclusion-exclusion, it’s actually not too hard to do it by hand; I’ve done it and got the same result.

$\endgroup$
  • $\begingroup$ Yes, this is what I got. @user3294068 was very close to the correct answer, but you nailed it. Good job, both of you! $\endgroup$ – Carl Löndahl Jan 28 '16 at 21:15
6
$\begingroup$

Updated, calculating paths only to A, rather than to any corner.

Calculating the number of paths where the ball does not visit A before the 20160127th bounce...

Define the side-length of the triangle as 1 unit.

Working my way up from small numbers. There is obviously exactly one path where the ball bounces one time before returning to A: straight down the middle.

If the walls were replaced with mirrors, the paths would be beams of light, reflecting off the mirrors. There will be many virtual images of point A. There will also be virtual images of B and C, but we are not interested in those.

Straight down the middle, there is a virtual image of A on the far side of a triangle 2 units in length. One the far side of the triangle 3 units in length, there are two images of corners, but those are B and C (see image, below). On the far side of the triangel 4 units in length, there will be 3 images, but the central one is obscured. All images

The red lines point to images of corner A, green lines to B, blue lines to C.

In general, for a triangle of length L, there will be L-1 images. But some of these will be hidden behind other images. The number of unobstructed images will be the number of integers less than L that are relatively prime with L. This is Euler's function $\phi(L)$.

As can be seen by following any of the lines in the image, the path from A to a virtual image on triangle L passes through $2L-3$ mirrors. Thus, a path that requires $20160127$ bounces must lead to an image on triangle $L = 10080065$.

The number of unobstructed images on that virtual triangle is $\phi(10080065) = 7589632$. Thanks to Euler Totient Calculator.

But we are only interested in images of A. For $L = 2, 5$, the leftmost and rightmost images are of A. In general, for $L = 3*i -1$, there will be $i$ images of A. Since $10080065 = 3*3360022 - 1$, that triangle will have $3360022$ images of A. Now to determine how many are unobstructed.

We can factor $10080065 = 5 \times 17 \times 118589$. Thus, on that triangle, every $5^{th}$, every $17^{th}$ and every $118589^{th}$ image will be obscured.

Images of A repeat with every $3^{rd}$ image, starting with the first and ending with the last. Since $3$ is relatively prime to each of the factors of $10080065$, each of the three corners will have its images obscured equally. The exception is A, which has an extra image.

Thus, the number of images of A that are not obscured = $(7589632 -1)/3 + 1 = 2529878$.

In summary,

  • The size of the triangle that has images which are reached after $20160127$ reflections is $L = 10080065$.
  • The number of images of A at that distance is $(L+1)/3 = 335062$.
  • The number of unobscured images of any corner at that distance is $\phi(L) = 7589632$.
  • The number of unbscured images of A at that distance is $(\phi(L) -1)/3 + 1 = 2529878$.

So the number of paths that reach A after 20160127 bouncess is 2529878.

$\endgroup$
  • $\begingroup$ This is clearly onto something, but it needs a lot of clarity especially near the end. $\endgroup$ – Fimpellizieri Jan 26 '16 at 17:32
  • $\begingroup$ Not quite. The idea of using an infinite grid of triangles is certainly a good way of viewing the problem, but you still have some way to go. $\endgroup$ – Carl Löndahl Jan 26 '16 at 17:44
  • $\begingroup$ I hope this version is more clear. Also corrected to find unboscured images of A. Forgot a step last time. $\endgroup$ – user3294068 Jan 26 '16 at 18:00
  • 1
    $\begingroup$ I got $2529880$, which is very close to yours so must be you or I made a small mistake not considering one of the cases. $\endgroup$ – Fimpellizieri Jan 27 '16 at 4:02
  • 1
    $\begingroup$ @Fimpellizieri I see... well, kind of hard for me to verify :-) This post is clearly onto something, so I will wait some week or so before posting anything more. $\endgroup$ – Carl Löndahl Jan 28 '16 at 8:07

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.