Suppose you have a tiling of length $n+2$. This can be built from:
- a tiling of length $n+1$ followed by a single tile; OR
- a tiling of length $n$ followed by a double tile
Let $T_n$ be the number of different ways of tiling a $1\times n$ space. Then for $n\ge1$
$$T_{n+2}=T_{n+1}T_1+T_n=3T_{n+1}+T_n \tag{1}$$
and for the "base" cases: $T_1=3,\:T_2=10$. Then by (1)
$$\begin{array}{l}
T_3=33 \\
T_4=109 \\
T_5=360 \\
T_6=1189
\end{array}$$
So the hallway must be at least six units long for 1000+ different tiling possibilities.
The recursion is Fibonacci-like and can be written in matrix form as:
$$\begin{bmatrix}T_{n+2}\\T_{n+1}\end{bmatrix}=\begin{bmatrix}3 & 1\\1 & 0\end{bmatrix}\begin{bmatrix}T_{n+1}\\T_{n}\end{bmatrix}$$
from which the characteristic equation is $(3-\lambda)(-\lambda)-1\times1=0 \implies \lambda^2-3\lambda-1=0$ which has solutions $\lambda=\frac{3\pm\sqrt{13}}{2}$
So we seek a formula for $T_n$ of the form $T_n=a\left(\frac{3+\sqrt{13}}{2}\right)^n+b\left(\frac{3-\sqrt{13}}{2}\right)^n$. Substituting for some values of $T_n$, e.g. $T_3,T_4$ to be safe, you can solve to get
$$T_n=\frac{1}{\sqrt{13}}\left\{\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}\right\}$$
It turns out that this formula works for $n=1,2$ as well even though the recursion didn't cover these cases. The formula can be proven by induction.
Appendix - Obtaining a Closed-Form Solution
In the formula $T_n=a\left(\frac{3+\sqrt{13}}{2}\right)^n+b\left(\frac{3-\sqrt{13}}{2}\right)^n$ let $a=a_1+a_2\sqrt{13},\:b=b_1+b_2\sqrt{13}$ (with $a_1,a_2,b_1,b_2$ all rational numbers). Then from $T_1=3,T_2=10$ we get:
$$\begin{align}
T_1&=(a_1+a_2\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^1+(b_1+b_2\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^1&=3 \\
T_2&=(a_1+a_2\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^2+(b_1+b_2\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^2&=10
\end{align}$$
and from this (by equating rational multiples of $1,\sqrt{13}$) we obtain four simultaneous equations:
$$\begin{array}{rccccccccc}
T_1[1]: & 3a_1 &+ &13a_2 &+ &3b_1 &- &13b_2 &= &6 \\
T_1[\sqrt{13}]: & a_1 &+ &3a_2 &- &b_1 &+ &3b_2 &= &0 \\
T_2[1]: & 11a_1 &+ &39a_2 &+ &11b_1 &- &39b_2 &= &20 \\
T_1[\sqrt{13}]: & 3a_1 &+ &11a_2 &- &3b_1 &+ &11b_2 &= &0 \\
\end{array}$$
with solution $a_1=b_1=\frac{1}{2},\:a_2=\frac{3}{26},b_2=-\frac{3}{26}$. So with a little manipulation
$$\begin{align}
T_n&=\tfrac{1}{2}(1+\tfrac{3}{13}\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^n + \tfrac{1}{2}(1-\tfrac{3}{13}\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^n \\[2ex]
&=\frac{1}{\sqrt{13}}\left(\frac{\sqrt{13}+3}{2}\right)\left(\frac{3+\sqrt{13}}{2}\right)^n + \frac{1}{\sqrt{13}}\left(\frac{\sqrt{13}-3}{2}\right)\left(\frac{3-\sqrt{13}}{2}\right)^n \\[2ex]
&=\frac{1}{\sqrt{13}}\left\{\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}\right\}
\end{align}$$
I will make frequent use of the words "domino" and "monomino" in this problem.
Let $a_k$ represent the number of ways to tile a $2\times k$ wall. We will seek to find a recurrence relation for $a_{k+1}$ by considering the rightmost between-column where there is a vertical line that doesn't cut through a domino.
Here will be the different summands of $a_{k+1}$:
- $2a_k$: There are two different ways to "cleanly" cover just the last column: one domino or two monominoes.
- $3a_{k-1}$: There are three different ways to cleanly cover exactly the last two columns: two dominoes one above the other, a domino on top and two monominoes on bottom, and a domino on bottom and two monominoes on top.
- $2a_{k-2}$: There are two ways to cleanly cover exactly exactly the last three columns:
- $2a_{k-3}+2a_{k-4}+\cdots+2a_1$+: Extending the same zipper pattern further, there are exactly two ways to cover any extra number of columns.
So we have $$a_{k+1}=2a_k+3a_{k-1}+2a_{k-2}+...+a_1,\ a_0=1$$
This is A030186 in OEIS. Also note that, since $$a_k=2a_{k-1}+3a_{k-2}+2a_{k-3}+...+a_1$$ we can rearrange and add the two equations together to get
$$a_{k+1} = 3a_k + a_{k-1} - a_{k-2}$$ Either way, $a=(1,2,7,22,71,228,733,2356,\cdots)$, so $a_7=2356$.
Best Answer
No, it is impossible, even allowing different sized hats.
Every internal angle of the hat has a measure of at least $90^\circ$, and there are exactly four right angles, marked A, B, C, and D in the image below. There needs to be some smaller hat which covers the vertex of angle D. Because the smallest angle is $90^\circ$, the point of smaller tile over vertex D must be one of the vertices A, B, C, or D. However, A, B, and C are impossible, because each of these angles have a neighboring reflex angle which measures greater than $180^\circ$, which would force the smaller hat to just out of the larger hat. Therefore, the smaller hat would have to have its D vertex aligned with the D vertex of the large tile. But this creates a different problem; since both of the angles next to D measure $120^\circ$, the smaller hat tile at D would create a $180^\circ-120^\circ=60^\circ$ angle in the leftover space, and the hat has no angle small enough to fit inside a $60^\circ$ angle. Therefore, there is no way to tile a hat with smaller hats.