Difference between revisions of "2013 UMO Problems/Problem 6"

(Created page with "== Problem == How many ways can one tile the border of a triangular grid of hexagons of length <math>n</math> completely using only <math>1 \times 1</math> and <math>1 \times ...")
 
m (See Also)
 
Line 78: Line 78:
 
== See Also ==
 
== See Also ==
 
{{UMO box|year=2013|num-b=5|after=Last Question}}
 
{{UMO box|year=2013|num-b=5|after=Last Question}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 15:28, 14 October 2014

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