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

Difference between revisions of "2013 USAMO Problems/Problem 2"

(→‎Solution)
Line 1: Line 1:
 +
== Problem ==
 +
 
For a positive integer <math>n\geq 3</math> plot <math>n</math> equally spaced points around a circle.  Label one of them <math>A</math>, and place a marker at <math>A</math>.  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 <math>2n</math> distinct moves available; two from each point.  Let <math>a_n</math> count the number of ways to advance around the circle exactly twice, beginning and ending at <math>A</math>, without repeating a move.  Prove that <math>a_{n-1}+a_n=2^n</math> for all <math>n\geq 4</math>.
 
For a positive integer <math>n\geq 3</math> plot <math>n</math> equally spaced points around a circle.  Label one of them <math>A</math>, and place a marker at <math>A</math>.  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 <math>2n</math> distinct moves available; two from each point.  Let <math>a_n</math> count the number of ways to advance around the circle exactly twice, beginning and ending at <math>A</math>, without repeating a move.  Prove that <math>a_{n-1}+a_n=2^n</math> for all <math>n\geq 4</math>.
 +
 +
== Solution 1 ==
 +
 +
We label the points in clockwise order as <math>1</math>, <math>2</math>, <math>3</math>, \dots, <math>n</math>, where point <math>A</math> is the same as point <math>1</math>.  We start and end at point <math>1</math>, and we must cross over it, either by visiting it again, or else by making the move from point <math>n</math> to point <math>2</math>. 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 <math>1\times 1</math> or <math>1\times 2</math> tile. If the point <math>1</math> is visited in the middle, then the first cycle around the circle can be thought of as a tiling of a <math>1\times n</math> board, and the second cycle around the circle can also be thought of as a <math>1\times n</math> 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 <math>1\times n</math> 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 <math>2\times n</math> board. Suppose there are <math>u_n</math> such tilings. It can easily be computed that <math>u_3=2</math> and <math>u_4=6</math> 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 <math>1</math> by moving from point <math>n</math> to point <math>2</math>, we can similarly think about it in terms of tiling two rows of <math>1\times n</math> 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 <math>n</math> to point <math>2</math>. Suppose that we can tile such boards in <math>s_n</math> ways. It can be easily computed that <math>s_3=3</math> and <math>s_4=5</math> 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
 +
<cmath>a_n=u_n+s_n\tag{1}.</cmath>
 +
 +
For the sake of convenience in determining recurrence relations, we define another type of board with two <math>1\times n</math> boards where a specific corner is removed (without loss of generality, we place this in the lower left hand corner). Let <math>t_n</math> 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 <math>t_3=3</math> and <math>t_4=5</math> 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 <math>s_n</math>, <math>t_n</math>, and <math>u_n</math> in terms of each other. For <math>s_n</math>, 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 <math>t_{n-1}</math>, <math>t_{n-2}</math>, and <math>s_{n-2}</math> ways, respectively. Hence for <math>n\ge 5</math>, we see that
 +
<cmath>s_n=t_{n-1}+t_{n-2}+s_{n-2}\tag{2}.</cmath>
 +
For <math>t_n</math>, 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 <math>s_{n-1}</math>, <math>s_{n-2}</math>, and <math>t_{n-2}</math> ways, respectively. Hence for <math>n\ge 5</math>, we see that
 +
<cmath>t_n=s_{n-1}+s_{n-2}+t_{n-2}\tag{3}.</cmath>
 +
For <math>u_n</math>, 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 <math>t_{n-1}</math>  ways in each case. Hence for <math>n\ge 4</math>, we see that
 +
<cmath>u_n=2t_{n-1}\tag{4}.</cmath>
 +
Subtracting (3) from (2), we find that
 +
<cmath>s_n-t_n=s_{n-1}-t_{n-1}.</cmath>
 +
Therefore, if <math>s_{n-1}=t_{n-1}</math>, then <math>s_n=t_n</math>. Since <math>s_3=t_3</math> and <math>s_4=t_4</math>, we see that <math>s_n=t_n</math> for all <math>n\ge 3</math>. Therefore, (2) can be rewritten as
 +
<cmath>s_n=s_{n-1}+2s_{n-2}\tag{5},</cmath>
 +
and (4) can be rewritten as
 +
<cmath>u_n=2s_{n-1}\tag{6}.</cmath>
 +
Now by (1), we know that
 +
<cmath>a_{n}+a_{n-1}=u_n+s_n+u_{n-1}+s_{n-1}.\tag{7}</cmath>
 +
In particular, <math>a_4+a_3=6+5+2+3=2^4</math>, so the statement is true for <math>n=4</math>. Then by (7), and then substituting (5) and (6) (where these are valid for <math>n\ge 5</math>), we find
 +
<cmath>
 +
\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*}
 +
</cmath>
 +
But then by (5), and then substituting <math>4s_{n-3}=2u_{n-2}</math> and <math>2s_{n-2}=u_{n-1}</math> (by (6), and these are valid for <math>n\ge 6</math>), we find
 +
<cmath>
 +
\begin{align*}
 +
2s_{n-1}&=2s_{n-2}+4s_{n-3}\\
 +
&=u_{n-1}+2u_{n-2}.
 +
\end{align*}
 +
</cmath>
 +
We substitute this into (8), finding that for <math>n\ge 6</math>,
 +
<cmath>
 +
\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*}
 +
</cmath>
 +
Therefore, if <math>a_{n-1}+a_{n-2}=2^{n-1}</math>, then <math>a_{n}+a_{n-1}=2^n</math>. We already know that <math>a_4+a_3=2^4</math>. Also, we can compute that
 +
<cmath>
 +
\begin{align*}
 +
s_5&=s_4+2s_3=5+2\cdot 3=11\\
 +
u_5&=2s_4=2\cdot 5=10.
 +
\end{align*}
 +
</cmath>
 +
Hence <math>a_5=s_5+u_5=21</math>. So as <math>a_4=s_4+u_4=11</math>, we find that <math>a_5+a_4=2^5</math>. Then we can use (9) for <math>n\ge 6</math> to find by induction that <math>a_{n}+a_{n-1}=2^n</math> for all <math>n\ge 4</math>.
 +
 +
{{MAA Notice}}

Revision as of 21:16, 6 July 2016

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"