Qm
BrainteasersJane StreetSIG

Tiling a board with a hole using L-shaped tiles

tilinginductiontrominoesrecursion

An L-tromino is a 2 by 2 square with one corner missing: three squares in an L shape.

Take an 8 by 8 board and remove any one square. There are 63 squares left, and 63 = 21 × 3.

Prove that the remaining board can always be tiled with 21 L-trominoes, wherever the missing square is. Then show that the same is true for a 2 to the n by 2 to the n board with one square removed, for every n.

Show a hint

Cut the board into four quarters. The missing square is in one quarter. Place a single L-tromino at the centre of the board so that it covers one square from each of the other three quarters. Now every quarter is a smaller board with one square missing.

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Induction and Recursive Structure in PuzzlesMathematical InductionCatalan NumbersColouring and Tiling ArgumentsCommon Knowledge and the Blue-Eyed Islanders

Related questions

The visitor who says she sees at least two blue-eyed peopleBinary strings with no two 1s in a rowThe blue-eyed islandersTiling a hexagon with lozenges1, 1, 2, 5, 14, 42, what next?
All questions →