If you were told to draw a rectangle along the lines of a sheet of graph paper such that its area is 40 squares, you could choose rectangles measuring 8x5, 10x4, 20x2 or 40x1.
For two of these, 8x5 or 10x4, you would find that you could draw a diagonal across the rectangle that would pass through exactly 12 squares.
What is the smallest number of squares that could be the area of three different rectangles whose diagonals pass through the same number of squares? How many squares does this diagonal pass through?
The minimum number of squares is 1. Then each time a column or row boundary is encountered the number goes up by 1. That would seem to indicate the number of squares traversed would be 1+(r-1)+(c-1) = r+c-1 would be the number of squares, where r is the number of rows and c the number of columns.
However, whenever a row and a column change at the same time, the count of squares goes up by only 1 altogether. As a result the actual count of squares traversed is r+c-gcd(r,c).
The following program tests all numbers of rows and columns for areas up to 10,000 (h for height and w for width):
DECLARE FUNCTION gcd# (x#, y#)
DEFDBL A-Z
FOR area = 2 TO 10000
REDIM sq(300), sqCt(300)
mx = INT(SQR(area) + .5)
IF mx * mx > area THEN mx = mx - 1
ct = 0
FOR w = 1 TO mx
h = area / w
IF h = INT(h) THEN
squares = w + h - gcd(w, h)
flag = 0
FOR i = 1 TO ct
IF sq(i) = squares THEN
sqCt(i) = sqCt(i) + 1
flag = 1
END IF
NEXT
IF flag = 0 THEN ct = ct + 1: sq(ct) = squares: sqCt(ct) = 1
END IF
NEXT w
FOR i = 1 TO ct
IF sqCt(i) >= 3 THEN
PRINT area, sq(i), sqCt(i)
IF foundIt = 0 THEN
firstArea = area: firstSq = sq(i)
foundIt = 1
END IF
END IF
NEXT
NEXT area
area = firstArea
mx = INT(SQR(area) + .5)
IF mx * mx > area THEN mx = mx - 1
FOR w = 1 TO mx
h = area / w
IF h = INT(h) THEN
squares = w + h - gcd(w, h)
IF squares = firstSq THEN
PRINT area, squares, w, h
END IF
END IF
NEXT w
FUNCTION gcd (x, y)
d = x: r = y
IF r > d THEN SWAP d, r
DO
q = INT(d / r)
rm = d - q * r
d = r
r = rm
LOOP UNTIL r = 0
gcd = d
END FUNCTION
It outputs
144 24 3
336 36 3
360 36 3
576 48 3
720 60 3
756 54 3
900 60 3
1296 72 3
1344 72 3
1440 72 3
1764 84 3
1980 90 3
2100 90 3
2304 96 3
2400 120 3
2880 120 3
3024 108 4
3240 108 3
3600 120 5
5184 144 4
5376 144 3
5760 144 3
6120 156 3
6300 210 3
6480 180 3
6720 168 3
6804 162 3
7056 168 4
7920 180 3
8100 180 4
8400 180 4
9000 180 3
9216 192 3
9504 192 3
9600 240 3
9828 198 3
144 24 6 24
144 24 8 18
144 24 9 16
where 144 is the first area to have at least 3 ways of getting a number of squares (24 as it happens). It goes on through 3024 as the first to have 4 and 3600 the first to have 5.
The section at the bottom breaks down the three equal ways of making that 144: 6x24, 8x18 and 9x16.
|
|
Posted by Charlie
on 2005-03-16 20:35:29 |
solution -- computer aided
