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

Home > Shapes > Geometry
A quadrilateral query (Posted on 2005-08-29) Difficulty: 3 of 5
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.)
Solution 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
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 (1)
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