Filling a rectangle with congruent squares in two columns

Question

I have a rectangle. This rectangle is divided into two columns; the widths of these columns are not necessarily equal, and are not known. I want to fill the rectangle with squares. The number of squares in each column is known. Each square should be the same size (congruent). I am trying to find the largest size that the squares can be so that they fill as much of the rectangle as possible, with all squares entirely contained inside the rectangle, arranged in a grid, and not overlapping. In this, I should find the best widths of each column for this number of squares.

This answer has a wonderful explanation of how to do this in one column. My question is how to do this in two.

---

An example

• Rectangle is 9 by 14
• Number of squares in column 1: 4
• Number of squares in column 2: 7

Best arrangement of squares (where the dashed line is the divider between columns, and dotted lines represent boundaries between squares):

---

To summarize: Given the number of squares in each column and the size of the rectangle, how can I find the square size and the width of each column that minimize the unfilled area?

Thanks in advance!

Answer 1

Given data:

• $H$ - height or rectangle
• $W$ - width of rectangle
• $N$ - number of squares in forst column
• $M$ - number of squares in second column (without loosing generality we can say, that $M>N$)

Notice some facts:

• If we fill first column in $k$ subcolumns, then we obtain $\left\lceil \frac{N}{k}\right\rceil$ subrows
• If we fill first column in $l$ subrows, then we should fill the second in the same amount of subrows, and that means it will be filled with $\left\lceil \frac{M}{l}\right\rceil$ subcolumns
• The above facts say, that filling first column with $k$ subcolumns will cause filling the second column with $\left\lceil \frac{M}{\left\lceil \frac{N}{k}\right\rceil}\right\rceil$ subcolumns and both columns are filled with $\left\lceil \frac{N}{k}\right\rceil$ subrows
• If we fill first column with $k$ subcolumns, then height of the square is: $$a(k) = \min\left(\frac{H}{\left\lceil \frac{N}{k}\right\rceil}, \frac{W}{k+\left\lceil \frac{M}{\left\lceil \frac{N}{k}\right\rceil}\right\rceil}\right)$$

The maximal height of the square is then $$A=\max\limits_{k\in\{1,2,...,N\}} a(k)$$