Squares

Stump your fellow simians.
User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Squares

Post by DanishDynamite » Wed Aug 11, 2004 4:14 pm

Prove that for any whole number N > 5, a square can be divided into N squares.

(I suspect this is the type of problem where you either see the answer fairly quickly or it takes you hours to see the solution. I was clearly in the last category.)

User avatar
gnome
Posts: 22244
Joined: Tue Jun 29, 2004 12:40 am
Location: New Port Richey, FL
Has thanked: 382 times
Been thanked: 408 times

Re: Squares

Post by gnome » Wed Aug 11, 2004 5:54 pm

DanishDynamite wrote:Prove that for any whole number N > 5, a square can be divided into N squares.

(I suspect this is the type of problem where you either see the answer fairly quickly or it takes you hours to see the solution. I was clearly in the last category.)
Ok... for even N's, take a square from the lower right corner and adjust its size so that the remaining space can be filled with an odd number of squares. The larger the corner square, the more small squares can fill the rest.

For odd N's... cut out a large square in the center of the bottom edge. Adjust size to need as with the even solution.

Hardly rigorous, but I think it makes it clear enough.

User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Re: Squares

Post by DanishDynamite » Wed Aug 11, 2004 6:04 pm

gnome wrote:
DanishDynamite wrote:Prove that for any whole number N > 5, a square can be divided into N squares.

(I suspect this is the type of problem where you either see the answer fairly quickly or it takes you hours to see the solution. I was clearly in the last category.)
Ok... for even N's, take a square from the lower right corner and adjust its size so that the remaining space can be filled with an odd number of squares. The larger the corner square, the more small squares can fill the rest.

For odd N's... cut out a large square in the center of the bottom edge. Adjust size to need as with the even solution.

Hardly rigorous, but I think it makes it clear enough.
"Hardly rigorous" seems right. :D

I can understand your solution for even N's as it is the one I found, but your solution for odd N's leaves me puzzled.

Could you post a diagram?

User avatar
gnome
Posts: 22244
Joined: Tue Jun 29, 2004 12:40 am
Location: New Port Richey, FL
Has thanked: 382 times
Been thanked: 408 times

Re: Squares

Post by gnome » Wed Aug 11, 2004 6:35 pm

DanishDynamite wrote:
gnome wrote:Ok... for even N's, take a square from the lower right corner and adjust its size so that the remaining space can be filled with an odd number of squares. The larger the corner square, the more small squares can fill the rest.

For odd N's... cut out a large square in the center of the bottom edge. Adjust size to need as with the even solution.

Hardly rigorous, but I think it makes it clear enough.
"Hardly rigorous" seems right. :D

I can understand your solution for even N's as it is the one I found, but your solution for odd N's leaves me puzzled.

Could you post a diagram?
...

Actually I'm incorrect, you still get an even number. Let me work on it some more.

User avatar
ceptimus
Posts: 1084
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
Has thanked: 56 times
Been thanked: 41 times

Post by ceptimus » Wed Aug 11, 2004 7:21 pm

Trying to hide this in a spoiler ('select' it, or Ctrl-A to view)

<table bgcolor=white><tr><td>
Given any existing arrangement, any existing square can be subdivided into four equal ones, yielding an extra three squares in total. So if we can solve for any three consecutive numbers, then all numbers greater than that are proven soluble by induction.
<pre>+-+-+-+<br>| | | |<br>+-+-+-+<br>| | | = 6 (and therefore 9, 12, 15...)<br>| +-+<br>| | |<br>+---+-+
+-+-+---+<br>| | | |<br>+-+-+ |<br>| | | |<br>+-+-+---+ = 7 (and therefore 10, 13, 16...)<br>| | |<br>| | |<br>| | |<br>+---+---+
+-+-+-+-+<br>| | | | |<br>+-+-+-+-+<br>| | |<br>| +-+ = 8 (and therefore 11, 14, 17...)<br>| | |<br>| +-+<br>| | |<br>+-----+-+<br></pre>
</td></tr></table>

User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite » Wed Aug 11, 2004 7:44 pm

The cepter is a must, for ceptimus!

A different inductive proof than mine, but just as valid. Well done!

(My proof was based on dividing the case into even and odd numbers of squares. The bit which took me forever to see was how to make a division into 7 squares.)

User avatar
gnome
Posts: 22244
Joined: Tue Jun 29, 2004 12:40 am
Location: New Port Richey, FL
Has thanked: 382 times
Been thanked: 408 times

Post by gnome » Thu Aug 12, 2004 12:01 am

Beautiful. I was approaching that, but I don't think I could have made the argument so elegantly.

:clap: