This 'puzzle' is from the New York Times website, from its puzzles. I decided it was fun and so I would share it with you.
Question
Here are 10 straight lines and 17 squares.
Here are 9 straight lines and 20 squares.
Find the smallest number of lines needed to make exactly 100 squares.
Once you’ve done this, investigate further.
How many different ways can you make a particular number of squares?
Suppose we have a rectangle made with $h$ horizontal lines and $v$ vertical lines. We can assume without loss of generality that $h\le v$.
The number of squares with side length $s$ is $(h-s)(v-s)$. The total number of squares is therefore
$$f(h,v) = \sum_{s=1}^{h-1} (h-s)(v-s)\\ =\sum_{s=1}^{h-1} (hv - (h+v)s + s^2)\\ =\sum_{s=1}^{h-1} hv - (h+v)\sum_{s=1}^{h-1}s + \sum_{s=1}^{h-1}s^2\\ =h(h-1)v - (h+v)\frac{h(h-1)}{2} + \frac{h(h-1)(2h-1)}{6}\\ =\frac{h(h-1)}{6}( 6v - 3(h+v) + (2h-1) )\\ =\frac{h(h-1)(3v-h-1)}{6}$$
We want to have $100$ squares.
$$ \frac{h(h-1)(3v-h-1)}{6} = 100 \\h(h-1)(3v-h-1) = 600 = 2^3\cdot 3\cdot 5^2$$
So we need $600$ to be divisible by two successive integers $h-1$ and $h$. There are not many possibilities to check.
$h=2$ gives $v=101$
$h=3$ gives a non-integer value for $v$ when we divide by its coefficient $3$
$h=4$ likewise
$h=5$ gives $v=12$
$h=6$ gives $v=9$
The next value of $h$ for which both $h$ and $h-1$ divide $2^3\cdot 3\cdot 5^2$ is $25$, but then $h>v$, and this formula is not valid there.
So the solutions are:
$(h,v)=(2,101)$, or a $1\times100$ rectangle, using $103$ lines
$(h,v)=(5,12)$, or a $4\times11$ rectangle, using $17$ lines
$(h,v)=(6,9)$, or a $5\times8$ rectangle, using $15$ lines
So $15$ lines is the best.
Those are just the solutions with a perfectly rectangular grid. It should be checked that no non-rectangular grid works better.
You could remove one or more unit squares from a corner of a rectangular grid to get an arrangement that has fewer squares, but which uses the same number of lines. Fortunately though, no rectangle with $14$ lines produces more than $100$ squares (the best is $h=v=7$ which gives $91$ squares).
Let's check that there is no alternative solution. The only rectangle with $15$ lines and more squares is $h=7$, $v=8$, the $6\times 7$ rectangle. It has $112$ squares. If you remove one corner unit square, six squares disappear, one of each size. You can then remove the square next to it on the long side to get rid another six squares, leaving exactly $100$ squares. Instead of the adjacent square you could remove one of the corners on the far side.
So this gives three alternative optimal solutions with $15$ lines.
Here are pictures of the alternative solutions:
The general formula for the number of squares in a $n \times (n+k-1)$ grid ($n>0,k\ge 0$) is
$N=\frac {(2n+3k-4)(n-1)n} 6$.
The smallest solution is
$n=6,k=4$, or $15$ lines in a $6\times9$ grid. Indeed, summing the numbers of $1\times 1$-, $2\times 2$- etc. squares gives $5\times 8 + 4\times 7 + 3\times 6 + 2\times 5 + 1\times 4 = 40 + 28 + 18 + 10 + 4 = 100$.
It is relatively easy to show that
overlaying square grids at odd angles, disjoint grids, non-uniform spacing of lines and non-rectangular grids are all inefficiencies, giving fewer squares for a given number of straight lines than a single complete rectangular grid.
Now
for an $m×n$ grid ($m\ge n$) using $m+n+2$ lines, the number of squares formed is $\frac n6(n+1)(3m-n+1)$ (see OEIS A115262). In particular, $s(8,5)=100$ and no $m,n$ with $m+n<8+5=13$ gives $s(m,n)=100$, so the minimum number of lines to make exactly $100$ squares is $15$:
To find the number of different ways to make a particular number $N$ of squares
while sticking to the rectangular grid, simply check whether $N=P_n+kT_n$ for some non-negative $k$, for $n=1,2,3,\dots$ until $P_n>N$, and pool all possibilities. Here $P_n$ is the $n$th square pyramidal number and $T_n$ the $n$th triangular number. There are two other ways to make $100$ squares up to symmetry, the $11×4$ and $100×1$ grids.
