# Partition a square into $k$ non-overlapping squares

Why is it for every $k\in\mathbb{N}\setminus\{2,3,5\}$ possible, to partition a square into $k$ non-overlapping squares (they have not to have the same size).

This should be proved with induction. The induction basis $k=1$ is clear.

But what should I do in the induction step?

• If it is not possible with 2,3 or 5 the induction basis should be $k = 6$. – Rafael Wagner Oct 3 '17 at 16:37
• Instead of induction, it will be easier to first prove the case for all even $k \ge 4$ and then use this result to prove the case for all odd $k \ge 7$. – achille hui Oct 3 '17 at 16:47
• Well the case $k=4$ is clear, but I already have problems with $k=6$. – user337073 Oct 3 '17 at 16:53
• @R.A. draw two pairs of lines, one horizontal and one vertical at the $1/3$ and $2/3$ position along the sides. You split the original square into a $3 \times 3$ grid of small squares. Along the grid lines, cut out a square of side $2/3$ at one corner, you then split the remaining L shade into 5 squares of side $1/3$. – achille hui Oct 3 '17 at 17:18

Instead of induction, it will be easier to prove the results directly.

We are going to show for all $n \ge 2$, we can split the square into $k = 2n$ and $k = 2n+3$ squares.

This will cover the cases for all even $k \ge 4$ and all odd $k \ge 7$. This leaves us with $k = 1, 2, 3, 5$. Since $k = 1$ is clearly possible, we can conclude for all $k \in \mathbb{N} \setminus \{ 2, 3, 5 \}$, we can split the square into $k$ smaller squares.

Let's back to the proof. WOLOG, we will assume the original square is the unit square $[0,1] \times [0,1]$.

• To split the unit square into $2n$ smaller squares.

We first cut out a square of side $1 - \frac1n$ along the lines $x = \frac1n$ and $y = \frac1n$. We then split the remaining $L$-shape into $2n-1$ squares of side $\frac1n$ ( the $\color{red}{\verb/red squares/}$ in figure below).

• To split the unit square into $2n+3$ smaller squares.

We first split the unit square into $2n$ smaller squares like above. We then split the square of side $1 - \frac1n$ into 4 equal pieces (the $\color{blue}{\verb/blue squares/}$ in figure below )

As an illustration of this procedure, following is a picture showing how to split the unit square into $11 = 2\cdot 4 + 3$ smaller squares.