Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2013 USAMO Problems/Problem 2

Revision as of 21:16, 6 July 2016 by Mathgeek2006 (talk | contribs)

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_USAMO_Problems/Problem_2&oldid=79205"