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.

Given a rectangle of sides $m$ and $n$. $( m,n \in [1,1000] )$ We can cut the rectangle into smaller identical pieces such that each piece is a square having maximum possible side length with no left over piece of the rectangle. How could we count this squares of maximum size?

For example: If the rectangle is of size $6 \times 9$. We can cut it into 54 squares of size $1 \times 1$, $0$ of size $2 \times 2$, $6$ of size $3 \times 3$, $0$ of size $4 \times 4$, $0$ of size $5 \times 5$ and $0$ of size $6 \times 6$. The minimum number of squares of maximum size that can cut is $6$.

My approach: I computed the product $m \times n$ say $K$.Then found the maximum perfect square that divides $K$. The quotient of this division seems to be the required answer. But unfortunately it's doesn't seem to yield correct answer. Where exactly I am going wrong?

share|improve this question

2 Answers 2

You want to cut the rectangle in squares with side length $s$ without pieces of the rectangle left over, so $s$ must divide both $m$ and $n$. To maximum possible value of $s$ is thus the greatest common divisor of $m$ and $n$: $$s = \gcd(m,n)$$

To find the number of squares the rectangle is cut into, you need to find how many squares fit in the length of the rectangle $\left(\frac{m}{\gcd(m,n)}\right)$ and multiply that with the amount of squares that fit in the width of the rectangle $\left(\frac{n}{\gcd(m,n)}\right)$:

$$ \left(\frac{m}{\gcd(m,n)}\right) \times \left(\frac{n}{\gcd(m,n)}\right) = \frac{m \times n}{\gcd(m,n)^2} $$

share|improve this answer

You should find the GCD of the sides of the rectangle, i.e., the GCD of $m$ and $n$. This is the side of the largest square you can use to fill in the entire rectangle. To find out the number of squares, calculate $\frac{mn}{\gcd(m,n)^2}$. For your example, $\gcd(6,9) = 3$. The number of squares = $6*\frac{9}{3^2}=6$.

share|improve this answer
    
Someone who is bad at math will not understand this answer, you're going way too fast. –  timvermeulen May 31 '13 at 21:30
1  
@timjver - my answer is identical to what you posted after me. If he had a problem with my answer he could have asked and I would have answered. Why downvote a correct answer because you think it is too terse? –  svenkatr May 31 '13 at 21:35
    
The only reason I posted after you is because I motivated my answer more elaborately. But you're right, in essence our answers are equal. –  timvermeulen May 31 '13 at 22:02

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.