I'm trying to prove that for all natural numbers $n \ge 6$, a square can be divided into $n$ smaller squares.

The smaller squares do not need to be of the same size.

So for induction, the base case is $P(6)$, which is that a square can be broken into $6$ squares (I can draw a picture to prove this).

  • $\begingroup$ To clarify, you mean that a square of dimensions $n\times n$ can be divided into $n$ smaller squares? That is, a $6\times6$ square can be broken into 6 smaller squares? $\endgroup$
    – apnorton
    Jul 25 '13 at 20:51
  • $\begingroup$ @anorton, the smaller squares do NOT have to be equal in size. $\endgroup$
    – Jose
    Jul 25 '13 at 20:53
  • $\begingroup$ @Jose, please choose more specific, informative titles (I've fixed this one) rather than general titles (which are largely useless). $\endgroup$
    – 6005
    Jul 25 '13 at 20:56
  • 1
    $\begingroup$ @anorton The size of the big square does not matter. The smaller squares do not have to go along any specific grid lines. The side length of a smaller square is allowed to be any real number. $\endgroup$
    – 6005
    Jul 25 '13 at 21:00
  • 1
    $\begingroup$ I don't see how writing $n\in\mathbb{N}_{\geq6}$ is making the problem less clear, but anyway, cool $\endgroup$
    – user67258
    Jul 25 '13 at 21:01

Hint: You only need to do it for $6$, $7$, and $8$. For these, you need to produce explicit splittings.

But after that, anything differs by $3$ from an earlier case. and adding $3$ squares is easy, we just do the natural splitting of an existing square.

If one wants to do a formal induction, let $n \gt 8$. Suppose the result is true for all $i$ such that $6\le i \lt n$. We want to show it holds at $n$. By the induction assumption, it holds at $n-3$. Split one of the squares of the splitting into $n-3$ squares into $4$ squares. That gives us a splitting into $n$ squares.

  • $\begingroup$ This is correct. But why? $\endgroup$
    – Jose
    Jul 25 '13 at 20:40
  • $\begingroup$ So for the indiction, I need to do 3 cases, one for 6, 7, and 8. $\endgroup$
    – Jose
    Jul 25 '13 at 20:45
  • $\begingroup$ I'm not sure what he meant, but I think that you only need to do it for $4$, $6$, $7$, $8$ and $9$. Maybe he dropped the cases $4$ and $9$ since they are easy. $\endgroup$
    – Ido
    Jul 25 '13 at 20:46
  • $\begingroup$ @Ido, no. Why would you need to do 4 and 9? You can construct 6,7, and 8 and then the induction holds in general for $n \ge 6$. $\endgroup$
    – 6005
    Jul 25 '13 at 20:48
  • 1
    $\begingroup$ @Ido: That's a matter of semantics. We are using the trivial fact that a square can be split into $4$ equal squares. Though it could be called the case $n=4$, it will cause needless confusion to call it that, since it may give the impression the induction begins at $4$. However, it does not: we can't split a square into $5$ squares. $\endgroup$ Jul 25 '13 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.