5

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). six squares out of one big square

عبدو عيد
  • 3
Jose
  • 253
  • 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? – apnorton Jul 25 '13 at 20:51
  • @anorton, the smaller squares do NOT have to be equal in size. – Jose Jul 25 '13 at 20:53
  • @Jose, please choose more specific, informative titles (I've fixed this one) rather than general titles (which are largely useless). – Caleb Stanford Jul 25 '13 at 20:56
  • @Jose I understand the smaller squares don't have to be equal in size, but I want to make sure that the big square is $n\times n$. That's what I'm assuming, but just wanted to confirm. – apnorton Jul 25 '13 at 20:57
  • 1
    @DannyCheuk, if you can see this, please don't make edits like that. Changing 6 to $6$ was okay but trivial, and the other thing you did (replacing "for all natural numbers" by math symbols) only made the question less clear. – Caleb Stanford Jul 25 '13 at 20:58
  • 1
    @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. – Caleb Stanford Jul 25 '13 at 21:00
  • 2
    I don't see how writing $n\in\mathbb{N}_{\geq6}$ is making the problem less clear, but anyway, cool –  Jul 25 '13 at 21:01
  • @Goos Ah! That clears up quite a bit of confusion in my mind. :) – apnorton Jul 25 '13 at 22:03

1 Answers1

6

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.

André Nicolas
  • 507,029
  • This is correct. But why? – Jose Jul 25 '13 at 20:40
  • So for the indiction, I need to do 3 cases, one for 6, 7, and 8. – Jose Jul 25 '13 at 20:45
  • 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. – Ido Jul 25 '13 at 20:46
  • 1
    @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$. – Caleb Stanford Jul 25 '13 at 20:48
  • @Andre, but that isn't using strong induction, is it? Should string induction have an $n'$? – Jose Jul 25 '13 at 20:50
  • My mistake. You are correct. Still you are using the case of $4$. – Ido Jul 25 '13 at 20:52
  • 1
    @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. – André Nicolas Jul 25 '13 at 21:02
  • @AndréNicolas Is it possible to revise your answer to use strong induction where $n≥6$? I can then accept it ;) – Jose Jul 25 '13 at 21:10
  • I used strong induction. From the induction assumption that the result held for all $i\lt n$, I proved it held for $n$. Maybe your version of strong induction goes from all $i\le n$ to $n+1$. The more common one goes along my lines. Now of the strong induction hypothesis, I only used the case $n-3$, but that's perfectly fine. – André Nicolas Jul 25 '13 at 21:14
  • Or is it that you would like the symbol $n'$ used where I used $i$? If that symbol fits better the notation of your book, the change is easy to make. – André Nicolas Jul 25 '13 at 21:34
  • Thanks, what would $p(n)$ be and $p(n+1)$, explicitly? – Jose Jul 25 '13 at 21:35
  • $p(n)$ is the assertion that a square can be divided into $n$ squares. We use strong induction, proving that if for all $i$ with $6\le i\lt n$, we have $p(i)$, then we have $p(n)$. Or if you prefer, if for all $i$ such that $6\le i\le n$, $p(i)$ holds, then $p(n+1)$ holds. – André Nicolas Jul 25 '13 at 21:39
  • Thanks! Yes, $n'$ would be better than i – Jose Jul 25 '13 at 21:47