lx. Tromino Tiling

Problem. Tile a $2^k\times 2^k$ board with one missing cell using L-shaped trominoes.

Answer: always possible, by divide and conquer: split into four quadrants, place one tromino at the centre covering one cell of each quadrant that does not contain the hole, and recurse on the four quadrants (each now has exactly one missing cell).

void trominoTile(vector<vector<int>>& g, int r, int c, int size, int hr, int hc, int& id) {  // hole at (hr, hc) inside the square
    if (size == 1) return;
    int h = size / 2, t = ++id;
    int qr[4] = {r, r, r + h, r + h}, qc[4] = {c, c + h, c, c + h};
    int cr[4] = {r + h - 1, r + h - 1, r + h, r + h}, cc[4] = {c + h - 1, c + h, c + h - 1, c + h};  // centre cells
    for (int q = 0; q < 4; q++) {
        bool hasHole = hr >= qr[q] && hr < qr[q] + h && hc >= qc[q] && hc < qc[q] + h;
        if (hasHole) trominoTile(g, qr[q], qc[q], h, hr, hc, id);
        else { g[cr[q]][cc[q]] = t; trominoTile(g, qr[q], qc[q], h, cr[q], cc[q], id); }
    }
}

Proof: the recursion is valid

By induction on $k$. The four central cells of the board form a $2\times 2$ block with one cell in each quadrant. The quadrant containing the hole keeps it; the three central cells of the other quadrants form an L-tromino and are covered by it. Each quadrant is then a $2^{k-1}$ board with exactly one missing cell, tiled by the induction hypothesis; the base case $1\times 1$ is the hole itself. The tile count is $(4^k-1)/3$. Checked for every hole position up to $16\times 16$ and for sampled holes on $32\times 32$ (each tile has 3 cells in a $2\times 2$ box). Other boards: an $n\times n$ board with one missing cell is tileable iff $3\mid n^2-1$ (always for $n\not\equiv 0(\mathrm{mod}3)$), except a few small cases (the $5\times 5$ board fails for some hole positions).