How Many Police Teams Are Needed for Optimal Area Division?

[kent davidge]

Homework Statement

Police will be sent to conduct their work on a site which is a rectangular region of sides 3.9 km and 9.1 km. To make their work easier, the region will be divided into square regions, each one having the largest possible area, and such that their sum equals the original region. One police team will be sent to each such region. How many teams have to be sent?

Homework Equations

The Attempt at a Solution

(If you find this text bad looking that's because it was in my native language and I (poorly) translated it to English.)

So I think the problem is asking how many small regions we can divide the total region into such that the small regions have the largest possible area.

My attempt at a solution:

Let the total area be $A = 3.9 \times 9.1 (km)^2$.

Let the small regions be $a$. As their sum should equal the total area, we have $ka = A, k \in \mathbb{N}$, or $a = A / k$, and we must find the largest $a$ which is equal to the RHS of the last equality. This happens when $k$ assumes the smalest possible value, 1. But, no. That's not the answer. The official answer is 21. What can we do?

 

[LCKurtz]

Homework Statement

Police will be sent to conduct their work on a site which is a rectangular region of sides 3.9 km and 9.1 km. To make their work easier, the region will be divided into square regions, each one having the largest possible area, and such that their sum equals the original region. One police team will be sent to each such region. How many teams have to be sent? (It does).

Homework Equations

The Attempt at a Solution

(If you find this text bad looking that's because it was in my native language and I (poorly) translated it to English.)

So I think the problem is asking how many small regions we can divide the total region into such that the small regions have the largest possible area.

My attempt at a solution:

Let the total area be $A = 3.9 \times 9.1 (km)^2$.

Let the small regions be $a$. As their sum should equal the total area, we have $ka = A, k \in \mathbb{N}$, or $a = A / k$, and we must find the largest $a$ which is equal to the RHS of the last equality. This happens when $k$ assumes the smalest possible value, 1. But, no. That's not the answer. The official answer is 21. What can we do?

Since the squares must fit exactly, the length of the side of the squares must evenly divide both the length and width. Simple trials should work.

 

[kent davidge]

Since the squares must fit exactly, the length of the side of the squares must evenly divide both the length and width. Simple trials should work.

Is not there a less painful way?

 

[LCKurtz]

How painful is it when the first or second thing you try works?

 

[LCKurtz]

Alternatively you could multiply both sides by 10 to make it 39 by 91. Factor those to see what is common.

 

[kent davidge]

Ok. So here is my satisfactory attempt

$L_1 = 9.1 km$, $L_2 = 3.9 km$. $A = L_1 L_2$

$m \sqrt{a} + n \sqrt{a} = L_1 + L_2$. Also $A = k a, k \in \mathbb{N}$. Substituting

$k(L_1 + L_2)^2/(m+n)^2 = L_1 L_2$ or $k = L_1 L_2 (m + n)^2 / (L_1 + L_2)^2 = (21/ (100 / (m + n)^2))$. We must have both $m$ and $n$ naturals and also $k$ natural. $21$ has $1,3,7,21$ as its multiples. This means $100 / (m+n)^2$ must be one of those. The only natural that divided by $100$ gives one of those multiples is $100$ itself. So $k = 21$.

 

[tnich]

Ok. So here is my satisfactory attempt

$L_1 = 9.1 km$, $L_2 = 3.9 km$. $A = L_1 L_2$

$m \sqrt{a} + n \sqrt{a} = L_1 + L_2$. Also $A = k a, k \in \mathbb{N}$. Substituting

$k(L_1 + L_2)^2/(m+n)^2 = L_1 L_2$ or $k = L_1 L_2 (m + n)^2 / (L_1 + L_2)^2 = (21/ (100 / (m + n)^2))$. We must have both $m$ and $n$ naturals and also $k$ natural. $21$ has $1,3,7,21$ as its multiples. This means $100 / (m+n)^2$ must be one of those. The only natural that divided by $100$ gives one of those multiples is $100$ itself. So $k = 21$.

This is quite difficult to follow, especially since you have not defined what you mean by k, m and n and you seem to have changed your mind about what (at least some of) them mean between the second and fourth line.
Also, how did you decide that (apparently) $L_1L_2 = 21$ and $(L_1+L_2)^2 = 100$?

 

[LCKurtz]

@kent davidge Did you read post #5?

 

[kent davidge]

@kent davidge Did you read post #5?

Yes, and, honestly, I didn't realize how to come up with an answer based on it.

This is quite difficult to follow

To be more clear

Let
- $L_1$ and $L_2$ be the two given sides length;
- $A$ the total area;
- $a$ the small areas which are obtained by dividing the total area.

From the problem statement we know that the sum of the small areas should equal the total area, so $A = L_1L_2 = ka$ for some
natural $k$. This is the target unknown variable. As the small regions are squares their length is equal to $\sqrt{a}$. Now, the side $L_1$ should be equal to an amount of the sides of the small regions: $L_1 = m \sqrt{a}$ for some natural $m$, and the same holds for $L_2 = n \sqrt{a}$. So we have

$L_1 + L_2 = \sqrt{a}(m + n)$, or $a = (L_1+L_2)^2/(m+n)^2$. Substitute this expression for $a$ into $A = ka$ and solve for $k$ to get $k = L_1L_2 / ((L_1+L_2)^2/(m+n)^2)$. Puting in the values $k = 21 / (100 / (m+n)^2)$.

Now $k,m,n$ must all be positive integers. This means that $100 / (m+n)^2$ must be a multiple of $21$, i.e., it should be an element of $\{1,3,7,21 \}$. The only possibility to get one of those by dividing $100$ by an integer (because $(m+n)^2$ is an integer) is when we divide $100$ by $100$. In such case we get $1$ in the denominator, that is, $k = 21$.

 

[tnich]

Yes, and, honestly, I didn't realize how to come up with an answer based on it.

To be more clear

Let
- $L_1$ and $L_2$ be the two given sides length;
- $A$ the total area;
- $a$ the small areas which are obtained by dividing the total area.

From the problem statement we know that the sum of the small areas should equal the total area, so $A = L_1L_2 = ka$ for some
natural $k$. This is the target unknown variable. As the small regions are squares their length is equal to $\sqrt{a}$. Now, the side $L_1$ should be equal to an amount of the sides of the small regions: $L_1 = m \sqrt{a}$ for some natural $m$, and the same holds for $L_2 = n \sqrt{a}$. So we have

$L_1 + L_2 = \sqrt{a}(m + n)$, or $a = (L_1+L_2)^2/(m+n)^2$. Substitute this expression for $a$ into $A = ka$ and solve for $k$ to get $k = L_1L_2 / ((L_1+L_2)^2/(m+n)^2)$. Puting in the values $k = 21 / (100 / (m+n)^2)$.

Now $k,m,n$ must all be positive integers. This means that $100 / (m+n)^2$ must be a multiple of $21$, i.e., it should be an element of $\{1,3,7,21 \}$. The only possibility to get one of those by dividing $100$ by an integer (because $(m+n)^2$ is an integer) is when we divide $100$ by $100$. In such case we get $1$ in the denominator, that is, $k = 21$.

Thank you, that is much clearer. I still don't understand how you know that $L_1L_2 / (L_1+L_2)^2 = 21/100$. Did you factor 1.3² our of the numerator and denominator? In that case, it seems that you already know $m=3$ and $n=7$.

 

[kent davidge]

I just did $L_1 L_2 = 3.9 \times 9.1 = 35.49$, and $(L_1 + L_2)^2 = (3.9 + 9.1)^2 = (13)^2 = 169$, which results in $35.49 / 169 = 21 / 100$.

 

[Ray Vickson]

Yes, and, honestly, I didn't realize how to come up with an answer based on it.

To be more clear

Let
- $L_1$ and $L_2$ be the two given sides length;
- $A$ the total area;
- $a$ the small areas which are obtained by dividing the total area.

From the problem statement we know that the sum of the small areas should equal the total area, so $A = L_1L_2 = ka$ for some
natural $k$. This is the target unknown variable. As the small regions are squares their length is equal to $\sqrt{a}$. Now, the side $L_1$ should be equal to an amount of the sides of the small regions: $L_1 = m \sqrt{a}$ for some natural $m$, and the same holds for $L_2 = n \sqrt{a}$. So we have

$L_1 + L_2 = \sqrt{a}(m + n)$, or $a = (L_1+L_2)^2/(m+n)^2$. Substitute this expression for $a$ into $A = ka$ and solve for $k$ to get $k = L_1L_2 / ((L_1+L_2)^2/(m+n)^2)$. Puting in the values $k = 21 / (100 / (m+n)^2)$.

Now $k,m,n$ must all be positive integers. This means that $100 / (m+n)^2$ must be a multiple of $21$, i.e., it should be an element of $\{1,3,7,21 \}$. The only possibility to get one of those by dividing $100$ by an integer (because $(m+n)^2$ is an integer) is when we divide $100$ by $100$. In such case we get $1$ in the denominator, that is, $k = 21$.

Why not make a much simpler formulation? If you divide the big rectangle into $m \times n$ small equal rectangles, the height of each small rectangle is $h = 3.9/m$ and the width is $w = 9.1/n.$ Since each small rectangle must be a square, we need $h=w$, so $3.9/m = 9.1/n$, or $n = (9.1/3.9) m = (91/39)m.$

Therefore, you need to find a pair of positive integers m and n so that $n = (91/39) m$, and $m$ should be as small as possible, so that there are the fewest possible small squares. If we take the brute-force method of trying $m=1,2,3,\ldots$ we find that $m = 3$, giving $n = 7$ and a total of $3 \times 7 = 21$ small squares, exactly as you have found.

 

[LCKurtz]

Alternatively you could multiply both sides by 10 to make it 39 by 91. Factor those to see what is common.

Yes, and, honestly, I didn't realize how to come up with an answer based on it.

Since you have the answer another way, I will explain further. $39=3\cdot 13,~91 = 7\cdot 13$. So, $13$, being the highest common factor of both will do for the side of the square. You need $3$ in one direction and $7$ in the other. Re-scaling back down gives a square $1.3\times 1.3$ with $21$ squares.

 

[kent davidge]

Why not make a much simpler formulation? If you divide the big rectangle into $m \times n$ small equal rectangles, the height of each small rectangle is $h = 3.9/m$ and the width is $w = 9.1/n.$ Since each small rectangle must be a square, we need $h=w$, so $3.9/m = 9.1/n$, or $n = (9.1/3.9) m = (91/39)m.$

Therefore, you need to find a pair of positive integers m and n so that $n = (91/39) m$, and $m$ should be as small as possible, so that there are the fewest possible small squares. If we take the brute-force method of trying $m=1,2,3,\ldots$ we find that $m = 3$, giving $n = 7$ and a total of $3 \times 7 = 21$ small squares, exactly as you have found.

Since you have the answer another way, I will explain further. $39=3\cdot 13,~91 = 7\cdot 13$. So, $13$, being the highest common factor of both will do for the side of the square. You need $3$ in one direction and $7$ in the other. Re-scaling back down gives a square $1.3\times 1.3$ with $21$ squares.

These are quickly but harder to figure out ways of doing it. Thank you @Ray Vickson and @LCKurtz .

 

[tnich]

These are quickly but harder to figure out ways of doing it. Thank you @Ray Vickson and @LCKurtz .

Do you know how to find the greatest common divisor (gcd) of two integers?

 

[kent davidge]

Do you know how to find the greatest common divisor (gcd) of two integers?

Something like this?

Integers: 30 and 45. Greatest common divisor: 5.

 

[tnich]

Something like this?
View attachment 221842 Integers: 30 and 45. Greatest common divisor: 5.

Yes. That is Euclid's algorithm for the gcd. Do you see that if you apply it to 91 = 10(9.1) and 39 = 10(3.9) that you will get the side of the largest square (times 10) that will work for this problem?

 

[tnich]

Yes. That is Euclid's algorithm for the gcd. Do you see that if you apply it to 91 = 10(9.1) and 39 = 10(3.9) that you will get the side of the largest square (times 10) that will work for this problem?

However, you are not doing it quite correctly. The first time you get a remainder that divides the previous remainder, that is the gcd. Notice that 15 divides both 30 and 45.

 

[tnich]

However, you are not doing it quite correctly. The first time you get a remainder that divides the previous remainder, that is the gcd. Notice that 15 divides both 30 and 45.

$\begin{matrix} dividend & divisor & remainder\\ 45& 30& 15\\ 30 & 15 & 0 \end{matrix}$

 

[Michael Hardy]

$$\begin{align*} 91 & = 7 \times 13 \\ 39 & = 3\times13 \end{align*}$$
Either prime factorization, as above, or Euclid's algorithm, will reveal that $91$ and $39$ have no factor in common bigger than $13$.
So $1.3\text{ km}\times1.3\text{ km}$ squares will go $3$ times into $3.9\text{ km}$ and $7$ times into $9.1\text{ km},$ forming a ##3\times7# rectangle.