How many padded squares can be placed in this square?

Take a square, $135 \times 135$. A bunch of smaller squares, each $1 \times 1$, are placed in some fashion inside the larger square. However,they must be placed with specific criteria: there must be an empty $1 \times 1$ gap on the north and south sides, as well as a $4 \times 1$ gap on their east side, with the $x_1$ of each measurement adjacent to the respective sides of the square. These gaps may overlap. Note that this does mean that the eastern wall has a $4$-unit gap before the first smaller squares, and the northern and southern walls have a $1$-unit gap before the first smaller squares from that direction.

What is the maximum number of small squares that may be placed in the large square given these criteria? If there is a formula that can be used, that would be amazing.

• So, then, squares can share corners? (Your criteria don't rule it out.) Can you put a square on the edge of the big square, and have "implied" padding off the edge? Even the east edge? – Spencer Aug 22 '17 at 2:24
• @Spencer No. All squares must have padding on all sides. I’ll edit to make that clearer. – DonielF Aug 22 '17 at 2:56

1 Answer

Starting from the east wall, leave 4 columns then pack 67 squares in alternating rows in the next column, and 66 squares in the next column west on the empty rows (except top and bottom). Leave 3 columns empty then repeat. From east to west, this gives column totals of $(\color{brown} 0,\color{blue}{0,0,0,67,66},0,0,0,67,66,..)$ etc. This finishes on the $135$th repeat at $67$, without space to add the $66$ in the following column. Clearly there are $k=\frac{135}{5}$ columns with $67$ squares and $k{-}1$ columns with $66$ squares.

• Out of curiosity, why do you assume that this is the most compact you can get? – DonielF Aug 22 '17 at 2:56
• On any given row, you cannot get more than 1/5 of squares occupied, due to the East buffer. You cannot fill all squares on the fifth column; this is the best occupancy for that column ( and the only way to get exactly one-fifth columns filled). The other rows can only manage one less square per row. The layout of these secondary rows can vary, as they have some "slack" at the West boundary. – Joffan Aug 22 '17 at 3:14