Remove any single square from an 8 by 8 board. Can the remaining 63 squares always be covered exactly by 21 L shaped trominoes with no overlaps and no overhang? Prove your answer and say what the divisibility count alone establishes.

Remove any single square from an 8 by 8 board. Can the remaining 63 squares always be covered exactly by 21 L shaped trominoes with no overlaps and no overhang? Prove your answer and say what the divisibility count alone establishes.

Approach: Induct on boards of size 2^n by 2^n with one square removed, and place a single piece at the meeting point of the four quadrants to reduce to four smaller copies.

Yes, for every removed square. Induct on n over 2^n by 2^n boards with one square missing. The base case 2 by 2 minus one square is a single L tromino. For the step, cut the board into four quadrants of side 2^{n-1}. The missing square lies in one quadrant, and one tromino placed at the centre covers exactly one square in each of the other three quadrants, so all four quadrants become deficient boards of half the size and the induction applies. Taking n as 3 tiles the 8 by 8 board minus any square, using 63/3 or 21 trominoes. The divisibility check that 3 divides 63 is necessary and settles nothing on its own: a 5 by 5 board minus one square also has a multiple of 3 squares, and for most choices of removed square no tromino tiling exists.

Follow-up: For which single removed squares does a 5 by 5 deficient board admit an L tromino tiling?

Key concepts: induction on quadrants, deficient board, divisibility check.