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

 A quadrilateral query (Posted on 2005-08-29)
Consider quadrilateral ABCD whose diagonals are perpendicular and meet at point E.

Minimize the perimeter of ABCD where AB, BC, CD, DA, EA, EB, EC, ED are all different integers.
(Or prove no such quadrilateral exists.)

 See The Solution Submitted by Jer Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Computer verification of minimum | Comment 4 of 5 |
(In reply to Second half of solution by Tristan)

A program checking all cases of triangles with their two legs adding to no more than 1000 and hypotenuses no more than 500, finds no perimeter less than 176.

Some other sets of triangles found are shown below with the lengths of the segments (there was no check to prevent duplicate measures, except that both legs of a triangle could not be equal), the ratio of the legs in each triangle and the total perimeter of the quadrilateral.  All those found seem to have at least a 3/4 or 5/12 ratio among them.

15  20  48  36
25  52  60  39
3 / 4 ; 5 / 12 ; 4 / 3 ; 12 / 5 ; 176

21  28  96  72
35  100  120  75
3 / 4 ; 7 / 24 ; 4 / 3 ; 24 / 7 ; 330

15  36  48  20
39  60  52  25
5 / 12 ; 3 / 4 ; 12 / 5 ; 4 / 3 ; 176

24  32  60  45
40  68  75  51
3 / 4 ; 8 / 15 ; 4 / 3 ; 15 / 8 ; 234

27  36  160  120
45  164  200  123
3 / 4 ; 9 / 40 ; 4 / 3 ; 40 / 9 ; 532

20  48  36  15
52  60  39  25
5 / 12 ; 4 / 3 ; 12 / 5 ; 3 / 4 ; 176

24  45  60  32
51  75  68  40
8 / 15 ; 3 / 4 ; 15 / 8 ; 4 / 3 ; 234

30  40  96  72
50  104  120  78
3 / 4 ; 5 / 12 ; 4 / 3 ; 12 / 5 ; 352

33  44  240  180
55  244  300  183
3 / 4 ; 11 / 60 ; 4 / 3 ; 60 / 11 ; 782

36  48  20  15
60  52  25  39
3 / 4 ; 12 / 5 ; 4 / 3 ; 5 / 12 ; 176

36  48  140  105
60  148  175  111
3 / 4 ; 12 / 35 ; 4 / 3 ; 35 / 12 ; 494

25  60  91  312
65  109  325  313
5 / 12 ; 60 / 91 ; 7 / 24 ; 312 / 25 ; 812

32  60  45  24
68  75  51  40
8 / 15 ; 4 / 3 ; 15 / 8 ; 3 / 4 ; 234

21  72  96  28
75  120  100  35
7 / 24 ; 3 / 4 ; 24 / 7 ; 4 / 3 ; 330

42  56  192  144
70  200  240  150
3 / 4 ; 7 / 24 ; 4 / 3 ; 24 / 7 ; 660

30  72  96  40
78  120  104  50
5 / 12 ; 3 / 4 ; 12 / 5 ; 4 / 3 ; 352

45  60  32  24
75  68  40  51
3 / 4 ; 15 / 8 ; 4 / 3 ; 8 / 15 ; 234

45  60  144  108
75  156  180  117
3 / 4 ; 5 / 12 ; 4 / 3 ; 12 / 5 ; 528

48  64  120  90
80  136  150  102
3 / 4 ; 8 / 15 ; 4 / 3 ; 15 / 8 ; 468

48  64  252  189
80  260  315  195
3 / 4 ; 16 / 63 ; 4 / 3 ; 63 / 16 ; 850

40  75  180  96
85  195  204  104
8 / 15 ; 5 / 12 ; 15 / 8 ; 12 / 5 ; 588

35  84  288  120
91  300  312  125
5 / 12 ; 7 / 24 ; 12 / 5 ; 24 / 7 ; 828

60  63  84  80
87  105  116  100
20 / 21 ; 3 / 4 ; 21 / 20 ; 4 / 3 ; 408

28  96  72  21
100  120  75  35
7 / 24 ; 4 / 3 ; 24 / 7 ; 3 / 4 ; 330

40  96  72  30
104  120  78  50
5 / 12 ; 4 / 3 ; 12 / 5 ; 3 / 4 ; 352

40  96  180  75
104  204  195  85
5 / 12 ; 8 / 15 ; 12 / 5 ; 15 / 8 ; 588

65  72  320  156
97  328  356  169
65 / 72 ; 9 / 40 ; 80 / 39 ; 12 / 5 ; 950

48  90  120  64
102  150  136  80
8 / 15 ; 3 / 4 ; 15 / 8 ; 4 / 3 ; 468

60  80  84  63
100  116  105  87
3 / 4 ; 20 / 21 ; 4 / 3 ; 21 / 20 ; 408

60  80  192  144
100  208  240  156
3 / 4 ; 5 / 12 ; 4 / 3 ; 12 / 5 ; 704

36  105  140  48
111  175  148  60
12 / 35 ; 3 / 4 ; 35 / 12 ; 4 / 3 ; 494

27  120  160  36
123  200  164  45
9 / 40 ; 3 / 4 ; 40 / 9 ; 4 / 3 ; 532

63  84  80  60
105  116  100  87
3 / 4 ; 21 / 20 ; 4 / 3 ; 20 / 21 ; 408

63  84  288  216
105  300  360  225
3 / 4 ; 7 / 24 ; 4 / 3 ; 24 / 7 ; 990

60  91  312  25
109  325  313  65
60 / 91 ; 7 / 24 ; 312 / 25 ; 5 / 12 ; 812

45  108  144  60
117  180  156  75
5 / 12 ; 3 / 4 ; 12 / 5 ; 4 / 3 ; 528

66  88  105  360
110  137  375  366
3 / 4 ; 88 / 105 ; 7 / 24 ; 60 / 11 ; 988

35  120  288  84
125  312  300  91
7 / 24 ; 5 / 12 ; 24 / 7 ; 12 / 5 ; 828

80  84  63  60
116  105  87  100
20 / 21 ; 4 / 3 ; 21 / 20 ; 3 / 4 ; 408

72  96  28  21
120  100  35  75
3 / 4 ; 24 / 7 ; 4 / 3 ; 7 / 24 ; 330

72  96  40  30
120  104  50  78
3 / 4 ; 12 / 5 ; 4 / 3 ; 5 / 12 ; 352

72  96  180  135
120  204  225  153
3 / 4 ; 8 / 15 ; 4 / 3 ; 15 / 8 ; 702

72  96  280  210
120  296  350  222
3 / 4 ; 12 / 35 ; 4 / 3 ; 35 / 12 ; 988

75  100  240  180
125  260  300  195
3 / 4 ; 5 / 12 ; 4 / 3 ; 12 / 5 ; 880

64  120  90  48
136  150  102  80
8 / 15 ; 4 / 3 ; 15 / 8 ; 3 / 4 ; 468

42  144  192  56
150  240  200  70
7 / 24 ; 3 / 4 ; 24 / 7 ; 4 / 3 ; 660

48  140  105  36
148  175  111  60
12 / 35 ; 4 / 3 ; 35 / 12 ; 3 / 4 ; 494

88  105  360  66
137  375  366  110
88 / 105 ; 7 / 24 ; 60 / 11 ; 3 / 4 ; 988

36  160  120  27
164  200  123  45
9 / 40 ; 4 / 3 ; 40 / 9 ; 3 / 4 ; 532

84  112  180  135
140  212  225  159
3 / 4 ; 28 / 45 ; 4 / 3 ; 45 / 28 ; 736

60  144  108  45
156  180  117  75
5 / 12 ; 4 / 3 ; 12 / 5 ; 3 / 4 ; 528

60  144  192  80
156  240  208  100
5 / 12 ; 3 / 4 ; 12 / 5 ; 4 / 3 ; 704

100  105  252  240
145  273  348  260
20 / 21 ; 5 / 12 ; 21 / 20 ; 12 / 5 ; 1026

72  135  180  96
153  225  204  120
8 / 15 ; 3 / 4 ; 15 / 8 ; 4 / 3 ; 702

90  120  64  48
150  136  80  102
3 / 4 ; 15 / 8 ; 4 / 3 ; 8 / 15 ; 468

90  120  288  216
150  312  360  234
3 / 4 ; 5 / 12 ; 4 / 3 ; 12 / 5 ; 1056

33  180  240  44
183  300  244  55
11 / 60 ; 3 / 4 ; 60 / 11 ; 4 / 3 ; 782

84  135  180  112
159  225  212  140
28 / 45 ; 3 / 4 ; 45 / 28 ; 4 / 3 ; 736

65  156  320  72
169  356  328  97
5 / 12 ; 39 / 80 ; 40 / 9 ; 72 / 65 ; 950

96  128  240  180
160  272  300  204
3 / 4 ; 8 / 15 ; 4 / 3 ; 15 / 8 ; 936

99  132  224  168
165  260  280  195
3 / 4 ; 33 / 56 ; 4 / 3 ; 56 / 33 ; 900

48  189  252  64
195  315  260  80
16 / 63 ; 3 / 4 ; 63 / 16 ; 4 / 3 ; 850

105  140  48  36
175  148  60  111
3 / 4 ; 35 / 12 ; 4 / 3 ; 12 / 35 ; 494

120  126  168  160
174  210  232  200
20 / 21 ; 3 / 4 ; 21 / 20 ; 4 / 3 ; 816

56  192  144  42
200  240  150  70
7 / 24 ; 4 / 3 ; 24 / 7 ; 3 / 4 ; 660

108  144  60  45
180  156  75  117
3 / 4 ; 12 / 5 ; 4 / 3 ; 5 / 12 ; 528

108  144  308  231
180  340  385  255
3 / 4 ; 36 / 77 ; 4 / 3 ; 77 / 36 ; 1160

75  180  96  40
195  204  104  85
5 / 12 ; 15 / 8 ; 12 / 5 ; 8 / 15 ; 588

75  180  240  100
195  300  260  125
5 / 12 ; 3 / 4 ; 12 / 5 ; 4 / 3 ; 880

99  168  224  132
195  280  260  165
33 / 56 ; 3 / 4 ; 56 / 33 ; 4 / 3 ; 900

80  192  144  60
208  240  156  100
5 / 12 ; 4 / 3 ; 12 / 5 ; 3 / 4 ; 704

96  180  75  40
204  195  85  104
8 / 15 ; 12 / 5 ; 15 / 8 ; 5 / 12 ; 588

96  180  135  72
204  225  153  120
8 / 15 ; 4 / 3 ; 15 / 8 ; 3 / 4 ; 702

96  180  240  128
204  300  272  160
8 / 15 ; 3 / 4 ; 15 / 8 ; 4 / 3 ; 936

63  216  288  84
225  360  300  105
7 / 24 ; 3 / 4 ; 24 / 7 ; 4 / 3 ; 990

120  160  36  27
200  164  45  123
3 / 4 ; 40 / 9 ; 4 / 3 ; 9 / 40 ; 532

120  160  168  126
200  232  210  174
3 / 4 ; 20 / 21 ; 4 / 3 ; 21 / 20 ; 816

120  160  300  225
200  340  375  255
3 / 4 ; 8 / 15 ; 4 / 3 ; 15 / 8 ; 1170

72  210  280  96
222  350  296  120
12 / 35 ; 3 / 4 ; 35 / 12 ; 4 / 3 ; 988

44  240  180  33
244  300  183  55
11 / 60 ; 4 / 3 ; 60 / 11 ; 3 / 4 ; 782

112  180  135  84
212  225  159  140
28 / 45 ; 4 / 3 ; 45 / 28 ; 3 / 4 ; 736

126  168  160  120
210  232  200  174
3 / 4 ; 21 / 20 ; 4 / 3 ; 20 / 21 ; 816

90  216  288  120
234  360  312  150
5 / 12 ; 3 / 4 ; 12 / 5 ; 4 / 3 ; 1056

144  165  220  192
219  275  292  240
48 / 55 ; 3 / 4 ; 55 / 48 ; 4 / 3 ; 1026

135  180  96  72
225  204  120  153
3 / 4 ; 15 / 8 ; 4 / 3 ; 8 / 15 ; 702

135  180  112  84
225  212  140  159
3 / 4 ; 45 / 28 ; 4 / 3 ; 28 / 45 ; 736

64  252  189  48
260  315  195  80
16 / 63 ; 4 / 3 ; 63 / 16 ; 3 / 4 ; 850

160  168  126  120
232  210  174  200
20 / 21 ; 4 / 3 ; 21 / 20 ; 3 / 4 ; 816

144  192  56  42
240  200  70  150
3 / 4 ; 24 / 7 ; 4 / 3 ; 7 / 24 ; 660

144  192  80  60
240  208  100  156
3 / 4 ; 12 / 5 ; 4 / 3 ; 5 / 12 ; 704

144  192  220  165
240  292  275  219
3 / 4 ; 48 / 55 ; 4 / 3 ; 55 / 48 ; 1026

25  312  91  60
313  325  109  65
25 / 312 ; 24 / 7 ; 91 / 60 ; 12 / 5 ; 812

108  231  308  144
255  385  340  180
36 / 77 ; 3 / 4 ; 77 / 36 ; 4 / 3 ; 1160

100  240  180  75
260  300  195  125
5 / 12 ; 4 / 3 ; 12 / 5 ; 3 / 4 ; 880

100  240  252  105
260  348  273  145
5 / 12 ; 20 / 21 ; 12 / 5 ; 21 / 20 ; 1026

120  225  300  160
255  375  340  200
8 / 15 ; 3 / 4 ; 15 / 8 ; 4 / 3 ; 1170

132  224  168  99
260  280  195  165
33 / 56 ; 4 / 3 ; 56 / 33 ; 3 / 4 ; 900

105  252  240  100
273  348  260  145
5 / 12 ; 21 / 20 ; 12 / 5 ; 20 / 21 ; 1026

128  240  180  96
272  300  204  160
8 / 15 ; 4 / 3 ; 15 / 8 ; 3 / 4 ; 936

180  189  252  240
261  315  348  300
20 / 21 ; 3 / 4 ; 21 / 20 ; 4 / 3 ; 1224

84  288  120  35
300  312  125  91
7 / 24 ; 12 / 5 ; 24 / 7 ; 5 / 12 ; 828

84  288  216  63
300  360  225  105
7 / 24 ; 4 / 3 ; 24 / 7 ; 3 / 4 ; 990

96  280  210  72
296  350  222  120
12 / 35 ; 4 / 3 ; 35 / 12 ; 3 / 4 ; 988

165  220  192  144
275  292  240  219
3 / 4 ; 55 / 48 ; 4 / 3 ; 48 / 55 ; 1026

72  320  156  65
328  356  169  97
9 / 40 ; 80 / 39 ; 12 / 5 ; 65 / 72 ; 950

168  224  132  99
280  260  165  195
3 / 4 ; 56 / 33 ; 4 / 3 ; 33 / 56 ; 900

91  312  25  60
325  313  65  109
7 / 24 ; 312 / 25 ; 5 / 12 ; 60 / 91 ; 812

120  288  84  35
312  300  91  125
5 / 12 ; 24 / 7 ; 12 / 5 ; 7 / 24 ; 828

120  288  216  90
312  360  234  150
5 / 12 ; 4 / 3 ; 12 / 5 ; 3 / 4 ; 1056

195  216  288  260
291  360  388  325
65 / 72 ; 3 / 4 ; 72 / 65 ; 4 / 3 ; 1364

192  220  165  144
292  275  219  240
48 / 55 ; 4 / 3 ; 55 / 48 ; 3 / 4 ; 1026

180  240  44  33
300  244  55  183
3 / 4 ; 60 / 11 ; 4 / 3 ; 11 / 60 ; 782

180  240  100  75
300  260  125  195
3 / 4 ; 12 / 5 ; 4 / 3 ; 5 / 12 ; 880

180  240  128  96
300  272  160  204
3 / 4 ; 15 / 8 ; 4 / 3 ; 8 / 15 ; 936

180  240  252  189
300  348  315  261
3 / 4 ; 20 / 21 ; 4 / 3 ; 21 / 20 ; 1224

66  360  105  88
366  375  137  110
11 / 60 ; 24 / 7 ; 105 / 88 ; 4 / 3 ; 988

189  252  64  48
315  260  80  195
3 / 4 ; 63 / 16 ; 4 / 3 ; 16 / 63 ; 850

189  252  240  180
315  348  300  261
3 / 4 ; 21 / 20 ; 4 / 3 ; 20 / 21 ; 1224

144  308  231  108
340  385  255  180
36 / 77 ; 4 / 3 ; 77 / 36 ; 3 / 4 ; 1160

195  260  288  216
325  388  360  291
3 / 4 ; 65 / 72 ; 4 / 3 ; 72 / 65 ; 1364

160  300  225  120
340  375  255  200
8 / 15 ; 4 / 3 ; 15 / 8 ; 3 / 4 ; 1170

105  360  66  88
375  366  110  137
7 / 24 ; 60 / 11 ; 3 / 4 ; 88 / 105 ; 988

156  320  72  65
356  328  97  169
39 / 80 ; 40 / 9 ; 72 / 65 ; 5 / 12 ; 950

210  280  96  72
350  296  120  222
3 / 4 ; 35 / 12 ; 4 / 3 ; 12 / 35 ; 988

240  252  105  100
348  273  145  260
20 / 21 ; 12 / 5 ; 21 / 20 ; 5 / 12 ; 1026

240  252  189  180
348  315  261  300
20 / 21 ; 4 / 3 ; 21 / 20 ; 3 / 4 ; 1224

216  288  84  63
360  300  105  225
3 / 4 ; 24 / 7 ; 4 / 3 ; 7 / 24 ; 990

216  288  120  90
360  312  150  234
3 / 4 ; 12 / 5 ; 4 / 3 ; 5 / 12 ; 1056

216  288  260  195
360  388  325  291
3 / 4 ; 72 / 65 ; 4 / 3 ; 65 / 72 ; 1364

225  300  160  120
375  340  200  255
3 / 4 ; 15 / 8 ; 4 / 3 ; 8 / 15 ; 1170

231  308  144  108
385  340  180  255
3 / 4 ; 77 / 36 ; 4 / 3 ; 36 / 77 ; 1160

260  288  216  195
388  360  291  325
65 / 72 ; 4 / 3 ; 72 / 65 ; 3 / 4 ; 1364

The program (note some lines have been commented out by an apostrophe, notably those asking for the least perimeter so far):

DECLARE FUNCTION gcd! (a!, b!)
DIM n%(650, 2)
FOR t = 1 TO 1000
FOR n1 = 1 TO t / 2
n2 = t - n1
hsq = n1 * n1 + n2 * n2
h = INT(SQR(hsq) + .5)
IF h * h = hsq AND h < 400 THEN
PRINT n1, n2, h
ct = ct + 1
'      IF ct MOD 45 = 0 THEN
'        DO: LOOP UNTIL INKEY\$ > ""
'      END IF
n%(ct, 1) = n1
n%(ct, 2) = n2
n%(ct, 0) = h
END IF
NEXT n1
NEXT t
PRINT ct

best = 999

OPEN "quadque2.txt" FOR OUTPUT AS #2
FOR i = 1 TO ct
n11 = n%(i, 1)
n12 = n%(i, 2)
t1 = n%(i, 0)
FOR j = 1 TO ct
IF j <> i THEN
IF (n%(j, 1) = n12 OR n%(j, 2) = n12) AND n%(j, 2) <> n%(j, 1) THEN
IF n%(j, 1) = n12 THEN
n21 = n12
n22 = n%(j, 2)
ELSE
n21 = n12
n22 = n%(j, 1)
END IF
t2 = n%(j, 0)

FOR k = 1 TO ct
IF j <> k AND i <> k THEN
IF (n%(k, 1) = n22 OR n%(k, 2) = n22) AND n%(k, 2) <> n%(k, 1) THEN
IF n%(k, 1) = n22 THEN
n31 = n22
n32 = n%(k, 2)
ELSE
n31 = n22
n32 = n%(k, 1)
END IF
t3 = n%(k, 0)

FOR l = 1 TO ct
IF j <> l AND i <> l AND k <> l THEN
IF (n%(l, 1) = n32 OR n%(l, 2) = n32) AND n%(l, 2) <> n%(l, 1) THEN
IF (n%(l, 1) = n11 OR n%(l, 2) = n11) AND n%(l, 2) <> n%(l, 1) AND n11 <> n32 THEN
IF n%(l, 1) = n32 THEN
n41 = n32
n42 = n%(l, 2)
ELSE
n41 = n32
n42 = n%(l, 1)
END IF
t4 = n%(l, 0)
'      IF t1 + t2 + t3 + t4 <= best THEN
PRINT n11; n21; n31; n41
PRINT t1; t2; t3; t4
PRINT n11 / gcd(n11, n21); "/"; n21 / gcd(n11, n21); ";"; n21 / gcd(n21, n31); "/"; n31 / gcd(n21, n31); ";"; n31 / gcd(n31, n41); "/"; n41 / gcd(n31, n41); ";"; n41 / gcd(n41, n11); "/"; n11 / gcd(n41, n11); ";";
PRINT #2, n11; n21; n31; n41
PRINT #2, t1; t2; t3; t4
PRINT #2, n11 / gcd(n11, n21); "/"; n21 / gcd(n11, n21); ";"; n21 / gcd(n21, n31); "/"; n31 / gcd(n21, n31); ";"; n31 / gcd(n31, n41); "/"; n41 / gcd(n31, n41); ";"; n41 / gcd(n41, n11); "/"; n11 / gcd(n41, n11); ";";
best = t1 + t2 + t3 + t4
PRINT t1 + t2 + t3 + t4
PRINT #2, t1 + t2 + t3 + t4
PRINT #2,
ct2 = ct2 + 1
'       IF ct2 MOD 11 = 0 THEN DO: LOOP UNTIL INKEY\$ > "": PRINT
'      END IF
END IF

END IF
END IF
NEXT l

END IF
END IF
NEXT k

END IF
END IF
NEXT j
NEXT i

END

FUNCTION gcd (a, b)
x = a: y = b
DO
q = INT(x / y): r = x - y * q
IF r = 0 THEN gcd = y: EXIT FUNCTION
x = y: y = r
LOOP
END FUNCTION

 Posted by Charlie on 2005-08-29 18:24:32

 Search: Search body:
Forums (1)