Prove an n x n square can be tiled with 3x1 slabs and one 1x1 slab (divide and conquer)
If I have a wooden slab of size 3m x 1m, and the wooden slab can tile any n x n room with such slab if n is divisible by 3. Is it true that for every n> 3 that is not divisible by 3, one can tile an n x n square with such slab and a single 1m x 1m slab? I know that it's possible. However, how can I prove this using divide and conquer?
I'll provide an example for clarification. If I have a 4x4 room, I can tile all the room with 3x1 wooden slabs and one 1x1 wooden slab.
You can cover them all. My apologies for not drawing pictures but alas I don't have the tools.
Let the square be of side K
a/ If K = 3n + 1 then we divide the square into a top left 3n x 3n square, a vertical 3n x 1 rectangle, a horizontal 3n x 1 rectangle and a 1 x 1 square at the bottom right
b/ if K = 3n+2 (and n>0) then we divide the square into a 2 x 3n rectangle along the top (starting at the left of the KxK square), a 3n x 2 rectangle along the right (starting at the top of the KxK square), a 2 x 3n rectangle along the bottom (starting at the right of the KxK) and a 3n x 2 rectangle along the left (starting at the bottom of the KxK), leaving a 3n+2-4 sided central square. But 3n+2-4 = 3n-2 = 3(n-1)+1 so by a/ we can cover that.