United States Mathematical Olympiad 2020.

This might seem like a difficult problem at first, but it's rather easily done using recurrence relations.

Let $A_{n}$ denote the number of ways to make two (seperate) laps around a circle with $n$ dots on it, such that no move is made in both laps. When I say "seperate", I mean the two laps each start and end at the marker point. Note that $A_0=1$ .

Let $a_{n}$ denote the number of ways to make two nonseperate laps around a circle with $n$ dots on it, such that no move is repeated, i.e. the first lap needn't necessarily end on the marker point.

We'll first find a recurrence relation for $A_{n}$ :

Let the first lap start with a $1$ , i.e. the first move progresses 1 point. Then the second lap must start with a $2$ . If the first lap's second move is a $1$ , we have $A_{n-2}$ ways to finish out the two laps. If the first lap's second move is a $2$ , we're in essentially the same case as just before, except we've already covered one extra point. Continuing on in this fashion, we see that $A_{n}=2\cdot(A_{n-2}+A_{n-3}+\dots+A_{0})$ . The factor 2 comes from the fact that if we replace the first lap with the second and the second with the first, we get all the variants in which the first lap starts with a $2$ instead. Solving this recurrence relation gives:

$\displaystyle A_{n}=\frac{2^n+2\cdot(-1)^{n}}{3}$ .

Now to find $a_{n}$ :

After the first lap is completed, we have either stopped at the marker point, yielding $A_{n}$ solutions, or we have jumped over the marker point. In this case, (following a very similar thought process as in the $A_{n}$ case) if our first move was $1$ , we have $A_{n-1}$ ways to finish. If it was $2$ , we have $2(A_{n-2}+A_{n-3}+\dots+A_{0})=A_{n-1}$ solutions. Adding these up, we get:

$a_{n}=A_{n}+2\cdot A_{n-1}+=\displaystyle\frac{2^{n+1}-2\cdot(-1)^{n}}{3}$ .

Substituting, we get $\displaystyle\frac{a_{2020}+a_{2019}}{a_{2017}+a_{2016}}=8$ .

Let $n \geq 4$ and start with a $2 \times n$ array of open points. As the marker moves around the circle the first time, record the points on the circle that the marker visits by filling in points in the first row, and do the same in the second row as the marker moves around the circle the second time. The figure below shows such a representation when the marker skips a point, skips another point, moves to the next point, skips a point, and moves to the next point. $\begin{matrix} \circ & \bullet & \circ & \bullet \\ \bullet & \circ & \bullet & \bullet \end{matrix}$ This example has three column types: open-closed (oc), closed-open (co), and closed-closed (cc). Arrays representing valid paths will only have these three column types because open-open columns represent places where the marker repeats a previous move or skips more than one point. Four more things can be said about the columns in arrays that represent valid paths:

(a) the $n$ th column is oc or cc;

(b) no column type appears twice in a row;

(c) if the $n$ th column is oc, then the first column cannot be be co; and

(d) if the $n$ th column is cc, the first column cannot be cc.

The number of $n$ -column arrays that satisfy (a) through (d) is $a_n$ . Counting arrays that meet requirements (a) and (b) is easy. There are two choices for the $n$ th column that satisfy (a), and for each other column, there are two choices that satisfy (b), so altogether there are $2^n$ such arrays. Notice that an $n$ -column array satisfies (a) and (b) but not (c) or (d) if and only if removing the first column produces an $(n - 1)$ -column array that satisfies (a) through (d). Therefore, the number of arrays that satisfy (a) and (b) but not (c) or (d) is $a_{n - 1}$ , and hence $a_n + a_{n - 1} = 2^n.$ Applying this relationship leads to the desired value: $\frac {a_{2020} + a_{2019}} {a_{2017} + a_{2016}} = \frac {2^{2020}} {2^{2017}} = 2^3 = \boxed{8}.$