Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many squares in progressively decreasing size can be created from a rectangle of dimension $a\;X\;b$

For example, consider a rectangle of dimension $3\;X\;8$ enter image description here

As you can see, the biggest square that you can carve out of it is of dimension $3\;X\;3$ and they are ABFE and EFGH

The next biggest square is of dimension $2\;X\;2$ which is GJIC

Followed by two other squares of dimension $2\;X\;2$ which are JHLK and KLDI

So the answer is 5.

Is there any mathematical approach of solving it for a rectangle of arbitrary dimension?

share|improve this question
    
I have full faith that you have the stamina to type out the word "number" rather than just typing "no," so please use "number instead! –  rschwieb Apr 30 '13 at 20:13
    
@rschwieb: Its more of a habit rather than a stamina. Sorry about that –  Abhijit May 1 '13 at 5:31
add comment

2 Answers

up vote 1 down vote accepted

Following the algorithm you seem to be doing, cutting the largest possible square off a rectangle, it is a simple recursive algorithm. If you start with an $n \times m$ rectangle with $n \ge m$, you will cut off $\lfloor \frac nm \rfloor m \times m$ squares and be left with a $(n-\lfloor \frac nm \rfloor m) \times m$ rectangle. Then you remove as many $(n-\lfloor \frac nm \rfloor m)$ squares as you can and continue. The smallest square will be the greatest common divisor of $n$ and $m$

share|improve this answer
add comment

Mathematically, start with the square pyramidal number under the rectangle's area, and compare with the list of known tightly packed rectangles, which usually have low excess values. You could see if a given rectangle is at squaring.net for known perfect packings.

It's quickly a hard problem. For example, can a $189\times189$ or $190\times188$ rectangle be cut into 47 decreasing squares? This problem is too combinatorially hard to solve at the moment.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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