darnit MAA why were #2, #3 so much harder than #1 ~_~

^I solved 2 and most of 3 but failed #1

I showed $ a_n=a_{n-1} + 2 * a_{n-2} $ and it fell from there

Note that the typo "Let $a_n$ count the number the number of ways" was on the USAMO paper. Not my fault.

I noticed that too.

Huge recursion solution (remnants of a bijection attempt) took 4 pages but worked

Showed the recursive formula an = an-1 + 2an-2, used induction -> base case: show a4 = 16 (a4 = 11, a3 = 5), then by induction proved an + an-1 = 2^n

Does this work? Label each point 1 or 2, and for every point move the labeled number of points forward if it's the first time you visit the point, and the other move if you're visiting the point a second time. The path ends either on A or on the point right after A. In the first case, there are a_n paths, and in the second case, there's a bijection to the a_(n-1) paths that work for n-1 points by just removing the point right before A.

@above, I did the same thing.

If we have a set of points like S1,S2,S3....Sn-1 could you use casework on S1 going to S2(giving a_n-2 comibinations for if the point returns back to S1 and a_n-2 combinations for if the point returns back to S_n-1). What I said I was doing was essentially getting rid of two of the points out of n depending on the case. I did something similar for a_n-1. Not sure if it works. Can anyone tell me?

I had a random bijection: a_n is the number of strings containing only 1s and 2s all summing up to $2n$ such that for any substring that sums to $n$ (these exist always), the number directly to the right of that substring (which might not exist) does not equal the first character in the substring. I couldn't produce anything with this though. Perhaps someone else can extract an nicer solution out of it. Comment: The number of such strings without the substring condition turns out to be F_(2n+1).

/Didn't take the contest, but here's a solution anyways

By expanding the points traveled on a n-point circle along a line, we have 2n+1 points, observe n=3 ....... n=4 ......... hence the recurrence: a_n=2*a_{n-1} Let induction do rest of the work.

@ALvez then $3|a_n+a_{n-1} \neq 2^n$

anchenyao wrote: @ALvez then $3|a_n+a_{n-1} \neq 2^n$ I didn't see the part about " without repeating a move" It doesn't work then.

also, if it were allowing move repetitions the answer would simply be the $2n$th fibonacci number (well depending on how you index things)

anchenyao wrote: ^I solved 2 and most of 3 but failed #1

Same! Although I did casework for the first move.

Here's another approach, significantly uglier but more straightforward.

ophiophagous wrote: Does this work? Label each point 1 or 2, and for every point move the labeled number of points forward if it's the first time you visit the point, and the other move if you're visiting the point a second time. The path ends either on A or on the point right after A. In the first case, there are a_n paths, and in the second case, there's a bijection to the a_(n-1) paths that work for n-1 points by just removing the point right before A. Can somebody please explain why the bijection to a_(n-1) paths works.

I will only explain the steps in my solution it;s kinda long and uses lots of recursive formulas. I proved the recursion formula by letting $b_n$ be the number of such paths that pass through $A$ after one cycle and $c_n$ the ones that don't. Then $a_n=c_n+b_n$ and for $b_n$ we easily find a recursive formula by considering the first point after $A$(clockwise) that the marker passess twice. So $b_n=2(b_{n-2}+b_{n-3}+....+b_1)$ Now this gives $b_n-b_{n-1}=2b_{n-2}$ giving the wanted formula for $b_n$ but we need it for $c_n$ as well. This can be accomplished similarly by considering the last point before $A$ and first point after $A$ where the marker passess twice. This proves $2(c_{2k+1} - c_{2k})=b_{2k-1}+2$ and $2(c_{2k}-c_{2k-1})=b_{2k-2}-2$. Now we can prove by induction \[b_{2k-1}+2=4c_{2k-1},b_{2k-2}-2=4c_{2k-2}\] This gives the result $c_n-c_{n-1}=2c_{n-2}$ for all $n$ giving the desired result

Sorry to revive this thread, but I can't understand what the problem means by "without repeating a move". Does it mean that after the marker is moved one unit forward, it has to be moved two units forward (and vice-versa)? Doesn't the whole path get determined by the starting move then?

No, it means that if you move forward one from some point, if you return to that point then you must move forward 2. That is, if you go all the way around the circle and hit the point again, then you must choose the other of $1$ and $2$ to move forward.

Yoshi wrote: By treating the node just before $A$ as an alternative start node, the circle passes through n-1 numbers, ends at a start node, then makes a second pass through n-1 numbers ending at a start node. This path then represents that of one drawn out for a circle of size $n-1$. Can anyone explain what this means and why this is true? Thanks a lot!

Anyone? Thanks.

Label each point with the number of times the marker is on it not counting the starting position. Every point must have the marker at some point because otherwise the move from the point before it to the point after it would be made twice. Hence, every point has 1 or 2 since the marker goes around the circle twice. Also, we can't have two consecutive points both labelled 2, because that would mean that on both times around the circle the marker moved from one point to the other, which is a repeated move. Now, we will split into two cases, first if $A$ is labelled 2. Given any two consecutive 2-labelled points, the paths the marker takes the first and second time must intersect only at those two points and not in between. Hence, two consecutive points in between the two points cannot both be on one path, because the other path will have to contain one of them otherwise. This results in two ways to get from the first 2-point to the next. Either move the marker by 1, 2, 2, ... or by 2, 2, 2, ... and making the appropriate move at the end to get onto the second 2-point. Whichever way the marker goes the first time, it must go the other way the second time. Hence, if there are $k$ points labelled with 2 on the circle, there are $2^k$ paths. The number of ways to choose $k$ non-consecutive points including $A$ on the circle is $\binom{n-k-1}{k-1}$, so there are $\sum_{k=1}\binom{n-k-1}{k-1}2^k$ ways. For the second case, $A$ is not labelled with 2. The argument for consecutive 2-points that do not have $A$ between them is the same. We will show that there is exactly one way to move between consecutive 2-points that have $A$ between them. Suppose that the closest two 2-points to $A$ are $B$ and $C$, where $B\rightarrow A\rightarrow C$ is in the clockwise direction. Merge the path from $A$ to $C$ at the start and the path from $B$ to $A$ at the end. This creates two paths from $B$ to $C$ that cannot intersect. As in the last case, there are two such choices for one of these paths. However, one of them must pass through $A$, so this uniquely determines the other path as well. Hence, there will be $2^{k-1}$ paths if there are $k$ 2-points. Since there are $\binom{n-k}{k}$ ways to choose $k$ non-consecutive points not including $A$ on the circle, there are $\sum_{k=1}\binom{n-k}{k}2^{k-1}$ ways for this case. For the final case, we consider if there are none of the points are labelled with 2. If this happens, every point is visited exactly once. The marker travels a total distance of $2n$. If every point is visited exactly once, then it makes exactly $n$ moves, so on each of those moves it must travel a distance of 2. However, if $n$ is even this obviously brings it back to $A$, but if $n$ is odd then this becomes a valid path. So if $n$ is odd then $a_n=1+\sum_{k=1}\binom{n-k-1}{k-1}2^k+\binom{n-k}{k}2^{k-1}$ and if $n$ is even then $a_n=\sum_{k=1}\binom{n-k-1}{k-1}2^k+\binom{n-k}{k}2^{k-1}$. Substituting the sums into $a_n+a_{n-1}=2^n$, we find an identity that can be easily proven by induction.

Imagine the counter is moving along the set $S = \{0, 1, \dots, 2n\}$ instead, starting at $0$ and ending at $2n$, in jumps of length $1$ and $2$. We can then record the sequence of moves as a matrix of the form \[ \begin{bmatrix} p_0 & p_1 & p_2 & \dots & p_{n-1} & p_n \\ p_n & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & p_{2n} \end{bmatrix} \]where $p_i$ denotes whether $i$ was used; in particular, $p_0 = p_{2n} = 1$. (Note that the upper-right and lower-left entries are equal.) Then, the problem amounts to finding the number of such matrices which avoid the contiguous submatrices \[ \begin{bmatrix} 0 & 0 \end{bmatrix} \qquad \begin{bmatrix} 0 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \]which correspond to forbidding jumps of length greater than $2$, repeating a length $2$ jump and repeating a length $1$ jump. We will for now ignore the boundary conditions. Instead we say a $2 \times m$ matrix is silver ($m \ge 2$) if it avoids the three shapes above. We can classify silver matrices into two shapes: type B matrices, of the shape $\begin{bmatrix} 1 & \dots & 1 \\ 0 & \dots & 0 \end{bmatrix}$, and type C matrices, of the shape $\begin{bmatrix} 1 & \dots & 0 \\ 0 & \dots & 1 \end{bmatrix}$. We let $b_m$ and $c_m$ denote matrices of each type, of size $2 \times m$, and claim the following two recursions for $m \ge 4$: \begin{align*} b_m &= c_{m-1} + b_{m-2} + c_{m-2} \\ c_m &= b_{m-1} + b_{m-2} + c_{m-2}. \end{align*}We prove the first recursion since the second is analogous. Consider the second column of a type B matrix. If it is $\left[ \begin{smallmatrix} 0 \\ 1 \end{smallmatrix} \right]$ then we find a type C matrix, giving $c_{m-1}$. If it is $\left[ \begin{smallmatrix} 1 \\ 1 \end{smallmatrix} \right]$ then the third column must be either $\left[ \begin{smallmatrix} 0 \\ 1 \end{smallmatrix} \right]$ or $\left[ \begin{smallmatrix} 1 \\ 0 \end{smallmatrix} \right]$, and we get a count of $b_{m-2} + c_{m-2}$. Using this recursion, the first few values are \[ \begin{array}{rrrrrrrr} n & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline b_n & 0 & 2 & 2 & 6 & 10 & 22 & 42 \\ c_n & 1 & 1 & 3 & 5 & 11 & 21 & 43 \end{array} \]and a calculation gives $b_n = \frac{2^{n-1} - 2(-1)^{n-1}}{3}$, $c_n = \frac{2^{n-1} + (-1)^{n-1}}{3}$. We now relate $a_n$ to $b_m$ and $c_m$. Observe that a matrix as described in the problem is a silver matrix of one of two forms: \[ \begin{bmatrix} 1 & p_1 & p_2 & \dots & p_{n-1} & 0 \\ 0 & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & 1 \end{bmatrix} \qquad \text{or}\qquad \begin{bmatrix} 1 & p_1 & p_2 & \dots & p_{n-1} & 1 \\ 1 & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & 1 \end{bmatrix}. \]There are $c_{n+1}$ matrices of the first form and $2b_{n-1} + 2c_{n-1}$ matrices of the second form, thus calculation gives the result \[ a_n = c_{n+1} + 2b_{n-1} + 2c_{n-1} = \frac{2^{n+1} + (-1)^{n+1}}{3}. \]

For those who think that the above interpretation was magic. The motivation was to actually remove the circle. Because it was the main criminal, which was not allowing us to think. one actually realises that the only condition important is the repeatation of the $A$ the starting point.The rest of the proof is nothing but translating the language of the problem in terms of the number of moves. The next tedious part comes in guessing the formula. You can expect the formula to be almost the same and a few calculation shows that too.

Lemma: Every point is hit at least once in the sequence of moves. Proof: If a point $P_i$ wasn't hit the first time around, that means that a move of length 2 was performed from $P_{i-1}$. In the second revolution, if $P_{i-1}$ is hit, then a move of length 1 must be performed, meaning $P_i$ will be hit. Otherwise, $P_{i-1}$ was skipped (i.e. a move of length 2 was performed from $P_{i-2}$) which will still result in $P_i$ being hit. As a corollary, this means that any sequence of moves which skipped $A$ on its first revolution is a valid sequence. Now, consider a circle of $n$ points, and assign each point a number - either 1 or 2. Consider the move sequence: If a point has not been hit yet, move the amount of steps its number dictates. Otherwise, move the remaining move. As each point is hit during the sequence of moves, all $2^n$ of these numberings will create different move sequences. Suppose $a_n=k$ of these sequences end up landing on $A$ after exactly 2 revolutions. So, $2^n-k$ of them failed. Now, consider a circle of size $n+1$, with numbers also assigned to all of the points. We define the $n$-subgame of such a circle to be the result obtained from taking a circle of size $n$ with the first $n$ labels from the current circle. If the $n$-subgame skips $A$ on its first revolution, that means that it will skip the point before $A$ in the $n+1$ circle, so the point before $A$ will be hit on the second revolution. This means that it must be numbered with a 1. If the $n$-subgame hits $A$ on its first revolution, then it hits the point before $A$ on its first revolution in the $n+1$ circle. If we label the point with 2, then $A$ will be skipped for the first revolution, and this must be a valid sequence of moves. On the other hand, if we label it with a 1, then we don't affect the result of the $n$-subgame. So, if the $n$-subgame yielded a good sequence of moves, then we will end up on the point before $A$, causing this to be a bad sequence of moves. However, if the $n$-subgame was bad, then this results in hitting $A$ on the second revolution, so this is a good sequence. To recap, if the $n$-subgame is good, then we can only number the last point with a 1, and if it is bad, then we can number it with 1 or 2. (recall all subgames in the first case were good by lemma.) So, $a_{n+1}=k+2(2^n-k)=2^{n+1}-k$ as desired.

Let \(B\) be the point directly counterclockwise to \(A\). Claim: We land on each point either once or twice. Proof. If we never land on a point, then we jump over it twice. \(\blacksquare\) Consider a circle with \(n\) points and a marker labeled \(A\), and assign each point either the number \(1\) or the number \(2\); this may be done in \(2^n\) ways. Then proceed around the circle starting from \(A\), such that the first time the marker reaches a certain point labeled \(i\), it moves \(i\) points forward. (If it reaches a point labeled \(i\) a second time, its only option is to move forward \(3-i\) points.) The paths where we reach the point \(A\) the second time around biject with the \(a_n\) ways to advance around a circle with \(n\) points. If we do not reach the point \(A\) the second time around, then we must have jumped over \(A\) from \(B\). Just delete the point \(B\) completely; it is easy to see these paths bijects with the \(a_{n-1}\) ways to advance around a circle with \(n-1\) points. Hence \(a_n+a_{n-1}=2^n\) as needed.

Remark: Cool problem!!! Thankfully, this was not the recursion bash I thought it would be Also this is very similar to the solutions provided above by users TheUltimate123 and JSGandora. Label the points from $1$ to $n$ cycling modulo $n$. Notice that the marker must arrive at each point at least once because otherwise, it jumps over that point twice, which is not possible since that would be using the same move twice. Furthermore, if we arrive at a point $\geq 3$ times, then we use the jump $2$ or jump $1$ moves twice. Hence, each point is reached by the marker once or twice. Next we establish a bijection between $a_{n-1}$ and $a_n$. Label each point with either $1$ or $2$, and there are $2^n$ ways to do this. For each point, when it is reached the first time, the marker performs the move on the label, and the second time, it performs the move not on the label. We divide these $2^n$ ways of labeling into two groups: one group for those where the marker reaches $A$ twice, and another for when it reaches $A$ once. For the former group of labelings, we see that they biject to the $a_n$ ways to advance around a $n$ point circle. For the latter group of labelings, we see that they biject to the $a_{n-1}$ ways to advance around a $n-1$ point circle, because the move from $A-1$ to $A+1$ is fixed, hence the remaining $n-1$ points biject to $a_{n-1}$ ways. Therefore, $a_{n-1} + a_n = 2^n$ for all $n$, as desired.

This is not similar to the solutions above. Assign the points numbers $1,2,\dots,n$ modulo $n$. Within the context of the set of moves, let the points be enumerated as $1,2,\dots,n,n+1,n+2,\dots,2n,2n+1$. Clearly any interval $[a,a+1]$ is contained within exactly one move in a particular sequence of moves. Define a brick road as a collection of two sequences of moves going from $1\to n+1$ composed such that no two collections of moves contain the same particular individual move $a\to b$. Let the number of brick roads be $b_n$. Observe that $b_1=0$, $b_2=2$, Let index $i+1>1$ denote the first instance of the two sequences agreeing. If $i+1=n+1$ then we have $2$ cases for $b_n$. Else, we get $2b_{n-i}$ for $i>1$. Thus $b_n=2\cdot [1+\sum_{1<i<n}b_{n-i}] $. Counting, we get $b_3=2,b_4=6,b_5=10,b_6=22,b_7=42,\dots$. We claim in general that $b_n = 2\cdot \frac{2^{n-1}-(-1)^{n-1}}{3}$. This holds by induction, since then \[b_n = 2\cdot \left[1+2\cdot \frac{2^{n-2}-\frac 32-\frac 12(-1)^{n-1}}{3}\right] = 2\cdot \left[1+\frac{2^{n-1}-3-(-1)^{n-1}}{3}\right] = 2\cdot \frac{2^{n-1}-(-1)^{n-1}}{3}.\] Then $a_n$ is simply $b_n$ plus the number of sequences of moves from $1\to 2n+1$ which include $n\to n+2$. Now, observe there are a number of types of this: if $1\to 2$ is also one of the moves and so is $2n\to 2n+1$, this is simply $b_{n-2}$. If $1\to 2$ is a move and $2n-1\to 2n+1$ is a move, this is $\frac 12 b_{n-1}$. The same holds if $1\to 3$ is a move and $2n\to 2n+1$ is a move. So far we have then counted $b_n+b_{n-1}+b_{n-2}$ sequences. Now, suppose $1\to 3,n\to n+2,2n-1\to 2n+1$ are all moves. View the complete sequence of moves as a brick road. By selecting the first point at which the two sequences agree, we count $\frac 12\sum_{1<i<n}b_{n-i}$ possibilities. If there exists no such point, then $n$ must be odd, thus we count $\frac 12+\frac 12(-1)^{n-1}$ additional possible moves. Hence \[a_n = 2\cdot \frac{2^{n-1}+2^{n-2}+2^{n-3}-(-1)^{n-1}}{3} + \frac{2^{n-2}-\frac 32-\frac 12(-1)^{n-1}}{3}+\tfrac 12+\tfrac 12(-1)^{n-1}=\]\[\frac{7\cdot 2^{n-2}+2^{n-2}-\frac 32-\frac 52(-1)^{n-1}}{3}+\tfrac 12+\tfrac 12(-1)^{n-1} = \frac{2^{n+1}-(-1)^{n+1}}{3}.\]The problem is now dead because \[a_n+a_{n-1}=\frac{3\cdot 2^n}{3}=2^n.\]

jj_ca888 wrote: Remark: Cool problem!!! Thankfully, this was not the recursion bash I thought it would be Also this is very similar to the solutions provided above by users TheUltimate123 and JSGandora. Remark: Cool problem!!! Unfortunately, I couldn't find the creative solution I knew existed Also this is very similar to the solutions provided above by user GeronimoStilton. We first do some work to write $a_n$ in terms of a few simpler sequences. Observe that since our first move is from $A$, we either move once or twice from $A$. If we move twice from $A$, we can view the sequence of moves as a pair of two moves, each of length $n$, such that no move from the same point is the same. From here, we can discard the circle entirely and instead view the moves in terms of two horizontal bars filled with blocks of length 1 or 2 such that no two blocks are at the same length and the same spot. Here's an example: [asy][asy] size(150); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((0,2)--(6,2)--(6,3)--(0,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((2,2)--(2,3)); draw((3,2)--(3,3)); draw((5,2)--(5,3)); [/asy][/asy] Let the number of ways to fill a pair of bars, both with length $n$, be $b_n$. We will do the recursion work later. Now suppose we move once from $A$. If we let the point counterclockwise from $A$ be $B$, then it is clear that on the first cycle around the circle we reach $B$, then move two points forward from there, and after that move to $A$. Once again, we can discard the circle and view it in terms of bars, but this time the bars are offset from each other. [asy][asy] size(150); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((1,2)--(7,2)--(7,3)--(1,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((3,2)--(3,3)); draw((5,2)--(5,3)); [/asy][/asy] [asy][asy] size(150); fill((4,0)--(4,1)--(6,1)--(6,0)--cycle,red); fill((4,2)--(4,3)--(6,3)--(6,2)--cycle,red); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((1,2)--(7,2)--(7,3)--(1,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((3,2)--(3,3)); draw((4,2)--(4,3)); draw((6,2)--(6,3)); [/asy][/asy] In the examples above, the upper example is valid, but the lower is not since the two red blocks are the same length at the same spot. Let the number of ways to fill these two bars of length $n$ be $c_n$. It is clear that $$a_n=b_n+c_{n-1}.$$Finally, introduce the sequence $(d_n)$, which counts the number of ways to fill two bars: one of length $n$, and the other of length $n-1$. Here's an example: [asy][asy] size(150); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((0,2)--(5,2)--(5,3)--(0,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((2,2)--(2,3)); draw((3,2)--(3,3)); [/asy][/asy] Now that we've defined everything, it's time to do the recursion work. First consider $c_n$. Call the bar which is offset to the right the "right bar" and the other bar the "left bar". Consider the following cases: Case 1: The first block in the left bar is a block of length 1. Then we clearly have $d_n$ ways to fill the remaining blocks. Case 2: The first block in the left bar is a block of length 2, and the first in the right bar is of length 1. Then we clearly have $d_{n-1}$ ways to fill the remaining blocks. Case 3: The first blocks in the left and right bars are both of length 2. Then we have $c_{n-2}$ ways to fill the remaining blocks. Hence we have the recursion $$c_n=c_{n-2}+d_n+d_{n-1}.$$Now we establish a relationship between $b_n$ and $d_n$. By inspection, we can see that in one of the bars, the rightmost block is of length 1, and in the other the rightmost block is of length 2 (anything else breaks the condition). If we delete/ignore the rightmost blocks, we then get one bar of length $n-1$ and another of $n-2$. Since $d_n$ doesn't count alignment, but there are two distinct possiblities for orientation after deleting the rightmost blocks, we establish $b_n=2d_{n-1}$. Now we compute $b_n$. Consider the leftmost distance along the block, except from the very left of the block, where two blocks both end (this must exist, since two blocks both end at the right edge of the bar). Here, this distance is marked by the red line: [asy][asy] size(150); draw((0,0)--(6,0)--(6,1)--(0,1)--cycle); draw((0,2)--(6,2)--(6,3)--(0,3)--cycle); draw((1,0)--(1,1)); draw((2,0)--(2,1)); draw((4,0)--(4,1)); draw((2,2)--(2,3)); draw((3,2)--(3,3)); draw((5,2)--(5,3)); draw((2,-1)--(2,4),red); [/asy][/asy] It is not hard to see that it is impossible for this distance to be 1, and for any (integer) distance in $[2,n]$ there is exactly two ways to fill in the blocks to the left of this distance. Hence we have the recursion: $$b_n=2b_{n-2}+2b_{n-3}+\cdots+2b_0.$$Comparing $b_n$ and $b_{n-1}$ and subtracting, we obtain $$b_n-b_{n-1}=2b_{n-2} \implies b_n=b_{n-1}+2b_{n-2}.$$Further, it's not hard to compute $b_0=1$ (there is one way to fill in the empty bars: doing nothing), and $b_1=0$ (if necessary, you can also compute a bit more). From here, simple induction is sufficient to show that $$b_n=\frac{2}{3}(2^{n-1}+(-1)^n),$$which also gives $$d_n=\frac{1}{3}(2^n-(-1)^n).$$Using this, we can verify the identity $$b_n+b_{n-1}=2^{n-1},$$as well as $$d_n+d_{n-1}=2^{n-1} \implies c_n=c_{n-2}+2^{n-1}.$$Further, we can get $c_0=c_1=1$, so \begin{align*} c_{2m}&=2^{2m-1}+2^{2m-3}+\cdots+2^1+1\\ c_{2m+1}&=2^{2m}+2^{2m-2}+\cdots+2^2+1. \end{align*}We're actually done now, since \begin{align*} a_{n-1}+a_n&=b_n+b_{n-1}+c_{n-1}+c_{n-2}\\ &=2^{n-1}+2^{n-2}+2^{n-3}+\cdots+2^2+2^1+1+1\\ &=2^{n-1}+2^{n-1}=2^n.\quad \blacksquare \end{align*}

Hey look it's the precursor to samrocksnature @mobro!

AOPqghj wrote: Hey look it's the precursor to samrocksnature @mobro! ??? What is this supposed to mean @below oops I am observationally challenged

8charlimit

We populate a boolean $2 \times n$ grid where we write a $1$ if the marker touches that position. For example, in the $2 \times 5$ below for $n = 5$, $$\begin{bmatrix} 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 \end{bmatrix}$$this means we move along the circle $1 \to 2 \to 4 \to 1 \to 3 \to 4 \to 5 \to 1$. Each column of the grid cannot be $\begin{bmatrix} 0 \\ 0 \end{bmatrix}$, so it must be one of $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, or $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$. Furthermore, three more constraints apply: No two consecutive columns are allowed to repeat. A repeat of $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ corresponds to repeating the same move, and repeating a $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, or $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ means we jumped more than 2 spots. The first column must either be $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ or $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ If we start with $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, we cannot end with $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$. If we start with $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ we cannot end with $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$. My previous solution actually had a bug -- thanks to v_Enhance for catching it below!

So, we've reduced the problem to the following: we have three states, $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, and $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$. We must start on either $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ or $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$. Count the number of ways to hop $n - 1$ times between the states (without repeating a state), and end up on a spot that doesn't violate the third constraint above. This is a routine exercise in recursion: one systematic way to do this is to assume you start at $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, and define $x_k, y_k, z_k$ to be the number of ways to reach $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, and $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ respectively after $k$ hops. You would have \begin{align*} x_{k+1} &= y_k + z_k \\ y_{k + 1} &= x_k + z_k \\ z_{k + 1} &= x_k + y_k \end{align*}with initial conditions $(x_0, y_0, z_0) = (1, 0, 0)$. Repeat the exercise, but assume you start at $(1, 1)$, and stitch your results together. There's a couple of observations that will save us a lot of algebra though. Notice that there's a symmetry among the three states. Specifically, suppose if $x_k$ is the number of ways to start at $(1, 0)$, hop $k$ times, and end up at $(1, 0)$, then $x_k$ should also be the number of ways to start at $(1, 1)$, hop $k$ times, and end up at $(1, 1)$. Furthermore, you can also see that $y_k = z_k$, which can be proven by induction on $k$. Then, we just have \begin{align*} a_n &= x_{n-1} + y_{n-1} \qquad \text{start at (1, 0) end at (1, 0) or (1, 1)} \\ &+ y_{n-1} + z_{n-1} \qquad \text{start at (1, 1) end at (1, 0) or (0, 1)} \end{align*}Focusing on what the problem asks for: \begin{align*} a_n + a_{n - 1} &= x_{n-1} + 2y_{n-1} + z_{n-1} + x_{n-2} + 2y_{n-2} + z_{n-2} \\ &= (y_{n-2} + z_{n-2}) + 2(x_{n-2} + z_{n-2}) + (x_{n-2} + y_{n-2}) + x_{n-2} + 2y_{n-2} + z_{n-2} \\ &= 4(x_{n-2} + y_{n-2} + z_{n-2}) \\ &= 4 \cdot 2^{n-2} \\ &= 2^n \end{align*}as desired. Note that in the last step, we used the observation that $x_k + y_k + z_k = 2^k$, since this corresponds to just counting how many ways there are to hop $k$ times, and there are two choices at each hop. One can also just prove that from the recursion itself.

fclvbfm934 wrote: We populate a boolean $2 \times n$ grid where we write a $1$ if the marker touches that position. For example, in the $2 \times 5$ below for $n = 5$, $$\begin{bmatrix} 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 \end{bmatrix}$$this means we move along the circle $1 \to 2 \to 4 \to 1 \to 3 \to 4 \to 5 \to 1$. Each column of the grid cannot be $\begin{bmatrix} 0 \\ 0 \end{bmatrix}$, so it must be one of $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, or $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$. Furthermore, no two consecutive columns are allowed to repeat, including wraparound (meaning $n$-th column is not allowed to be equal to $1$-st column). One can easily check that these conditions alone are necessary and sufficient for a sequence being valid. I think the wraparound condition is not quite correct. As an example for $n=5$, the matrix \[ \begin{bmatrix} 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \end{bmatrix} \]corresponds to $1 \to 2 \to 4 \to 5 \to 7 \to 8 \to 9 \to 1$. I think this is a valid sequence of moves, but the first and and $n$th column are both $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$. This seems to cause some problems later, for example you wrote $a_n = 2x_n$ written, but I think \[ a_n = \frac{2^{n+1}+(-1)^{n+1}}{3} \]is actually odd for all $n \geq 3$. I think this is not too hard to fix. The symmetry observation is nice, and does lead to a shorter solution.

Here is what I think is a repaired version of the solution in post #39. (Note that in my write-up, the matrix has one extra redundant column compared to the notation in fclvbfm934's post). Record the sequence of moves as a matrix of the form \[ \begin{bmatrix} p_0 & p_1 & p_2 & \dots & p_{n-1} & p_n \\ p_n & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & p_{2n} \end{bmatrix} \]where $p_i = 1$ if the point $i$ was visited by the counter, and $p_i = 0$ if the point was not visited by the counter. Note that $p_0 = p_{2n} = 1$ and the upper-right and lower-left entries are equal. Then, the problem amounts to finding the number of such matrices which avoid the contiguous submatrices \[ \begin{bmatrix} 0 & 0 \end{bmatrix} \qquad \begin{bmatrix} 0 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \]which correspond to forbidding jumps of length greater than $2$, repeating a length $2$ jump and repeating a length $1$ jump. If we focus on just the three possible column vectors that appear, say \[ \mathbf u \coloneqq \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \qquad \mathbf v \coloneqq \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \qquad \mathbf w \coloneqq \begin{bmatrix} 1 \\ 1 \end{bmatrix} \]then we can instead describe valid matrices as sequences of $n+1$ such column vectors, where no two column vectors are adjacent, and where the boundary condition is that either we start with $\mathbf u$ and end with $\mathbf v$, or either we start with $\mathbf w$ and end with $\mathbf w$. Let $x_n$ and $y_n$ denote the number of such $2 \times (n+1)$ matrices. (Hence $a_n = x_n + y_n$.) But owing to the symmetry of the setup with $\mathbf u$, $\mathbf v$, $\mathbf w$, we could instead view $x_n$ and $y_n$ as the number of $2 \times (n+1)$ matrices for a fixed starting first column whose final column is the same/different. So we have the recursions \begin{align*} x_{n+1} &= x_n + y_n \\ y_{n+1} &= 2x_n. \end{align*}We also have that \[ 2x_n + y_n = 2^n \]which may either be proved directly from the recursions (using $x_0=1$ and $y_0=0$), or by noting the left-hand side counts the total number of sequences of $n+1$ column vectors with no restrictions on the final column at all (in which case there are simply $2$ choices for each of the $n$ columns after the first one). Thus, \begin{align*} a_{n+1} + a_n &= (x_{n+1} + y_{n+1}) + (x_n + y_n) \\ &= \left( (x_n + y_n) + 2x_n \right) + (x_n + y_n) \\ &= 2(2x_n + y_n) = 2^{n+1} \end{align*}as needed.

Oof yes, you are absolutely right. Thanks for catching this! I patched up my solution upon reading your find, but it looks like I ended up doing essentially the same thing as your fix, with the exception of the redundant column as you point out. I think I even like your redundant column more than mine, to be honest.

For each point, give them an instruction sheet: it is either "jump 1 now, jump 2 after" or "jump 2 now, jump 1 after". Notice each point cannot be jumped twice, so two different instruction lists necessarily lead to different outcomes. Now point can be reached more than twice so this instruction list is sufficient. The only cases that don't fall into $a_n$ are when the last jump skips over the original point $A$. Let $A$ be preceded by $A'$, which is preceded by $A''$. In this case, there are two subcases: First, if we reached $A'$ the first time around and moved one to $A$, then reached $A'$ the second time around and jumped over $A$. In this case, merging $A'$ into $A$ and removing the first jump reduces bijectively to the cases for $n - 1$ where we reach $A$ twice during the process. Second, if we skipped $A'$ the first time around and the second time around we jumped over $A$. In this case, we always reach $A''$ in the first go around. Thus, if we merge $A$ into $A'$, endowing $A'$ with the initial action of $A$, then this bijects into the cases for $n - 1$ where we skip $A$ during the process by reach $A$ after the second loop. Thus, since we have accounted for all cases, we have $a_{n-1} +a_n = 2^n$ as desired.