Bouncing Inside a Triangle

The problem does not need to be in Computer Science. I solved it with just a sheet of graph paper.

The triangle is repeatedly reflected over its sides until the full vector is drawn. At this point, we can see 19 walls have been crossed (reflected over). I made these walls thick red. The colors of the triangle are to keep track of the orientation of the triangle. The blue ones are mirror images of the pink ones. Because the vector ends in the blue, the ball hasn't actually reached (0.3,0.5) but rather (0.5,0.3) and is traveling upward relative to the original triangle. This means it would take a further 19 bounces to return the ball to its original position. It's possible but not easy to count these 38 bounces in the original picture.

1000 divided by 38 is 26 with remainder 12. So all we really need now we need the position of the 12th bounce. Again, counting carefully you can see this bounce in the original picture. It's on the x-axis just below 0.5 I've marked it on my picture with a green dot.

The vector is the line with equation $y-0.5=\frac{-7}{5}(x-0.3)$ and we can see the point we're looking for is on the line $y=-4$

Solving gives $x=\frac{123}{35}=3+\frac{18}{35}$ .

Since this point is on a blue reversed triangle, relative to the original (0.0) is the lower right corner and (0,1) is to the left. So we need to reverse $\frac{18}{35}$ to $\frac{17}{35}$ . The point on the original triangle has coordinates $(0,\frac{17}{35})$ and the solution is $\lfloor 1000(0+\frac{17}{35})\rfloor = \boxed{485}$

An attempt to generalize the 2D problem for a convex hull. The set of boundaries can be defined as:

$\displaystyle B = \begin{cases} y_1 = a_1+b_1 x \\ y_2 = a_2+b_2 x \\ \quad \quad \vdots \\ y_n = a_n+b_n x \end{cases}$

The initial conditions are:

$\displaystyle P_0 = (p^{(0)}_x, p^{(0)}_y)$

$\displaystyle V_0 = (v^{(0)}_x, v^{(0)}_y)$

The slope of the line $l_k$ passing through $P_k$ and parallel to $V_k$ is $\displaystyle m_k = \frac{v^{(k)}_y}{v^{(k)}_x}$ , hence the line itself is

$l_k = m_k(x - p^{(k)}_x) + p^{(k)}_y$

The set $C_k$ of possible $P_{k+1}$ candidates is

$\displaystyle C_k = \left\{(c^{(k, j)}_x, c^{(k, j)}_y) = \left(\frac{a_j - p^{(k)}_y+m_k p^{(k)}_x}{m_k-b_j}, a_j + b_j\frac{a_j - p^{(k)}_y+m_k p^{(k)}_x}{m_k-b_j}\right) \bigg| c^{(k, j)}_x \in \left[ \min_{j} \left(-\frac{a_j}{b_j}\right), \max_{j} \left(-\frac{a_j}{b_j}\right) \right], \ c^{(k, j)}_y \in \left[ \min_{j} a_j, \max_{j} a_j \right] \right\}$

In other words, each candidate $c^{(k, j)}$ results from the intersection of $P_k$ with the $j$ -th line in $B$ . But the resulting point could end up out of the hull. That is why we need to check whether the components of $c^{(k, j)}$ are inside the region, that is delimited by the highest and lowest intersection of the lines in $B$ with the $y$ axis and the rightmost and leftmost intersection with the $x$ axis.

Among all the candidate points in $C_k$ , $P_{k+1}$ will be the one pointed by the vector $V_k$ . All the points in $C_k$ , in fact, lay on $l_k$ , but we have to pick the one which is oriented in the sense of $V_k$ . So,

$\displaystyle P_{k+1} = c^{(k,j)} \in C_k \ \text{s. t.} \ \text{sgn}(c^{(k, j)}_x - p^{(k)}_x) = \text{sgn}(v^{(k)}_x), \ \text{sgn}(c^{(k, j)}_y - p^{(k)}_y) = \text{sgn}(v^{(k)}_y)$

As for $V_{k+1}$ , we need to find the new vector resulting from the bounce. If the point bounces on the $x$ axis,

$\displaystyle V_{k+1} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} v^{(k)}_x \\ v^{(k)}_y \end{pmatrix} = S \cdot V_k = (v^{(k)}_x, -v^{(k)}_y)$

So, we could rotate each line into $y=0$ , change the sign of the $y$ coordinate of $V_k$ and rotate the line again to the initial position. Each line in $B$ makes an angle $\theta_j$ with the $x$ axis, that is

$\displaystyle \theta_j = \tan^{-1}(b_j)$

Given the rotation matrix $R(\theta)$

$R(\theta) = \begin{pmatrix} \cos{\theta} & -\sin{\theta} \\ \sin{\theta} & \cos{\theta} \end{pmatrix}$

the vector $V_{k+1}$ is

$\displaystyle V_{k+1} = \big(R(-\theta) \circ S \circ R(\theta)\big)(V_k) = \begin{pmatrix} \cos{\theta} & -\sin{\theta} \\ \sin{\theta} & \cos{\theta} \end{pmatrix} \left[ \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \left[\begin{pmatrix} \cos{(-\theta)} & -\sin{(-\theta)} \\ \sin{(-\theta)} & \cos{(-\theta)} \end{pmatrix} \begin{pmatrix} v^{(k)}_x \\ v^{(k)}_y \end{pmatrix}\right] \right]$