7
$\begingroup$

Can you find a convex quadrilateral such that all its sides, diagonals and area are distinct integers? Note that a polygon is convex if all its internal angles are smaller than 180 degrees.

Good luck!

$\endgroup$
  • 1
    $\begingroup$ Great puzzle! I found a paper about quadrilaterals all of whose side lengths are distinct integers, but adding diagonals and area makes it much harder. (Of course, cyclic quadrilaterals are right out.) $\endgroup$ – Rand al'Thor Sep 17 at 7:12
  • $\begingroup$ I think this puzzle should be more fit in Mathematics Overflow Community :P $\endgroup$ – Conifers Sep 17 at 9:09
10
$\begingroup$

Assume convex quadrilateral has its sides $a,b,c,d$ where $a<b<c<d$, 2 diagonals $m,n$ where $m<n$, and area $Z$.
For convenience, I also assume that $(a,b)$, $(b,c)$, $(c,d)$ and $(d,a)$ are adjacent sides.
enter image description here

Then consider the following properties:

  • Triangle Inequality:
    $a+b>m$, $a+m>b$ and $a+m>b$ stands. Also for $(c,d,m)$, $(a,d,n)$ and $(b,c,n)$.

  • Heron Theorem:
    For any triangle $(p,q,r)$, the area $T$ could be calculated as: $T = \sqrt{s(s-p)(s-q)(s-r)}$ where $s=\frac{(p+q+r)}{2}$.
    Also could be represented as: $T = \frac{1}{4}\sqrt{(p+q+r)(-p+q+r)(p-q+r)(p+q-r)}$.

Here also assume that the area in any triangle $(a,b,m)$, $(c,d,m)$, $(a,d,n)$ and $(b,c,n)$ should be integer.

Due to $T$ is integer, the expression in the square root should has at least $2^4$ by prime factor decomposition. Also assume that each term $(p+q+r),(-p+q+r),(p-q+r),(p+q-r)$ in square root should be all even(contain at least $2^1$ for each), then $(p,q,r)$ will contains only 3 evens or 2 odds & 1 even.

Then start brute-force searching, and checked with the prime factor decomposition to ensure the square root value is rational and Triangle Inequality also holds for all $(a,b,m)$, $(c,d,m)$, $(a,d,n)$ and $(b,c,n)$, finally found one solution:

$(a,b,c,d) = (10,17,28,35)$, $(m,n) = (21,39)$, $Z=T_{(a,b,m)}+T_{(c,d,n)}=378$

I think there may exist a better derivation for this math question, too many assumption for my answer, and the final brute-force is not a pretty solution :P

$\endgroup$
  • $\begingroup$ Wonderfully neat solution! $\endgroup$ – Dmitry Kamenetsky Sep 17 at 8:20
  • 2
    $\begingroup$ Very nice. You assumed that the two smallest sides are adjacent. There could well be other small solutions where the two smallest sides are opposite. $\endgroup$ – Jaap Scherphuis Sep 17 at 8:58
2
$\begingroup$

I ran a computer search, which confirms Conifers' answer.

The program simply tries all values for the sides and the diagonals. I do not assume the sides are in any particular order, and the areas of the triangle on either side of a diagonal need not themselves be integer. Even so, Conifer's answer is the smallest, in the sense that its longest side is minimal. Here are the first few that my program produced:

Sides, diagonals: area
(10,17,28,35) 39,21: 378
(5,29,27,51) 52,30: 396
(17,39,33,55) 60,44: 1056
(33,39,52,56) 65,60: 1938
(16,25,33,60) 52,39: 714
(25,34,33,60) 65,39: 1014
(25,39,52,60) 65,56: 1764
(25,39,60,52) 63,56: 1764

I think that first answer (i.e. Conifers') is also the smallest in area, though the second one comes close.

Here is my program code (C#).

  using System;

  namespace test
  {
     class PseIntQuad {

        static void Main() {
           for (long d = 1; d<=55; d++){
              for (long c = 1; c < d; c++){
                 for (long b = 1; b < c; b++){
                    for (long a = 1; a < b; a++){
                       // up to rotation/reflection there are three orderings of the edges
                       SearchDiag(a, b, c, d);
                       SearchDiag(a, b, d, c);
                       SearchDiag(a, c, b, d);
                    }
                 }
              }
           }
        }

        private static void SearchDiag(long a, long b, long c, long d)
        {
           for (long n = 1; n < a + b && n < c + d; n++){   // n straddles ab, cd
              if (a >= b + n || b >= a + n || c >= d + n || d >= c + n) continue;
              if (n == a || n == b || n == c || n == d) continue;
              long area1 = CalcArea(a, b, n);
              if (area1 <= 0) continue;
              long area2 = CalcArea(c, d, n);
              if (area2 <= 0) continue;
              long area = area1 + area2;
              if (area % 4 != 0) continue;
              for (long m = 1; m < b + c && m < a + d; m++){
                 if (a >= d + m || b >= c + m || c >= b + m || d >= a + m) continue;
                 if (m == a || m == b || m == c || m == d || m == n) continue;
                 long area3 = CalcArea(b, c, m);
                 if (area3 <= 0) continue;
                 long area4 = CalcArea(a, d, m);
                 if (area4 <= 0) continue;
                 if (area3 + area4 == area){
                    Console.WriteLine("({0},{1},{2},{3})  {4},{5}: {6}", a, b, c, d, m, n, area/4);
                 }
              }
           }
        }

        private static long CalcArea(long a, long b, long c)
        {
           long p = (a + b + c) * (a + b - c) * (a - b + c) * (-a + b + c);
           long area = (long)(Math.Sqrt(p)+.5);
           return area * area == p ? area : -1;
        }
     }
  }
$\endgroup$
  • $\begingroup$ You may have a bug in your program, because the smallest area solution is 378. $\endgroup$ – Dmitry Kamenetsky Sep 17 at 13:11
  • 1
    $\begingroup$ @DmitryKamenetsky Thanks, I found the bug, and it does indeed seem to be the smallest in area too (though I haven't proved it). $\endgroup$ – Jaap Scherphuis Sep 17 at 13:31
  • $\begingroup$ You can reduce the search space by starting a at 1+max(0, d-c-b), since d>a+b+c isn't a closed polygon. (Sorry, just popped over from Code Review and saw this!) $\endgroup$ – Toby Speight Sep 20 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.