# 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]$