Question 1203906: For some values of 𝑛, it is possible to cut a large square into 𝑛 smaller
squares (which need not be of equal size).
For example, it not possible when 𝑛 = 5 but is possible when 𝑛 = 6, as
shown below.
Find, with proof, all values of 𝑛 for which it is possible to do this.
Found 2 solutions by ikleyn, mccravyedwin:
Answer by ikleyn(52781)   (Show Source):
You can put this solution on YOUR website! .
For nice and accurate solution to this problem, look at this source
https://courses.grainger.illinois.edu/cs173/sp2014/A-lecture/Homework/hw6-solutions.pdf
problem 2.
To see nice plots, look at this source
https://www.geeksforgeeks.org/puzzle-dividing-a-square-into-n-smaller-squares/
Enjoy ( ! )
Answer by mccravyedwin(407)  (Show Source):
You can put this solution on YOUR website!
  
(1) The first figure above proves that we can cut a square into 4 smaller
squares.
(2) The second figure above proves that we can cut a square into 6 smaller
squares.
(3) The third figure above proves that we can cut a square into 8 smaller
squares.
LEMMA: If we can cut a square into n smaller squares, we can also cut a square
into n+3 smaller squares.
Proof: Suppose we have a square cut into smaller squares. Now suppose we cut one
of its smaller squares into 4 even smaller squares. We then will have lost the
square that we cut in the count, but we will have gained 4 squares, for a net
gain of 3 squares. QED
Therefore, by the LEMMA, we can also cut a square into 7 smaller squares, by
picking one of the squares in the first figure and cutting it into 4 smaller
squares.
So we have proved that we can cut a square into 6, 7, or 8 smaller squares.
Every integer divided by 3 leaves a remainder of 0, 1, or 2.
So every integer is either a multiple of 3, 1 more than a multiple of 3,
or 2 more than a multiple of 3.
Proof by induction: Assume that up through k, where  , it is possible
to cut a square into k smaller squares. Then by the LEMMA, a square can be cut
into k+1 squares, by cutting a square in (k+1)-3 or k-2 smaller squares, and
then cutting any one of its smaller squares into 4 even smaller squares, cutting
the square into (k-2)+3 or k+1 squares.
So we can cut any square into n smaller squares except for n=2,3,5. QED
Edwin
|
|
|
