The Sierpinski Gasket "Chaos Game" Challenge Analysis
The Sierpinski Gasket "Chaos Game" challenge is played on a level-$n$ stage of the Sierpinski gasket construction. Begin with an equilateral triangle with vertices $V_1$ (top), $V_2$ (bottom-left), and $V_3$ (bottom-right). Subdividing recursively as in the construction of the Sierpinski gasket, at level $n$ the figure contains $3^n$ small upward-pointing triangles, each with side length $\tfrac{1}{2^n}$ of the original. One of these small triangles is designated the target. A point starts at one of the vertices of the equilateral triangle. On each move the player chooses a vertex $V_i$, ${i\in\{1,2,3\}}$, and the point moves to the midpoint of its current position and $V_i$. The player wins when the point first enters the interior of the target triangle.
Claim The minimum number of moves required to guarantee that some target triangle in the level-$n$ game can be reached is ${n+2}$. More precisely:- No sequence of $n+1$ or fewer moves can place the point in the interior of any level-$n$ small triangle.
- For every level-$n$ small triangle there exists a sequence of exactly ${n+2}$ moves that places the token in its interior.
Barycentric Coordinates.
Every point $P$ in the plane of a triangle can be written uniquely as \[ P = \alpha V_1 + \beta V_2 + \gamma V_3, \qquad \alpha + \beta + \gamma = 1,\quad \alpha,\beta,\gamma \ge 0. \] The triple $(\alpha,\beta,\gamma)$ are the barycentric coordinates of $P$ with respect to the triangle.
Level 2
The figure below shows the 9 gray subtriangles for the level-2 stage in the construction of the Sierpinski gasket. The edges of these subtriangles are parallel to the sides of the equilateral triangle and each edge corresponds to where one of the barycentric coordinates is a constant multiple of $\frac{1}{4}$.
The red edges are where $\alpha$ is equal to $1$ at vertex $V_1$ and then moving towards the bottom edge of the equilateral triangle, $\frac{3}{4}$, $\frac{2}{4}$, $\frac{1}{4}$, and finally 0 at all points along the bottom edge. Similarly, the blue edges correspond to where $\beta$ decreases 1,$\tfrac34$,$\tfrac24$,$\tfrac14$,0 from $V_2$ to the right edge of the triangle, and the green edges correspond to where $\gamma$ decreases from 1 to 0 in the same way from $V_3$ to the left edge of the triangle.
In particular this means that a point in the level-2 Sierpinski gasket is in the interior of some level-2 subtriangle if and only if none of its barycentric coordinates is an exact multiple of $\frac{1}{4}$.
Suppose the initial point is $P_0 = V_{k_0}$ and the first three vertices chosen to play the game are $V_{k_1}$, $V_{k_2}$, and $V_{k_3}$. If we calculate the points using barycentric coordinates, we get $$\begin{align} P_0 &= V_{k_0} \\ P_1 &= \frac{1}{2}(P_0 + V_{k_1}) = \frac{1}{2}V_{k_0} + \frac{1}{2}V_{k_1} \\ P_2 &= \frac{1}{2}(P_1 + V_{k_2}) = \frac{1}{4}V_{k_0} + \frac{1}{4}V_{k_1} + \frac{2}{4}V_{k_2}\\ P_3 &= \frac{1}{2}(P_2 + V_{k_3}) = \frac{1}{8}V_{k_0} + \frac{1}{8}V_{k_1} + \frac{2}{8}V_{k_2} + \frac{4}{8}V_{k_3} \end{align} $$
Since each $V_j$ is a standard basis vector in barycentric coordinates, the barycentric coordinates of $P_n$ for $n \le 3$ have the form \[ \alpha = \frac{a}{2^n},\quad \beta = \frac{b}{2^n},\quad \gamma = \frac{c}{2^n}, \] for some non-negative integers $a, b, c$ with $a + b + c = 2^n$. In general, after exactly $n$ moves, the point's barycentric coordinates can be written as fractions over $2^n$, where the numerators are non-negative integers summing to $2^n$.
We see that after both the first and second moves, each barycentric coordinate of the new point is a multiple of $\tfrac{1}{4}$, and thus the point is on the edge (actually a vertex) of a subtriangle. After three moves, the point has coordinates $\left(\frac{a}{8},\frac{b}{8},\frac{c}{8}\right)$ for some non-negative integers $a, b, c$ with $a + b + c = 8$. Because 8 is even, at least one of $a$, $b$, or $c$ must also be even. But then the corresponding coordinate will be a multiple of $\frac{1}{4}$, and so the third point also lies on the edge of a subtriangle. Thus no sequence of 3 or fewer moves can place a point in the interior of any level-$2$ small triangle.
Example. Suppose the initial point $P_0 = V_1$ and the moves are towards vertices $V_3$, $V_2$, and $V_3$. The first three points are
After 4 moves the coordinates are of the form $(a/16, b/16, c/16)$ with $a+b+c = 16$. The point is in the strict interior of a level-$2$ cell if and only if none of $a, b, c$ is a multiple of $4$ (since a multiple of 4 over 16 equals a multiple of $\tfrac14$). The parity obstruction of $n=3$ no longer applies. For example, if in the example above move 4 is towards $V_2$, then $P_4 = \left(\frac{1}{16},\frac{10}{16},\frac{5}{16}\right)$. Here $1+10+5 = 16$, where one numerator is even but none is divisible by 4, so $P_4$ is in the interior of one of the subtriangles as shown in the figure below, confirming that 4 moves suffice for this example.
To show that every target is reachable in 4 moves starting at vertex $V_{k_0}$, note that the set of points reachable in exactly $4$ moves is \[ \mathcal{R}_4 = \left\{ \frac{V_{k_0}}{16} + \sum_{i=1}^{4} \frac{V_{k_i}}{2^{5-i}} : k_i \in \{1,2,3\} \right\}, \] a set of $3^4 = 81$ points distributed throughout the triangle. One can verify by direct enumeration [Python code] that for every one of the 9 small triangles in the level-2 gasket, exactly two of these 81 points fall in the interior of the triangle. In the following figure the 18 interior points are plotted when starting at the initial vertex $V_1$, $V_2$, or $V_3$. Click the button below the figure for the particular initial vertex.
Since there are two points in each small triangle, there are actually two ways to move a point from the initial vertex into the interior of a target triangle in 4 moves.
Level $n$
For the level-$n$ Sierpinski gasket, the original equilateral triangle has been scaled by $\frac{1}{2^n}$. The edges of the $3^n$ subtriangles in the gasket are parallel to the sides of the large triangle and each edge corresponds to where one of the barycentric coordinates is a constant multiple of $\dfrac{1}{2^n}$.
Therefore a point in the level-$n$ Sierpinski gasket is in the interior of some level-$n$ subtriangle if and only if none of its barycentric coordinates is an exact multiple of $\dfrac{1}{2^n}$.
A sequence of $m$ moves is a tuple $M = (k_1, k_2, \ldots, k_m) \in \{1,2,3\}^m$ where move $i$ is half-way towards vertex $V_{k_i}$. Starting from $V_{k_0}$ and applying $m$ half-steps, the resulting point has barycentric coordinates $$ P(M) \;=\; \frac{V_{k_0}}{2^{m}} + \sum_{i=1}^{m} \frac{V_{k_i}}{2^{m+1-i}} = \left(\frac{a}{2^m}, \frac{b}{2^m},\frac{c}{2^m} \right) $$ for non-negative integers $a$, $b$, and $c$ with $a+b+c = 2^m$.
If $m \le n$, then each coefficient in $P(M)$ is a multiple of $\frac{1}{2^n}$. Therefore the point is on the edge (actually a vertex) of a subtriangle of the level-$n$ gasket for each of the $m$ moves for $m \le n$. After $m = n+1$ moves, the point has barycentric coordinates of the form $$\left(\frac{a}{2^{n+1}}, \frac{b}{2^{n+1}},\frac{c}{2^{n+1}}\right).$$ Since $a+b+c = 2^{n+1}$, at least one of these numerators is even. But then the corresponding coefficient will be a multiple of $\frac{1}{2^n}$, so the point will not be in the interior of a subtriangle, but rather on one of the edges. Thus no sequence of ${n+1}$ or fewer moves can place a point in the interior of any level-$n$ small triangle.
To show that every target is reachable in ${n+2}$ moves starting at a vertex $V_{k_0}$, note that the set of points reachable in exactly ${n+2}$ moves is \[ \mathcal{R}_{n+2} = \left\{ \frac{V_{k_0}}{2^{n+2}} + \sum_{i=1}^{n+2} \frac{V_{k_i}}{2^{n+3-i}} : k_i \in \{1,2,3\} \right\}, \] a set of $3^{n+2}$ points distributed throughout the triangle. For the cases $n=3$, $n=4$, and $n=5$ in this particular Sierpinski Gasket Chaos Game challenge, we can again compute all the possible points [Python code] in $\mathcal{R}_{n+2}$ and plot those that are in the interior of a small triangle in the level-$n$ gasket. Below are the plots when starting at the initial vertex $V_1$.
There are two points in each small triangle in level 3 (54 plotted points), level 4 (162 plotted points), and level 5 (486 plotted points), which take 5, 6, and 7 moves, respectively. The plots when starting at $V_2$ and $V_3$ are similar. Thus every small triangle in the level-$n$ gasket for ${n=3, 4, 5}$ can be reached in $n+2$ moves.
The enumeration method does not work well, however, to show that for every level-$n$ small triangle there exists a sequence of exactly ${n+2}$ moves that places an initial vertex point into its interior, or why the minimum has the form $n+2$. That is best done by considering the three functions \[ f_j(P) = \frac{P + V_j}{2}, \quad j \in \{1, 2, 3\}, \] each of which sends any point $P$ to the midpoint between $P$ and vertex $V_j$. A single move toward $V_j$ in the game is precisely an application of $f_j$. These three functions constitute an iterated function system for the Sierpinski gasket. The details are left to the reader since understanding how the IFS can be used to prove the sufficiency of $n+2$ moves for the level-$n$ game might suggest an algorithm for how to play and win the game. It might also explain why there are exactly 2 winning sets of moves when given a particular target triangle and initial vertex no matter the level of the game.
