10
$\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$
6
  • $\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$ Commented Jan 26, 2016 at 14:57
  • $\begingroup$ @SpiritFryer No $\endgroup$ Commented Jan 26, 2016 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$ Commented Jan 26, 2016 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
    Commented Jan 27, 2016 at 5:08
  • 1
    $\begingroup$ @aroth Clearly, it is a very special ball :-) $\endgroup$ Commented Jan 27, 2016 at 8:57

2 Answers 2

4
$\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 \iff m(2p+1) = n\cdot 2q\tag{1}$$

Notice that regardless of the situation, $2q \in \Bbb Z$.

Claim: Let $K$ be a corner on a level $n$ triangle, where $n>2$ is odd. Let $p+\frac12\in \Bbb Z +\frac12$ be $K$’s $x$-coordinate. Then $K$ is obscured if and only if $2p+1$ contains a factor of $n$.

Proof: Consider equality $(1)$ in terms of prime decomposition: if $2p+1$ did not contain any of $n$'s prime factors, then they would all show up on $m$'s prime factors, which would contradict $m<n$. It follows that whenever the equality holds, $2p+1$, contains a factor of $n$.

Now, suppose $2p+1 = c\cdot f$, where $f\geqslant 3$ divides $n$. Observe that $2p+1$ and $n$ are odd, so the assumption $f\geqslant 3$ is justified. We consider cases.

If $m$ is even, then $q\in \Bbb Z$ and we pick $m = \frac {2n}f$ and $q = c$. Because $f\geqslant 3$, it holds that $m< n$. With this in mind, we have

$$q \leqslant m/2 \iff c \leqslant n/f\iff 2p+1 = cf \leqslant n,$$

which is true by hypothesis.

If $m$ is odd, then $q\in \Bbb Z+\frac12$ and we pick $m = \frac nf$ and $2q = c$. Once again, $f\geqslant 3$, so $m< n$. Finally,

$$q \leqslant m/2 \iff 2q \leqslant m \iff c \leqslant n/f \iff 2p+1 = cf \leqslant n,$$

which once again is true by hypothesis and concludes the proof. $\square$


Using the claim 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$
1
  • $\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$ Commented Jan 28, 2016 at 21:15
8
$\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$
7
  • $\begingroup$ This is clearly onto something, but it needs a lot of clarity especially near the end. $\endgroup$ Commented Jan 26, 2016 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$ Commented Jan 26, 2016 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$ Commented Jan 26, 2016 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$ Commented Jan 27, 2016 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$ Commented Jan 28, 2016 at 8:07

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