Consider a $2^{1999} \times 2^{1999}$ square, with a single $1 \times 1$ square removed. Show that no matter where the small square is removed it is possible to tile this "giant square minus tiny square" with L-trominos.


marked as duplicate by MJD, user147263, Harish Chandra Rajpoot, user99914, Winther Sep 30 '15 at 0:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Try induction. Place the first L around the missing square so that you have a 2x2 block removed. Look at the 4 blocks that are left. Each looks like a square with a corner removed... $\endgroup$ – TravisJ Sep 28 '15 at 14:23
  • $\begingroup$ TravisJ's comment and your response sound like you were thinking about L-tromino, not L-tetromino? $\endgroup$ – J. J. Sep 28 '15 at 14:34
  • $\begingroup$ A tetromino contains 4 squares and 4 is an even number. So what sort of L-tetromino we are allowed to use??? $\endgroup$ – achille hui Sep 28 '15 at 15:02
  • $\begingroup$ @J.J., I thought the L-tetromino was made of 3 squares... not like a tetris L with 4 squares. That is an important clarification that should be made. The hint I provided should work for 3-square L, I don't know if it will work (and expect it will not work) for a 4-square L. $\endgroup$ – TravisJ Sep 28 '15 at 15:36
  • $\begingroup$ I meant the 3 square one. $\endgroup$ – guest Sep 28 '15 at 18:43

Let $\mathcal{D}_{1999}$ consist of the single $2^{1999} \times 2^{1999}$-square. For $1 \le n \le 1999$, define the family $\mathcal{D}_{n-1}$ recursively to contain the squares obtained from the squares of $\mathcal{D}_n$ by splitting them into four equal size squares.

For each $0 \le k \le 1999$ there is a unique dyadic cube $Q_k$ in $\mathcal{D}_k$ that contains the removed unit square. We prove by induction that one can fill $Q_k$ by L-trominos starting from $k=0$.

When $k=0$ there are no squares to fill, so we are done. Let then $k \ge 1$ and assume that the claim holds for $k-1$. The square $Q_k$ contains $Q_{k-1}$, and by filling $Q_{k-1}$ we get one fourth of $Q_k$ filled and are left with three $2^{k-1} \times 2^{k-1}$ subsquares to fill. Place one L-tromino so that it covers the three non-filled center-squares. Each of the three $2^{k-1} \times 2^{k-1}$ subsquares will then have one filled (removed) square, and we can fill them by induction.


Not the answer you're looking for? Browse other questions tagged or ask your own question.