Lines

[cinelli]

.--- --- ---        --- --- 
|   |   |   |      |   |   |   
 --- --- ---        --- --- 
|   |   |   |      |   |   |   
 --- --- ---        --- --- 
|   |   |   |      |   |   |   
 --- --- ---        --- --- 
|   |   |   |      |   |   |   
 --- --- ---        --- --- 
  Figure 1         |   |   |   
                    --- --- 
                   |   |   |   
                    --- --- 
                   Figure 2

In the first diagram nine lines have been drawn, equally spaced up and down and left to right, to make 20 squares (12 of side 1, 6 of side 2, and 2 of side 3), whereas in the second diagram we have more lines, ten, but with fewer squares, 17. This puzzle is to make exactly 100 squares using the fewest lines.

Cinelli

[SteelCamel]

Spoiler
8 by 5 gives 40 single squares, 28 2x2 squares, 18 3x3 squares, 10 4x4 squares, and 4 5x5 squares for a total of 100 squares. This uses 15 lines. It's also possible to get exactly 100 with 4 by 11, but this uses 17 lines. And of course 100 by 1, using 103 lines. There are no other solutions so 8x5 is the fewest lines.

Unfortunately I haven't managed to come up with a very elegant solution.
It's easy enough to work out how many squares are in a grid - call the smaller dimension x and the longer y, it's (x*y)+(x-1*y-1)+... for all values from x to 1. And since the possible grids are fairly limited (7x7 is too big, so the smallest dimension is no more than 6) it's easy enough to enumerate all the possible counts in a spreadsheet. Though I'm sure there should be some simpler way to do it.

[UncleEbenezer]

Steelcamel has given a solution assuming all lines are the same length as all others in their direction - i.e. a perfect rectangular grid. We can verify that 15 lines is the minimum by noting that a square grid will always maximise the ratio of squares and lines, and that no square grid smaller than 7*7 gives 100 squares.

However, if we drop Steelcamel's assumption, there's another solution. Or set of equivalent solutions, if you prefer. A 6*7 grid also has 15 lines and gives 112 squares, but if we shorten three of the lines to omit two small squares from a corner, this removes two squares of each size - for a total of 12 squares - from that count. 100 squares again.

The truncated corner looks like

.   -------
    | | |
-----------
| | | | |

[cinelli]

Reply to solution.

Yes, SteelCamel has it. This was the solution I had in mind, not with any corner of the rectangle nibbled away. And my method was the same. There aren't too many cases to check, but an interesting little puzzle, I think.

Cinelli