2013 USAMO Problems/Problem 2

Problem

For a positive integer $n\geq 3$ plot $n$ equally spaced points around a circle. Label one of them $A$ , and place a marker at $A$ . 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 $2n$ distinct moves available; two from each point. Let $a_n$ count the number of ways to advance around the circle exactly twice, beginning and ending at $A$ , without repeating a move. Prove that $a_{n-1}+a_n=2^n$ for all $n\geq 4$ .

Solution 1

We label the points in clockwise order as $1$ , $2$ , $3$ , \dots, $n$ , where point $A$ is the same as point $1$ . We start and end at point $1$ , and we must cross over it, either by visiting it again, or else by making the move from point $n$ to point $2$ . We interpret each of these cases in terms of tiling. In each move, we either move one or two points clockwise, so we can think of each move as a $1\times 1$ or $1\times 2$ tile. If the point $1$ is visited in the middle, then the first cycle around the circle can be thought of as a tiling of a $1\times n$ board, and the second cycle around the circle can also be thought of as a $1\times n$ board. We place this second board directly below the first board. Therefore, in this first case, we wish to find the number of tilings of two $1\times n$ boards, and to guarantee that no move is repeated, we cannot have two tiles of the same type lying directly atop each other in the $2\times n$ board. Suppose there are $u_n$ such tilings. It can easily be computed that $u_3=2$ and $u_4=6$ as shown below. $[asy] unitsize(10); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle^^(0,1)--(3,1),linewidth(2)); draw((1,0)--(1,1)^^(2,1)--(2,2)); draw(shift((0,-2.5))*((0,0)--(3,0)--(3,2)--(0,2)--cycle^^(0,1)--(3,1)),linewidth(2)); draw(shift((0,-2.5))*((1,0)--(1,1)^^(2,1)--(2,2))); draw(shift((7,0))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((7,0))*((1,1)--(1,2)^^(2,0)--(2,2)^^(3,1)--(3,2))); draw(shift((7,-2.5))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((7,-2.5))*((1,0)--(1,1)^^(2,0)--(2,2)^^(3,1)--(3,2))); draw(shift((12,0))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((12,0))*((1,1)--(1,2)^^(2,0)--(2,1)^^(3,1)--(3,2))); draw(shift((12,-2.5))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((12,-2.5))*((1,1)--(1,2)^^(2,0)--(2,2)^^(3,0)--(3,1))); draw(shift((17,0))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((17,0))*((1,0)--(1,1)^^(2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((17,-2.5))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((17,-2.5))*((1,0)--(1,1)^^(2,0)--(2,2)^^(3,0)--(3,1))); [/asy]$ In the second case, where we pass by point $1$ by moving from point $n$ to point $2$ , we can similarly think about it in terms of tiling two rows of $1\times n$ boards, but we remove the last square in the first row and the first square in the second row to make sure that we jump from point $n$ to point $2$ . Suppose that we can tile such boards in $s_n$ ways. It can be easily computed that $s_3=3$ and $s_4=5$ as shown below. $[asy] unitsize(10); draw((1,0)--(3,0)--(3,1)--(2,1)--(2,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(2,1),linewidth(2)); draw(shift((0,-2.5))*((1,0)--(3,0)--(3,1)--(2,1)--(2,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(2,1)),linewidth(2)); draw(shift((0,-2.5))*((2,0)--(2,1))); draw(shift((4,0))*((1,0)--(3,0)--(3,1)--(2,1)--(2,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(2,1)),linewidth(2)); draw(shift((4,0))*((1,1)--(1,2))); draw(shift((11,0))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((11,0))*((1,1)--(1,2)^^(2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((11,-2.5))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((11,-2.5))*((2,0)--(2,2))); draw(shift((16,0))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((16,0))*((2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((16,-2.5))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((16,-2.5))*((1,1)--(1,2)^^(2,0)--(2,1)^^(3,0)--(3,1))); draw(shift((21,0))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((21,0))*((1,1)--(1,2)^^(2,0)--(2,1))); [/asy]$ Since these are the only two possible cases, we see that $a_n=u_n+s_n\tag{1}.$

For the sake of convenience in determining recurrence relations, we define another type of board with two $1\times n$ boards where a specific corner is removed (without loss of generality, we place this in the lower left hand corner). Let $t_n$ be the number of ways to tile such a board without placeing two of the same type of tile atop each other. Once again, we compute that $t_3=3$ and $t_4=5$ as shown below. $[asy] unitsize(10); draw((1,0)--(3,0)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1),linewidth(2)); draw((1,1)--(1,2)^^(2,0)--(2,1)); draw(shift((0,-2.5))*((1,0)--(3,0)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((0,-2.5))*((1,1)--(1,2)^^(2,1)--(2,2))); draw(shift((4,0))*((1,0)--(3,0)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((4,0))*((2,1)--(2,2))); draw(shift((11,0))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((11,0))*((1,1)--(1,2)^^(2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((11,-2.5))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((11,-2.5))*((1,1)--(1,2)^^(2,0)--(2,1)^^(3,1)--(3,2))); draw(shift((16,0))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((16,0))*((2,0)--(2,2)^^(3,1)--(3,2))); draw(shift((16,-2.5))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((16,-2.5))*((2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((21,0))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((21,0))*((2,0)--(2,2)^^(3,0)--(3,1))); [/asy]$ We can determine reccurence relations for $s_n$ , $t_n$ , and $u_n$ in terms of each other. For $s_n$ , note that a tiling can end in one of the three following ways such that the rest of the board can be tiled without restriction (the placed tiles are shaded). $[asy] path unitrect=(0,0)--(2,0)--(2,1)--(0,1)--cycle; unitsize(10); fill(shift((3,0))*unitsquare,mediumgray); draw(shift((0,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(3,1)--(3,2)--(0,2)),linewidth(2)); draw(shift((0,0))*((3,0)--(3,1))); label("$\dots$",(-1,1)); fill(shift((10,1))*unitsquare,mediumgray); fill(shift((10,0))*unitrect,mediumgray); draw(shift((8,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(3,1)--(3,2)--(0,2)),linewidth(2)); draw(shift((8,0))*((2,0)--(2,2))); label("$\dots$",(8-1,1)); fill(shift((18,0))*unitrect,mediumgray); fill(shift((17,1))*unitrect,mediumgray); draw(shift((16,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(3,1)--(3,2)--(0,2)),linewidth(2)); draw(shift((16,0))*((2,0)--(2,1)^^(1,1)--(1,2))); label("$\dots$",(16-1,1)); [/asy]$ In the first, second, and third cases, we see that we can tile the rest of the board in $t_{n-1}$ , $t_{n-2}$ , and $s_{n-2}$ ways, respectively. Hence for $n\ge 5$ , we see that $s_n=t_{n-1}+t_{n-2}+s_{n-2}\tag{2}.$ For $t_n$ , note that a tiling can end in one of the three following ways such that the rest of the board can be tiled without restriction. $[asy] path unitrect=(0,0)--(2,0)--(2,1)--(0,1)--cycle; unitsize(10); filldraw(shift((3,0))*unitsquare,mediumgray); filldraw(shift((2,1))*unitrect,mediumgray); draw(shift((0,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$\dots$",(-1,1)); filldraw(shift((11,1))*unitsquare,mediumgray); filldraw(shift((10,0))*unitrect,mediumgray); filldraw(shift((9,1))*unitrect,mediumgray); draw(shift((8,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$\dots$",(8-1,1)); filldraw(shift((19,1))*unitsquare,mediumgray); filldraw(shift((18,1))*unitsquare,mediumgray); filldraw(shift((18,0))*unitrect,mediumgray); draw(shift((16,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$\dots$",(16-1,1)); [/asy]$ In the first, second, and third cases, we see that we can tile the rest of the board in $s_{n-1}$ , $s_{n-2}$ , and $t_{n-2}$ ways, respectively. Hence for $n\ge 5$ , we see that $t_n=s_{n-1}+s_{n-2}+t_{n-2}\tag{3}.$ For $u_n$ , note that a tiling can end in one of the two following ways such that the rest of the board can be tiled without restriction. $[asy] path unitrect=(0,0)--(2,0)--(2,1)--(0,1)--cycle; unitsize(10); filldraw(shift((3,1))*unitsquare,mediumgray); filldraw(shift((2,0))*unitrect,mediumgray); draw(shift((0,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$\dots$",(-1,1)); filldraw(shift((11,0))*unitsquare,mediumgray); filldraw(shift((10,1))*unitrect,mediumgray); draw(shift((8,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$\dots$",(8-1,1)); [/asy]$

In either case, we are left with a board with a corner removed, hence we can tile the rest of the board in $t_{n-1}$ ways in each case. Hence for $n\ge 4$ , we see that $u_n=2t_{n-1}\tag{4}.$ Subtracting (3) from (2), we find that $s_n-t_n=s_{n-1}-t_{n-1}.$ Therefore, if $s_{n-1}=t_{n-1}$ , then $s_n=t_n$ . Since $s_3=t_3$ and $s_4=t_4$ , we see that $s_n=t_n$ for all $n\ge 3$ . Therefore, (2) can be rewritten as $s_n=s_{n-1}+2s_{n-2}\tag{5},$ and (4) can be rewritten as $u_n=2s_{n-1}\tag{6}.$ Now by (1), we know that $a_{n}+a_{n-1}=u_n+s_n+u_{n-1}+s_{n-1}.\tag{7}$ In particular, $a_4+a_3=6+5+2+3=2^4$ , so the statement is true for $n=4$ . Then by (7), and then substituting (5) and (6) (where these are valid for $n\ge 5$ ), we find $\begin{align*} a_n+a_{n-1}&=u_n+s_n+u_{n-1}+s_{n-1}\\ &=2s_{n-1}+(s_{n-1}+2s_{n-2})+u_{n-1}+s_{n-1}\\ &=4s_{n-1}+2s_{n-2}+u_{n-1}.\tag{8} \end{align*}$ But then by (5), and then substituting $4s_{n-3}=2u_{n-2}$ and $2s_{n-2}=u_{n-1}$ (by (6), and these are valid for $n\ge 6$ ), we find $\begin{align*} 2s_{n-1}&=2s_{n-2}+4s_{n-3}\\ &=u_{n-1}+2u_{n-2}. \end{align*}$ We substitute this into (8), finding that for $n\ge 6$ , $\begin{align*} a_{n}+a_{n-1}&=2s_{n-1}+2s_{n-2}+u_{n-1}+(u_{n-1}+2u_{n-2})\\ &=2(s_{n-1}+s_{n-2}+u_{n-1}+u_{n-2})\\ &=2(a_{n-1}+a_{n-2}).\tag{9} \end{align*}$ Therefore, if $a_{n-1}+a_{n-2}=2^{n-1}$ , then $a_{n}+a_{n-1}=2^n$ . We already know that $a_4+a_3=2^4$ . Also, we can compute that $\begin{align*} s_5&=s_4+2s_3=5+2\cdot 3=11\\ u_5&=2s_4=2\cdot 5=10. \end{align*}$ Hence $a_5=s_5+u_5=21$ . So as $a_4=s_4+u_4=11$ , we find that $a_5+a_4=2^5$ . Then we can use (9) for $n\ge 6$ to find by induction that $a_{n}+a_{n-1}=2^n$ for all $n\ge 4$ .

Solution 2

We choose the tilings for the first and second pass around the circle simultaneously. As we tile both passes, our state is defined by whether or not we are in a continuation of a length 2 block on the first and second pass. We can't be in a continuation of a length 2 block on both passes, since that would mean we used the same move on the same block on both passes. Thus we have three states: (non-continuation, non-continuation), (non-continuation, continuation), and (continuation, non-continuation), where the elements of each tuple refer to the first and second pass. Listing out the possible states we can transition to in each state (while following the rule that we can't use the same move twice), we get the transition matrix $T = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} = J-I$ , where $J$ is the ones matrix, and $I$ is the identity. We have that $a_n = \left(T^n\right)_{11} + \left(T^n\right)_{23}$ . The first term represents the case where we end the first pass at point $A$ , and the second term represents the case where we jump over point $A$ when finishing the first pass. Thus it simply remains to compute $T^n$ . We have $T^n = (J-I)^n = \sum_{k=0}^n J^k (-1)^{n-k} {n \choose k} = J \sum_{k=1}^n 3^{k-1} (-1)^{n-k} {n \choose k} + (-1)^n I = \frac{1}{3}J\left(2^n-(-1)^n\right) + (-1)^n I$ . Thus $a_n = \left(T^n\right)_{11} + \left(T^n\right)_{23} = \frac{2}{3}\left(2^n-(-1)^n\right) + (-1)^n$ . Thus, $a_{n-1}+a_n = 2^n$ , as desired.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Page

Toolbox

Search

2013 USAMO Problems/Problem 2

Problem

Solution 1

Solution 2