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$.

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

ACS WASC
ACCREDITED
SCHOOL

Stay Connected

Subscribe to get news and
updates from AoPS, or Contact Us.
© 2017
AoPS Incorporated
Invalid username
Login to AoPS