Induction on 3D grid with one cube missing

62 Views Asked by At

A three dimensional chessboard of size $2^n$x$ 2^n $x$ 2^n$ with one 1 x 1 x 1 cube missing can be completely covered by 2 x 2 x 2 cubes, each with one 1 x 1 x 1 cube missing.

The base case is quite clear, and assuming the induction hypothesis for $n=k$ is fine, but then how do we construct an answer for $n=k+1$?

1

There are 1 best solutions below

0
On BEST ANSWER

Hint: We can build a $2^{k+1} \times 2^{k+1} \times 2^{k + 1}$-size board with one cube missing by combining $8$ $2^{k} \times 2^{k} \times 2^{k}$-size boards, each with one cube missing, together with an extra $2 \times 2 \times 2$-size block with a cube missing.