What is the fewest straight lines with which you can make exactly 100 squares?
For example with four vertical and five horizontal lines, evenly spaced, 20 squares are formed: twelve 1x1, six 2x2 and two 3x3.
_____
|_|_|_|
|_|_|_|
|_|_|_|
|_|_|_|
The following table shows the number of squares that are formed when a rectangle of m x n smallest-size squares is formed, where m is the larger if the two are unequal:
n 2 3 4 5 6 7 8 9 10 11 12 13 14
m
2 5
3 8 14
4 11 20 30
5 14 26 40 55
6 17 32 50 70 91
7 20 38 60 85 112 140
8 23 44 70 100 133 168 204
9 26 50 80 115 154 196 240 285
10 29 56 90 130 175 224 276 330 385
11 32 62 100 145 196 252 312 375 440 506
12 35 68 110 160 217 280 348 420 495 572 650
13 38 74 120 175 238 308 384 465 550 638 728 819
14 41 80 130 190 259 336 420 510 605 704 806 910 1015
15 44 86 140 205 280 364 456 555 660 770 884 1001 1120
16 47 92 150 220 301 392 492 600 715 836 962 1092 1225
17 50 98 160 235 322 420 528 645 770 902 1040 1183 1330
18 53 104 170 250 343 448 564 690 825 968 1118 1274 1435
19 56 110 180 265 364 476 600 735 880 1034 1196 1365 1540
20 59 116 190 280 385 504 636 780 935 1100 1274 1456 1645
21 62 122 200 295 406 532 672 825 990 1166 1352 1547 1750
22 65 128 210 310 427 560 708 870 1045 1232 1430 1638 1855
23 68 134 220 325 448 588 744 915 1100 1298 1508 1729 1960
24 71 140 230 340 469 616 780 960 1155 1364 1586 1820 2065
25 74 146 240 355 490 644 816 1005 1210 1430 1664 1911 2170
26 77 152 250 370 511 672 852 1050 1265 1496 1742 2002 2275
27 80 158 260 385 532 700 888 1095 1320 1562 1820 2093 2380
28 83 164 270 400 553 728 924 1140 1375 1628 1898 2184 2485
29 86 170 280 415 574 756 960 1185 1430 1694 1976 2275 2590
30 89 176 290 430 595 784 996 1230 1485 1760 2054 2366 2695
31 92 182 300 445 616 812 1032 1275 1540 1826 2132 2457 2800
32 95 188 310 460 637 840 1068 1320 1595 1892 2210 2548 2905
33 98 194 320 475 658 868 1104 1365 1650 1958 2288 2639 3010
34 101 200 330 490 679 896 1140 1410 1705 2024 2366 2730 3115
35 104 206 340 505 700 924 1176 1455 1760 2090 2444 2821 3220
36 107 212 350 520 721 952 1212 1500 1815 2156 2522 2912 3325
37 110 218 360 535 742 980 1248 1545 1870 2222 2600 3003 3430
38 113 224 370 550 763 1008 1284 1590 1925 2288 2678 3094 3535
39 116 230 380 565 784 1036 1320 1635 1980 2354 2756 3185 3640
40 119 236 390 580 805 1064 1356 1680 2035 2420 2834 3276 3745
The number of lines in any of these is m+1+n+1, or m+n+2. We see that 100 squares can be formed as an 8 x 5 array of small squares, requiring 15 lines.
Could any other way of generating the squares do better? I don't think so. If we used 7 instead of the 8 rows, we'd need 6 instead of 5 columns, and cut out some squares (if that'e even possible to make exactly 100). An 11 x 3 array of small squares requires 16 lines--worse than what we have.
That any such puzzle might require other than a rectangular array of little squares when such an array is available, consider trying to make 104 squares. The chart above shows that an 18 x 3 array, using 23 lines, would produce 104 squares in all. But so would
_______________
|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
which uses only 22 lines.
A search was made for similar patterns for 100 squares, but the results showed only the following:
2 5 8 8 15
2 6 6 9 17
2 7 5 10 19
2 8 5 5 15
3 5 8 8 15
3 6 5 10 18
3 8 4 9 19
3 8 5 5 15
4 5 4 10 17
4 5 6 9 16
4 5 8 8 15
4 6 4 9 17
4 6 5 8 16
4 7 4 8 17
4 8 4 7 17
4 8 5 5 15
4 9 4 6 17
4 10 4 5 17
5 5 5 8 15
5 5 6 8 15
5 5 7 8 15
5 5 8 8 15
5 6 5 7 15
5 7 5 6 15
5 8 5 5 15
where the first number is the number of rows of small squares at the wider size; the second number is the total number of rows; the third number is the narrower width; the fourth number is the wider width. The last number is the number of lines required.
The 2,5,8,8 represents just the rectangle we have found, as the wide and narrow widths are the same 8; likewise the ones where the number of rows matches the number that are wide. There is, however one that is not rectangular: 5,6,5,7, that also requires only 15 lines:
_____________
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|
where 40 squares are size 1, 28 size 2, 18 size 3, 10 size 4 and 4 size 5.
The program for finding these non-rectangular arrays is:
CLS
FOR lat1 = 2 TO 9
FOR lat2 = lat1 TO 10
FOR lon1 = lat1 TO 9
FOR lon2 = lon1 TO 10
t = 0
FOR s = 1 TO lon1
FOR r1 = 0 TO lat2
r2 = r1 + s
FOR c1 = 0 TO lon2
c2 = c1 + s
IF (r2 <= lat1 OR c2 <= lon1) AND (r2 <= lat2 AND c2 <= lon2) THEN
t = t + 1
ELSE
EXIT FOR
END IF
NEXT
NEXT
NEXT
IF t = 104 THEN
lines = lat2 + 1 + lon2 + 1
PRINT lat1; lat2, lon1; lon2, lines
END IF
NEXT
NEXT
NEXT
NEXT
The program for producing the table at the beginning is:
CLS
FOR a = 2 TO 40
IF a < 15 THEN mx = a: ELSE mx = 14
FOR b = 1 TO mx
ct = 0
IF a < b THEN l = a: ELSE l = b
FOR s = 1 TO l
FOR h = 0 TO a - s
FOR v = 0 TO b - s
ct = ct + 1
NEXT
NEXT h
NEXT s
LOCATE a, b * 5
PRINT USING "####"; ct;
NEXT
NEXT
|
|
Posted by Charlie
on 2006-04-30 20:10:08 |
solution and discussion
