All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Shapes
100 squares (Posted on 2006-04-30) Difficulty: 2 of 5
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.

 _____
|_|_|_|
|_|_|_|
|_|_|_|
|_|_|_|

See The Solution Submitted by Jer    
Rating: 4.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution and discussion | Comment 4 of 6 |

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information