2013 UMO Problems/Problem 6

Problem

How many ways can one tile the border of a triangular grid of hexagons of length $n$ completely using only $1 \times 1$ and $1 \times  2$ hexagon tiles? Express your answer in terms of a well-known sequence, and prove that your answer holds true for all positive integers $n \ge 3$ (examples of such grids for $n = 3$, $n = 4$, $n = 5$, and $n = 6$ are shown below).

[asy] path S=rotate(30)*polygon(6); filldraw(S,green+linewidth(.75)); filldraw(shift(sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(2*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(sqrt(3)/2,3/2)*S,green+linewidth(.75)); filldraw(shift(3*sqrt(3)/2,3/2)*S,green+linewidth(.75)); filldraw(shift(sqrt(3),3)*S,green+linewidth(.75));  filldraw(shift(6,0)*S,green+linewidth(.75)); filldraw(shift(6,0)*shift(sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(6,0)*shift(2*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(6,0)*shift(3*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(6,0)*shift(sqrt(3)/2,3/2)*S,green+linewidth(.75)); //filldraw(shift(6,0)*shift(3*sqrt(3)/2,3/2)*S,green+linewidth(.75)); filldraw(shift(6,0)*shift(5*sqrt(3)/2,3/2)*S,green+linewidth(.75)); filldraw(shift(6,0)*shift(sqrt(3),3)*S,green+linewidth(.75)); filldraw(shift(6,0)*shift(2*sqrt(3),3)*S,green+linewidth(.75)); filldraw(shift(6,0)*shift(3*sqrt(3)/2,9/2)*S,green+linewidth(.75));  filldraw(shift(14,0)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(2*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(3*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(4*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(sqrt(3)/2,3/2)*S,green+linewidth(.75)); //filldraw(shift(14,0)*shift(3*sqrt(3)/2,3/2)*S,green+linewidth(.75)); //filldraw(shift(14,0)*shift(5*sqrt(3)/2,3/2)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(7*sqrt(3)/2,3/2)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(sqrt(3),3)*S,green+linewidth(.75)); //filldraw(shift(14,0)*shift(2*sqrt(3),3)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(3*sqrt(3),3)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(3*sqrt(3)/2,9/2)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(5*sqrt(3)/2,9/2)*S,green+linewidth(.75)); filldraw(shift(14,0)*shift(2*sqrt(3),6)*S,green+linewidth(.75));   filldraw(shift(24,0)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(2*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(3*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(4*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(5*sqrt(3),0)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(sqrt(3)/2,3/2)*S,green+linewidth(.75)); //filldraw(shift(24,0)*shift(3*sqrt(3)/2,3/2)*S,green+linewidth(.75)); //filldraw(shift(24,0)*shift(5*sqrt(3)/2,3/2)*S,green+linewidth(.75)); //filldraw(shift(24,0)*shift(7*sqrt(3)/2,3/2)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(9*sqrt(3)/2,3/2)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(sqrt(3),3)*S,green+linewidth(.75)); //filldraw(shift(24,0)*shift(2*sqrt(3),3)*S,green+linewidth(.75)); //filldraw(shift(24,0)*shift(3*sqrt(3),3)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(4*sqrt(3),3)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(3*sqrt(3)/2,9/2)*S,green+linewidth(.75)); //filldraw(shift(24,0)*shift(5*sqrt(3)/2,9/2)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(7*sqrt(3)/2,9/2)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(2*sqrt(3),6)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(3*sqrt(3),6)*S,green+linewidth(.75)); filldraw(shift(24,0)*shift(5*sqrt(3)/2,15/2)*S,green+linewidth(.75));  filldraw(shift(38,0)*S,green+linewidth(.75)); filldraw(shift(38,0)*shift(sqrt(3)/2,3)*S,green+linewidth(.75)); filldraw(shift(38,0)*shift(-sqrt(3)/2,3)*S,green+linewidth(.75)); [/asy]

Solution

See Also

2013 UMO (ProblemsAnswer KeyResources)
Preceded by
Problem 5
Followed by
Last Question
1 2 3 4 5 6
All UMO Problems and Solutions