Number of all squares placed side by side in a rectangle.

Question

I've been struggling lately to find out a way to calculate the number of squares in a given rectangle.

The thing is that I don't want to calculate the number of permutations of a NxN sized square in a rectangle but try to find out how many squares placed side by side of size NxN can fit into the rectangle.

For example let's assume there's given a 3x2 rectangle. That means that there can fit 6 1x1 squares and only one 2x2 square(you cannot place 2 2x2 squares at the same time without having them overlap) so the total is 7 squares.

Thanks in advance.

Answer 1

Suppose you have a rectangle $w$ units wide and $h$ units high, and you place $2\times2$ squares in this rectangle. Wherever there is an edge of any of these squares parallel to the bottom edge of the rectangle, extend that edge into a line all the way across the rectangle. In this way you will divide the entire rectangle into horizontal strips of which parts are covered by parts of the $2\times2$ squares and parts are not. In the figure below, $2\times2$ squares have been placed in a $9\times7$ rectangle. The red lines cut the rectangle into strips of $9$ units from left to right and various distances from bottom to top.

In this example the squares appear to be placed somewhat haphazardly, but no matter how you place the squares, you cannot make more than $4$ squares overlap any of the horizontal strips. In general, if the width of the rectangle is $w,$ you can make at most $\lfloor w/2 \rfloor$ of the $2\times2$ squares overlap each strip.

This means that each horizontal strip contains at least $w_2\Delta h$ area that is not covered by the $2\times2$ squares, where $w_2 = (w - 2\lfloor w/2 \rfloor)$ and $\Delta h$ is the height of each strip. (Some of the strips have an even larger area uncovered.) If we add up the uncovered area over all the strips, we find that an area measuring at least $w_2 h$ is uncovered.

Similarly, if we cut the rectangle into vertical strips by extending every vertical edge of every square, we find that each strip has at least $h_2 \Delta w$ uncovered area, where $h_2 = (h - 2\lfloor h/2 \rfloor)$ and $\Delta w$ is the width of the strip. Adding this up, we find that an area of at least $h_2 w$ is uncovered.

These two uncovered regions overlap, but only to a limited extent, namely a total area of $(2\lfloor w/2 \rfloor)(2\lfloor h/2 \rfloor) = (w - w_2)(h - h_2).$ The total uncovered area comes out to $$ w_2 h + h_2 w - (w - w_2)(h - h_2) = wh - w_2 h_2. $$

This is the same as you get if you simply arrange the $2\times2$ squares in an array $\lfloor w/2 \rfloor$ squares across and $\lfloor h/2 \rfloor$ squares high in the lower left corner of the rectangle. That is to say, we have just shown (in a rigorous, though long-winded way) that the best arrangement of the squares is just to stack them in continuous rows, leaving a gap (if necessary) along two edges of the rectangle.

The total number of squares in the array fitted in this way is $\lfloor w/2 \rfloor \times \lfloor h/2 \rfloor.$

If we generalize this to $N\times N$ squares in a $w\times h$ rectangle, the maximum number of squares of that size is $\lfloor w/N \rfloor \times \lfloor h/N \rfloor.$

---

Now that we know how to count the number of squares of size $N\times N,$ we can write the algorithm to compute the total number of squares as requested in the question. The answer is $$ \sum_{N=1}^\infty \left(\left\lfloor\frac WN\right\rfloor \times \left\lfloor\frac HN\right\rfloor\right), $$ which counts all possible $1\times 1$ squares, then all possible $2\times 2$ squares, then $3\times 3,$ and so forth until we come to a square that is so large that not even one such square can fit in the rectangle. For that $N$ and any larger $N$ the product $\lfloor w/N \rfloor \times \lfloor h/N \rfloor$ is zero, so we only need to add a finite number of terms.

Answer 2

For a rectangle of size $M \times N$, maximum number $\mathcal{N}(n;M \times N)$ of $n \times n$ sized squares placed adjacent to each other is can be arrived at as : $$\mathcal{N}(n;M \times N)=\mathcal{C}(M,n)\mathcal{C}(N,n),$$ where $\mathcal{C}(M,n)=\big[\frac{M}{n}\big]$ and $[]$ is the lower ceiling function. Then total number of squares that can be placed is : $$\sum_{n=1}^{\min\{M,N\}}\mathcal{N}(n;M \times N)=\sum_{n=1}^{\min\{M,N\}}\mathcal{C}(M,n)\mathcal{C}(N,n)=\sum_{n=1}^{\min\{M,N\}}\Bigg[\frac{M}{n}\Bigg]\Bigg[\frac{N}{n}\Bigg].$$

Answer 3

$\require{begingroup} \begingroup \newcommand{idiv}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor} \newcommand{R}{\mathcal R} \newcommand{L}{\mathcal L} \newcommand{S}{\mathcal S} $This answer is based on an answer to a related question, but generalized to account for uniform squares of any size within a rectangle of any size. The sides of the rectangle do not even need to be commensurate with the sides of the squares. It is assumed, however, that all squares placed in the rectangle are placed with their sides parallel to the sides of the rectangle. (It seems intuitively obvious that rotating the squares will not enable more squares to fit in the rectangle, but proving it is another matter.)

Given a rectangle $\R$ of width $W$ and height $H,$ where $W$ and $H$ may be any real numbers, we first determine how many squares of side $N$ can fit in rectangle $\R$ without overlapping. That is, the sides of squares may touch other squares or the edges of the rectangle, but the interior of any square cannot intersect another square or the boundary of the rectangle.

We can show that the maximum number of squares that can be arranged in rectangle $\R$ in this way is $\idiv WN \times \idiv HN.$ The following proof does this by constructing a rectangular lattice $\L$ of $\idiv WN \times \idiv HN$ points such that in any such arrangement of squares inside $\R,$ each square must contain at least one point of $\L.$

Proof. Choose a Cartesian coordinate system such that the vertices of rectangle $\R$ are at coordinates $(0,0),$ $(0,W),$ $(H,W),$ and $(0,H).$ Let \begin{align} w &= \frac{W}{\idiv WN + 1}, \\[0.7ex] h &= \frac{H}{\idiv HN + 1}, \end{align} and let $\L$ be the set of points $(jw, kh)$ where $j$ and $k$ are integers, $1 \leq j \leq \idiv WN,$ and $1 \leq k \leq \idiv HN.$ In other words, we can tile rectangle $\R$ completely with rectangles of width $w$ and height $h,$ and let the set $\L$ consist of all vertices of these rectangles that are in the interior of rectangle $\R.$ The points of $\L$ then form a rectangular lattice with $\idiv WN$ points in each row and $\idiv HN$ points in each column, a total of $\idiv WN \times \idiv HN$ points altogether.

Since $\idiv WN + 1 > \frac WN,$ it follows that $w < N,$ and similarly $h < N.$ Therefore if we place a square $\S$ of side $N$ anywhere within rectangle $\R$ with sides parallel to the sides of $\R,$ at least one of the lines through the rows of points in $\L$ will pass through the interior of $\S,$ and at least one of the lines through the columns of points in $\L$ will pass through the interior of $\S;$ therefore $\S$ will contain the point of $\L$ at the intersection of those lines. That is, the interior of $\S$ must contain at least one point of the set $\L.$

Suppose now we have placed some number of squares of side $N$ inside rectangle $\R$ so that no two squares overlap (their boundaries may touch but their interiors must be disjoint). Then no two of these squares can both contain the same point of the set $\L.$ By the pigeonhole principle, we can place at most $\lvert\L\rvert = \idiv WN \times \idiv HN$ squares in this way. On the other hand, an array of squares with $\idiv HN$ rows and $\idiv WN$ columns fits inside rectangle $\R$ (using the "greedy algorithm"), so it is possible to achieve the upper bound of $\idiv WN \times \idiv HN$ squares. This completes the proof. $\square$

In the question, however, we are allowed to arrange squares of side $1$ inside the rectangle, then ignore them and arrange squares of side $2$ inside the rectangle, then ignore those squares and arrange squares of side $3,$ and so forth, as long as at least one square can fit inside the rectangle; and then the answer is the total number of squares of all sizes that were arranged in this way. The final answer therefore is $$ \sum_{N=1}^\infty \left(\idiv WN \times \idiv HN\right). $$ Note that this is actually a finite sum, since for $N > W$ or $N > H$ all terms will be zero. The last non-zero term of the sum is the term for $N = \min\{\lfloor W\rfloor, \lfloor H\rfloor\}. \endgroup$

Answer 4

If the rectangle has size $ m\times n $ then you can fit in $ \lfloor m/N \rfloor × \lfloor n / N \rfloor $ squares of size $ N\times N $.

The idea: Fit as many squares as possible into the rectangle. Now look at the strip consisting of the top N rows. If a square meets this strip we can push it upwards so that it is fully contained in the strip. Therefore, by maximality, the strip contains $ \lfloor n / N \rfloor $ squares. Now remove the top strip altogether and proceed via induction.