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

 Equal Diagonals (Posted on 2005-03-16)
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?

 No Solution Yet Submitted by Sam Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution -- computer aided | Comment 1 of 8

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

 Search: Search body:
Forums (0)