<style>
.text-center
{ text-align: center; //文字置中 }
.text-left
{ text-align: left; //文字靠左 }
.text-right
{ text-align: right; //文字靠右 }
</style>

# Covering $L_n$ by $L_1$

An $L_1$-block is a fundamental block structure composed of three 1×1 tiles arranged in an 'L' shape. There are four possible orientations for an $L_1$-block, each corresponding to a different rotation of the 'L' shape as shown in Fig. 1.

<p class="text-center">
<img src="https://hackmd.io/_uploads/HkoaNXClkx.png" width=60% height=60%> </p>

$$\text{Fig. 1 Four types of } L_1\text{-blocks}$$

In fact, we can describe an $L_1$-block as a $2\times 2$ square containing three tiles and one empty cell. Let $L_1(x,y)$ denote the $L_1$-block with its empty cell positioned at $(x, y)$ for $0\le x,\ y\le 1$. Specifically, the above four $L_1$-blocks are designated as $L_1(0,0)$, $L_1(0,1)$, $L_1(1,0)$ and $L_1(1,1)$, respectively.

We define an $L_n$-block as a $2^n\times 2^n$ square composed of $2^n\times 2^n-1$ tiles and a single empty cell, which can be specifically denoted as $L_n(x,y)$ with its empty cell positioned at $(x, y)$ for $0\le x,\ y\le 2^n-1$. Then, the following theorem holds.
:::info
$Theorem$
$Each\ L_n\text{-}block\ can\ be\ covered\ by\ L_1\text{-}blocks\ without\ overlapping.$
:::
:::success
$Proof\ (By\ mathematical\ induction)$
Consider $n=1$. Any $L_1$-block, either $L_1(0,0)$, $L_1(0,1)$, $L_1(1,0)$ or $L_1(1,1)$, can be easily constructed via a specific rotation of any $L_1$-block.
Suppose that the statement holds for $n=k$.
For $n=k+1$, consider the $L_{k+1}$-block $L_{k+1}(x,y)$ where $0\le x,y\le 2^{k+1}-1$. We may decompose the $2^{k+1}\times 2^{k+1}$ square into four $2^{k}\times 2^{k}$ sub-squares which are named as $L_k^{00}$, $L_k^{01}$, $L_k^{10}$ and $L_k^{11}$ as shown in Fig. 2.

<p class="text-center">
<img src="https://hackmd.io/_uploads/HJsDeNAekg.png" width=45% height=45%> </p>

$$\text{Fig. 2 } L_{k+1}\text{-block and its four corresponding sub-blocks: }L_k^{01}\ L_k^{01},\ L_k^{10} and L_k^{11}$$

Applying $(u, v)=(\lfloor x/2^k\rfloor, \lfloor y/2^k\rfloor)$, we realize that the empty cell $(x,y)$ is located within $L_{k}^{uv}$ where $0\le u, v\le 1$. Without loss of generality, let $(u, v)=(1, 0)$. Then, the position of the empty cell $(x,y)$ in $L_{k+1}$ becomes $(x', y')=(x-2^k, y)$ in $L_k$.
Based on the assumption, we know that each $L_k$-block can be construcked by $L_1$-blocks. Thus, we construct $L_k^{00}$, $L_k^{01}$, $L_k^{10}$ and $L_k^{11}$ by $L_k(2^k-1, 2^k-1)$, $L_k(2^k-1, 0)$, $L_k(x', y')$ and $L_k(0, 0)$, respectively, as illustrated in Fig. 3. In addition, we place one $L_1$-block, namely $L_1(1,0)\ (=L_1(u,v))$ marked as green, at the corners where $L_k^{00}$, $L_k^{01}$ and $L_k^{11}$ meet. This completes the construction of $L_{k+1}(x,y)$.

<p class="text-center">
<img src="https://hackmd.io/_uploads/rJ4_0axWkx.png" width=50% height=50%> </p>

$$\text{Fig. 3 Constructing } L_{k+1}(x,y) \text{ by }L_k(2^k-1, 2^k-1),\ L_k(2^k-1, 0),\ L_k(x', y'),\ L_k(0, 0) \text{ and } L_1^{10} \text{ when } (x,y)\in L_k{10}$$

For the other cases of $(u, v)=(0,0),\ (0,1),$ or $(1, 1)$, $L_{k+1}(x, y)$ can be similarly constructed. Therefore, by the principle of mathematical induction, we realize that the statement holds.
:::

:::danger
Note that after obtaining $(u,v)=(x/2^k, y/2^k)$, we could determine new position $(x',y')$ in $L_{k}^{uv}$ with respect to $(x,y)$ in $L_{k+1}$ according to Table 1.

Table 1 $(x',y')\in L_k^{uv}$ with respect to $(x, y)\in L_{k+1}(x,y)$

|$(u,v)$ |$(0,0)$ | $(0,1)$ | $(1,0)$ | $(1,1)$|
|:--:|:--:|:--:|:--:|:--:|
| $(x',y')$|$(x,y)$ |$(x,y-2^k)$ |$(x-2^k,y)$ |$(x-2^k,y-2^k)$ |

Depending on the position of $(x,y)$ in either $L_k^{00}$, $L_k^{00}$, $L_k^{00}$ or $L_k^{00}$, the construction of $L_{k+1}(x,y)$ can be achieved using the arrangements shown in Table 2.

Table 2 Construction rules of $L_{k+1}(x,y)$ with regard to $(x,y)\in L_k^{uv}$ where $0\le u,v \le 1$
|$L_k^{00}$ | $L_k^{01}$|$L_k^{10}$ | $L_k^{11}$|
|:-:|:-:|:-:|:-:|
| | ||  |

We refer to the last added $L_1$-block, marked as green, the *corner-block*. We add-in more information in the following.
|$(u,v)$ |$(0,0)$ | $(0,1)$ | $(1,0)$ | $(1,1)$|
|:--:|:--:|:--:|:--:|:--:|
| $(x',y')$|$(x,y)$ |$(x,y-2^k)$ |$(x-2^k,y)$ |$(x-2^k,y-2^k)$ |
| $(bx,by)$|$(0,0)$ |$(0,2^k)$ |$(2^k,0)$ |$(2^k,2^k)$ |
| $(cx,cy)$|$(2^k-1,2^k-1)$ |$(2^k-1,0)$ |$(0,2^k-1)$ |$(0,0)$ |

Note that $(cx,cy)$ denotes the *corner-cell* of each sub-block that meet the other 3 blocks (marked as green in the figure). Apparently, any corner-block is composed by 3 corner-blocks accordingly.
We summarize all the information:
$\qquad (u,v)=(\lfloor x/2^{k}\rfloor,\ \lfloor y/2^{k}\rfloor)$
$\qquad (x',y')=(u\cdot (x-2^k),\ v\cdot (y-2^k))$
$\qquad (bx,by)=(u\cdot 2^k,\ v\cdot 2^k)$
$\qquad (cx,cy)=((1-u)(2^k-1),\ (1-v)(2^k-1))$
where $0\le u, v\le 1$ given a certain $k$.

:::

Following the above discussion, we know that the number of $L_1$-blocks in $L_{k+1}$ is $g(k+1)=4\times g(k)+1$. In general,
$$
g(n) =
\begin{cases}
\ 1, \qquad\qquad\qquad\ \text{if }n=1;\\
\ 4g(n-1)+1, \quad \text{otherwise,}\\
\end{cases}
$$
for $n\ge 1$. That is,
:::danger
$$g(n)=\dfrac{4^n-1}{3}$$
:::
Below show an example of $L_4(11,5)$ consisting of $85\ (=\frac{4^4-1}{3})$ $L_1$-blocks.

---

For more information about the implementation of constructing $L_n(x,y)$ given $n, x, y$, please refer to https://hackmd.io/e6WnmL2WQ6Cq86fJ2HlEsQ.