,
,
.
be an arbitrary point inside 
such that 
.
intersects 
(other than 
(other than 
.
intersects rays 
and 
at points 
and 
,
.
and 
Prove that
Let 
Prove that
Let 
and 
Prove that
Let 
Prove that
games and lost 
were there in which 
,
,
.
are all real positive number that: 
.
,
,
.
and 
.
Let 
.
Let 
.
Let 
.
Y by Davi-8191, mobro, megarnie, Adventure10, Mango247
For a positive integer 
plot 
equally spaced points around a circle. Label one of them 
, and place a marker at . One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of 
distinct moves available; two from each point. Let 
count the number of ways to advance around the circle exactly twice, beginning and ending at , without repeating a move. Prove that 
for all 
.
plot 
equally spaced points around a circle. Label one of them 
, and place a marker at . One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of 
distinct moves available; two from each point. Let 
count the number of ways to advance around the circle exactly twice, beginning and ending at , without repeating a move. Prove that 
for all 
.
for even 
for odd 
point or the 
point from the beginning.
and it fell from there
.
good points, there are 
valid paths that visit exactly that set of points twice if that set includes 
otherwise.
.
- this pair of paths must intersect only at 
and 
.
and 
where the identity of the last step depends on the parity of the length of the path. For each pair of neighboring good points, we can execute either of these paths first and the other second, giving 
paths in all.
be our set. Each valid path consists of a path from 
,
,
to 
paths from 
items, there are easily ![\[\binom{a - b + 1}{b}\]](http://latex.artofproblemsolving.com/8/b/7/8b7818fbc2b07d6abd04730ddfe4c2b99dacd66e.png)
ways to choose 
of them with no two consecutive. Together with casework on whether or not we include ![\[a_n = 2\sum_{k \ge 0}{\binom{n - 2 - k}{k}2^k} + \sum_{k \ge 1}{\binom{n - k}{k}2^{k - 1}} + \frac{1 - (-1)^n}{2} \; \; \; \; (*)\]](http://latex.artofproblemsolving.com/5/3/f/53f8d7c5bfaef117ffafa3f72b3d28a8023aec5a.png)
where the final term is to account for the fact that the null set is a valid configuration of good points iff ![\begin{align*} \sum_{k}{\binom{n - k}{k}x^k} &= [y^n]\left(\sum_{n}{y^n\sum_{k}{\binom{n - k}{k}x^k}}\right) \\ &= [y^n]\left(\sum_{k}{x^k\sum_{n}{\binom{n - k}{k}y^n}}\right) \\ &= [y^n]\left(\sum_{k}{x^k\frac{y^{2k}}{(1 - y)^{k + 1}}}\right) \\ &= [y^n]\left(\frac{1}{1 - y} \cdot \frac{1}{1 - \frac{xy^2}{1 - y}}\right) \\ &= [y^n]\left(\frac{1/3}{1 + y} + \frac{2/3}{1 - 2y} \right) = \frac{2^n + (-1)^n}{3}\end{align*}](http://latex.artofproblemsolving.com/3/7/3/37372e7a936c09d4095eee27b8e08b09967354c8.png)
when 
.
explicity; it becomes ![\[\frac{2^{n + 1} - (-1)^{n + 1}}{3}\]](http://latex.artofproblemsolving.com/5/8/a/58a676511f55062f84dbee0c0fa739ef2461e325.png)
so that 
,
or 
and for every point you move the labeled number of points forward if it is the first time the point is visited and the other move if it is the second time the point is visited. Call a labeling 
must be skipped twice. The only possible way that can happen is if the marker visits the point right before 
is equal to the number of 
possible labelings in total. Thus, the number of 
be the number of such paths that pass through 
the ones that don't. Then 
and for 
Now this gives 
giving the wanted formula for 
and 
.![\[b_{2k-1}+2=4c_{2k-1},b_{2k-2}-2=4c_{2k-2}\]](http://latex.artofproblemsolving.com/3/1/d/31d8d3778f963d2d880301da055e95d36fca62db.png)
for all 
points labelled with 2 on the circle, there are 
paths. The number of ways to choose 
,
ways.
is in the clockwise direction. Merge the path from 
paths if there are 
ways to choose 
ways for this case.
and if 
.
instead, starting at 
and ending at ![\[ \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} \]](http://latex.artofproblemsolving.com/e/b/5/eb508dabaef073fcceda03b17260192fba7699d5.png)
where 
was used; in particular, 
.![\[ \begin{bmatrix} 0 & 0 \end{bmatrix} \qquad \begin{bmatrix} 0 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \]](http://latex.artofproblemsolving.com/3/4/3/343d6d75615e9922e0287e9a43be48fb93c9a1db.png)
which correspond to forbidding jumps of length greater than 
matrix is silver 
)
,
.
and 
denote matrices of each type, of size 
:
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]$](http://latex.artofproblemsolving.com/9/1/3/9130258fab86872d2ae6609ffc9d4ebd7acc35ef.png)
then we find a type C matrix, giving 
.![$\left[ \begin{smallmatrix} 1 \\ 1 \end{smallmatrix} \right]$](http://latex.artofproblemsolving.com/7/3/7/7370b4a6c009ba31ce940053fa4381abfd1fe8d6.png)
then the third column must be either ![$\left[ \begin{smallmatrix} 1 \\ 0 \end{smallmatrix} \right]$](http://latex.artofproblemsolving.com/7/d/5/7d5acff64ba593a997281ccb955298474139a2d4.png)
,
.![\[ \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} \]](http://latex.artofproblemsolving.com/f/e/2/fe203664045296510d599282643bcbcb68a1406e.png)
and a calculation gives 
,
.![\[ \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}. \]](http://latex.artofproblemsolving.com/4/3/e/43e850641d4ae64136a9749a107f0912289bdaa3.png)
There are 
matrices of the first form and 
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}. \]](http://latex.artofproblemsolving.com/a/6/d/a6d77d06b573e15d9dae9ac17d2631a6c1938059.png)
wasn't hit the first time around, that means that a move of length 2 was performed from 
.
)
of these sequences end up landing on 
of them failed. Now, consider a circle of size 
,
as desired.
be the point directly counterclockwise to 
.
points and a marker labeled 
or the number 
;
ways. Then proceed around the circle starting from 
,
points.)
ways to advance around a circle with 
ways to advance around a circle with 
points.
as needed.
Also this is very similar to the solutions provided above by users TheUltimate123 and JSGandora.
times, then we use the jump 
to 
is fixed, hence the remaining 
for all 
modulo 
.![$[a,a+1]$](http://latex.artofproblemsolving.com/3/d/4/3d46843af7a761025a009a8e8b55d5a5dafb932e.png)
is contained within exactly one move in a particular sequence of moves.
composed such that no two collections of moves contain the same particular individual move 
.
,
,
denote the first instance of the two sequences agreeing. If 
then we have 
for 
.![$b_n=2\cdot [1+\sum_{1<i<n}b_{n-i}] $](http://latex.artofproblemsolving.com/b/5/7/b57ad99143f7435420da0c28c9d2496092521eb2.png)
.
.
.![\[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}.\]](http://latex.artofproblemsolving.com/9/a/0/9a07be3ff4a679345b5c27a02842f8943fc3bd32.png)
which include 
.
is also one of the moves and so is 
,
.
is a move, this is 
.
is a move and 
sequences.
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 
possibilities. If there exists no such point, then 
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}=\]](http://latex.artofproblemsolving.com/c/b/2/cb2aa388001eab219e2d5876ffae835e74eb8686.png)
![\[\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}.\]](http://latex.artofproblemsolving.com/7/a/2/7a21f3139ff8e45284af2736e038467c4f4d471d.png)
The problem is now dead because![\[a_n+a_{n-1}=\frac{3\cdot 2^n}{3}=2^n.\]](http://latex.artofproblemsolving.com/7/3/b/73b9331abcdf4b9dcbc68e96ac0db1644f0a2a07.png)
![[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]](http://latex.artofproblemsolving.com/7/6/9/769ac8ee6e5e5d07fc06f968097a49ec319ade55.png)
![[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]](http://latex.artofproblemsolving.com/a/a/5/aa5d9c583db56eaed9f9e33ab47f1f6d1a3f3ba8.png)
![[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]](http://latex.artofproblemsolving.com/a/e/0/ae01133ff9aab0f2971e0429191dc644f25f67a0.png)
Finally, introduce the sequence 
,![[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]](http://latex.artofproblemsolving.com/b/d/c/bdcb9811008e98b3243654fdd3859286e2056792.png)
ways to fill the remaining blocks.
ways to fill the remaining blocks.
ways to fill the remaining blocks.
Now we establish a relationship between 
.
.![[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]](http://latex.artofproblemsolving.com/9/0/d/90d9d9adde584ed61b098cd139b6c68963a09f91.png)
![$[2,n]$](http://latex.artofproblemsolving.com/e/6/4/e6409fd10c6174fc1e20b7290146a7f3354d77f9.png)
there is exactly two ways to fill in the blocks to the left of this distance. Hence we have the recursion:
Comparing 
and subtracting, we obtain
Further, it's not hard to compute 
(there is one way to fill in the empty bars: doing nothing), and 
which also gives
Using this, we can verify the identity
as well as
Further, we can get 
,
We're actually done now, since
grid where we write a 
below for 
,
this means we move along the circle 
.
,
,
,
.
corresponds to 
which is actually valid.
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 
to be the number of ways to reach 
with initial conditions 
.
,
is the number of ways to start at 
,
,
Focusing on what the problem asks for:
as desired. Note that in the last step, we used the observation that 
,
,![\[
\begin{bmatrix}
1 & 1 & 0 & 1 & 1 \\
0 & 1 & 1 & 1 & 0
\end{bmatrix}
\]](http://latex.artofproblemsolving.com/a/8/d/a8dd5c8fe3c030d28b93ec8c195838d193f275dd.png)
corresponds to 
.
written, but I think ![\[ a_n = \frac{2^{n+1}+(-1)^{n+1}}{3} \]](http://latex.artofproblemsolving.com/2/f/1/2f149f9686a449e317243336ce9617519650770c.png)
is actually odd for all 
.
if the point 
if the point was not visited by the counter. Note that ![\[ \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} \]](http://latex.artofproblemsolving.com/7/7/5/775d8d1f57a992b2bdf8ce3b824eb2e1796d2c10.png)
then we can instead describe valid matrices as sequences of 
and end with 
,
and end with 
and 
denote the number of such 
matrices. (Hence 
.
We also have that ![\[ 2x_n + y_n = 2^n \]](http://latex.artofproblemsolving.com/f/b/9/fb9271f0adbcf250735855119e31cf3d3c9023c2.png)
which may either be proved directly from the recursions (using 
and 
)
as needed.
,
.
as desired.
denote the number of sequences that hit A again. Recursing (lay it out in a line and take cases on where the two paths first meet) gives that 
or 
.
ways. If the first jump is of length one, merge 
,
.
