0

In the following problem (should be solved using the mathematical induction method):

You are given $n$ arbitrary squares. Prove that they can be divided into parts so that from the obtained parts you can make a square.

I got confused when started proving the induction step.

mhmhhmhmhm
  • 121
  • I would guess, that if you want to prove it for n arbitrary squares and you know that you can divide and rearrange the first n-1 squares into 1 square, then you only need to show that you can divide and rearrange 2 squares into 1. – Leander Tilsted Kristensen Sep 25 '19 at 16:05
  • 1
    I think you have to describe the method for $n=2$ squares first. Then, for $n=3$, you use the same method for two of them and then again for that resulting square and the third one. Are you getting the idea? If the method is valid for $n=p$ then is also valid for $n=p+1$ squares (because is always based on the method you described for the two squares). – Pspl Sep 25 '19 at 16:05

1 Answers1

1

The answer to this question is quite simple (and trivial). Maybe you didn't research the matter properly.

First of all, the problem is "only" a problem for $n \ge 2$ (we don't have to lose our time with merging one square to itself, right?!).

Using induction, we have to prove, at first, that we can divide two squares into a certain number of parts in a way to rearrange those parts into another square. If the squares are equal to each other, we can do the following (for instance):

merging two equal squares

On the other side, if the squares are different then:

merging two different squares

It's easy to see (and conclude) that the previous method works for any situation (for two arbitrary squares, they can be equal to each other or different; there's no other possibility).

The first induction step is done!

Then, let's assume that we can do our merging with $p$ squares (i.e, your conjecture is valid for $n=p$). If we have $p+1$ squares then, by hypotheses, we can merge the first $p$ squares into one first and then we can do the merging of this one with the $(p+1)$-th square (because we already proved that we can do it with two squares). So, if the merging is possible for $p$ squares, it's also possible for $p+1$.

Then, by induction, your conjecture is proved. $QED$

Pspl
  • 566