10
$\begingroup$

Of all hexadecagons lying in the cartesian plane, all of whose vertices are lattice points, and whose sides are of length $1,2,3,\dots,16$ in some order, which two have the largest and smallest area?

The case of dodecagons is dealt with here: Largest and smallest dodecagon with sides $1, 2, 3, \dots,12$ .

$\endgroup$
  • $\begingroup$ Do you know an optimal solution? $\endgroup$ – the default. Jun 27 at 8:18
  • $\begingroup$ Seems like a worthy addition to OEIS. Separate sequences for n=12, 16, etc. I guess start at side 1 and go in order of next shortest side. $\endgroup$ – smci Jun 27 at 18:33
  • 1
    $\begingroup$ I now have a proof for what values of n such n-gons exist. I have also obtained an explicit tight upper bound for the area minimization problem for the case where n is divisible by 4, and an explicit reasonably good upper bound for when n+1 is divisible by 4. $\endgroup$ – SE - stop firing the good guys Jul 10 at 12:52
  • 1
    $\begingroup$ Here you go :-) $\endgroup$ – SE - stop firing the good guys Jul 11 at 13:21
  • 1
    $\begingroup$ (work in progress) A gallery of solutions for small values of $n$ hohmiyazawa.github.io/n-gon-solution-viewer/viewer.html $\endgroup$ – SE - stop firing the good guys Jul 15 at 22:01
13
$\begingroup$

The small one, the "double headed snake"

Area = 59 small hexadecagon

Old attempt: the "circle"

New attempt, using the same diagonals as Weather Vane and shuffling around 9 of the sides:

Area = 1221 large hexadecagon


some results for the problem in general

1. For what values of $n$ do these n-gons exist?

Proof:

Since the n-gons can't be deformed, we have to step away from the (0,0) position of the first corner both in x and y direction on the grid. But since we have to close the shape too, we must end up at (0,0) again. As such, every step in x or y direction must be "undone", and their sum therefore an even number. In the orthogonal case, this only allows $4 | n$ or $4 | n + 1$, since the sum of the side lengths, $\frac{n(n+1)}{2}$ is only even in those cases.

Regarding diagonals:

Diagonal sides contribute to both the x direction and the y direction. But since they form a Pythagorean triple, one of the legs are always an even number. Therefore, the sum of the legs always have the same parity as the hypotenuse, and the parity argument in the previous paragraph is not affected.

But that doesn't say anything about whether the allowed values of $n$ actually have a geometrically valid realisation. I will handle this later

The following construct ("snake body") is going to be the core of all later reasoning:

snake body

It consists of a terminating tail, which uses the number "1" and a pair of small integers, followed by some number of sides constructed by groups of four consecutive integers, together forming a spiral.

If one can find a "snake head" of fixed size, so the remaining integers can be used to build a "snake body", one has an explicit construction for infinitely many values of $n$

A simple snake head:

For the case $4 | n$,  $ n \geq 8$ simple snake head 1

The other simple snake head required:

For the case $4 | n + 1$,  $ n \geq 15$ simple snake head 2

This only leaves a few stray cases, which we can deal with one by one:

  • 3: Trivially impossible
  • 4: Trivially impossible
  • 7: ${(0,0),(7,0),(7,-2),(10,-2),(6,-5),(6,-1),(0,-1)}$
  • 11: ${(0,0),(11,0),(15,-3),(15,-5),(18,-5),(10,1),(1,1),(1,5),(8,5),(8,6),(0,6)}$

All possible values of $n$ have then been covered.


2. An upper bound for the area minimization problem

The snake heads from the proof above already provide a simple upper bound:

$4 | n$

$\frac{n(n+1)}{4} - 2$

$4 | n + 1$

$\frac{n(n+1)}{4} - 11$

But this can be improved.

linear snake heads

The $4 | n + 1$ head has a simple generalization:

linear snake head 1

Lowering the upper bound to:

$\frac{n(n+1)}{4} - 16\lfloor{\frac{n+5}{20}\rfloor} + 5$

For the $4 | n$ case, we need a different head to do the same:

linear snake head 2

Lowering the upper bound to:

$\frac{n(n+1)}{4} - 16\lfloor{\frac{n}{20}\rfloor} + 3$

quadratic snake heads

In the $4 | n + 1$ case, we have this monstrosity:

quadratic snake head 1

Which works out to a bound of

$\frac{n(n+1)}{4} - 11p^2 - 23p - 11$, where $p = \lfloor{\frac{n - 15}{20}\rfloor}$

Asymptotically, this is

$\frac{89}{400} \cdot n^2$

The $4 | n$ is very similar:

quadratic snake head 2

Bound to:

$\frac{n(n+1)}{4} - 11p^2 - 11p - 13$, where $p = \lfloor{\frac{n - 20}{20}\rfloor}$

Which is asymptotically the same.

Improving asymptotic behaviour through sparse multiples of the 5-12-13 triple.

First, it may be beneficial to get a clearer intuition of the quadratic snake heads already presented. Let's take a look at the number line:

number line

Notably, for 3/4 or the range, we simply have pairs of 3-4-5 multiples interspaced by snake body segments.

The next trick is to notice that for values on the form $130k + 26$ and $130k + 39$, we have two multiples of the 5-12-13 triple with just a single pair of 3-4-5 triples in between.

We can simply replace this region with a slightly more elaborate construction, of smaller area.

Of course, when a few 3-4-5 triples are taken out of circulation, the number line is no longer divided into 1/4 and 3/4. The new ratios are 12/51 and 39/51.

The "slightly more elaborate construction" is this one, combining two such 130k areas into a repeating unit:

Segment lengths not to scale, only widths. 5-12-13 module

The red, green and pink pairs are scavenged from the $5k + 1$ and $5k - 1$ pairs, since minimizing their lengths is very much beneficial due to their width. Their original use can be replaced by stealing more snake body legs, at no additional cost.

Pinning down all the terms of the bound would be tedious, but I have calculated the asymptotic behaviour, which is:

$\frac{657301}{3005600} \cdot n^2$

Ever so slightly better than the comparatively less complex quadratic constructions, improving them by 1.7%

3. An lower bound for the area minimization problem

Pick's theorem is once again highly relevant.

While it's hard to guarantee the necessity of internal lattice points (in fact I think an indefinitely expandable construction with only finitely many of them exists), perimeter points are considerably easier. For instance, there are at least $n$ perimeter points, because every vertex is one. That gives $\lceil{\frac{n}{2} - 1\rceil}$

By the generalized version of Euclid's construction of Pythagorean triples, a number that's neither composite nor the sum of two squares can only be placed orthogonally in a lattice.

By the asymptotically equal number of Pythagorean and non-Pythagorean primes, and the prime number theorem, there are asymptotically $\frac{n}{\log{n}}$ such numbers.

Applying Pick's theorem to this fact, the lower bound is proportional to:

$\frac{n^2}{\log{n}}$

I would be very interested if someone can find a bound in the form of a constant factor multiplied by $n^2$


In more practical terms, one takes all side lengths, and express each of them as $k \cdot z$, where $z$ is the diagonal of a primitive Pythagorean triple (counting $(0,1,1)$ as a primitive triple), as large as possible. All of these $k$ values are summed, being the minimum number of perimeter lattice points. The bound for this procedure is quite possibly better than the one obtained through the PNT. (Bound requested!)

4. An upper bound for the area maximization problem

(work in progress)

An easily obtainable upper bound is:

$\lfloor{\frac{n^2 (n+1)^2}{16\pi}\rfloor}$

By noticing that the area can not possibly be larger than that of a circle by the given circumference

A similar bound is:

$\lfloor{\frac{1}{4} \frac{n(n+1)}{2} \cot{\left(\frac{2\pi}{n(n+1)}\right)}\rfloor}$

Because

The area can't be larger than a $\frac{n(n+1)}{2}$ sided regular polygon

5. A lower bound for the area maximization problem

(work in progress)

In the case of $8|n$, we have this indefinitely expandable construction:

tilted square made out of smaller segments

It's also applicable to all $4|n$, since we can just express this as $12 + 8k$, inserting the sides above into the $n=12$ solution, which is already proven to exist.

This gives a bound of:

$\frac{1}{128} n^4$, plus some terms of lower order

This way of "mending" the construction for $4|n$ is very powerful (Do the same for the $4|n + 1$ case, just use the 11-gon solution as base). It's similar to the Euclidean division theorem, and since we already have an existence proof for all possible values of $n$, we can now go wild with constructions requiring $n$ to have very constricted forms, but still be immediately generalizable for sufficiently large $n$

Time for another repeatable unit:

5k

Grouping 8 consecutive units of these, one side of a "big square" can consist of elements 1 and 8 in all these groups, another side 2 and 7, the third 3 and 6, and the last 4 and 5. (all summing to the same length)

This requires $40|n$, but since we have shown that any such construction can be generalized to all valid $n$ of sufficient size, this is a general solution.

It translates 5 perimeter units into a diagonal of length $\frac{\sqrt{365}}{5}$, in contrast to the solution presented earlier that merely achieves 2 perimeter units into a diagonal of $\sqrt{2}$

This improves the asymptotic behaviour to:

$\frac{73}{8000}n^4$

Including more primitive Pythagorean triples (and thus making the integers in the fraction horribly large), one may improve this slightly.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I like the technique for the area between JK and CB. That's the approach I was still looking for in the dodecagon problem. $\endgroup$ – Weather Vane Jun 27 at 12:50
  • 1
    $\begingroup$ @SE-stopfiringthegoodguys Fantastic! $\endgroup$ – Bernardo Recamán Santos Jul 11 at 17:22
  • 1
    $\begingroup$ @BernardoRecamánSantos I found a way of incorporating a few multiples of the 5-12-13 Pythagorean triple into the existing construction. It reduced the bound ever so slightly. $\endgroup$ – SE - stop firing the good guys Jul 12 at 15:01
  • 2
    $\begingroup$ @SE-stopfiringthegoodguys Beautiful work! I think you should seriously consider polishing up all this, prepare a paper and submit to, say, Mathematics Magazine. $\endgroup$ – Bernardo Recamán Santos Jul 14 at 14:19
  • 1
    $\begingroup$ @BernardoRecamánSantos I'm indeed considering writing up something, this problem seems to have more depth than a first glance should suggest. $\endgroup$ – SE - stop firing the good guys Jul 14 at 15:21
7
$\begingroup$

Here's my snake for the smallest area of

62 units

The big numbers are the areas, the small ones are side lengths:

enter image description here
The narrow part is exactly a quarter square in vertical height. The black lines are just for making the areas easier to count and identify.

And here's the most circular 16-gon I managed to make out of these edges:

enter image description here

It has an area of

1201 units

unless I miscounted something.

| improve this answer | |
$\endgroup$
4
$\begingroup$

Smallest area, based on best solution from previous question:

Area = 66 enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Ah, there is an actual working tail. I couldn't keep it from colliding. $\endgroup$ – SE - stop firing the good guys Jun 27 at 10:40
3
$\begingroup$

I have another solution for the greatest area:

Area = $1219$ units

enter image description here

This is
$38 \times 38 = 1444 $
less
$ 3 \times 4 / 2 = 6$
$ 6 \times 8 / 2 = 24$
$ 5 \times 12 / 2 = 30$
$ 9 \times 12 / 2 = 54$
$ 9 \times 3 = 27$
$ 3 \times 8= 24$
$ 5 \times 4 = 20$
$ 1 \times 14= 14$
$ 13 \times 2= 26$

Total $1444 - 225 = 1219 $

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ beat me by 2 units... $\endgroup$ – SE - stop firing the good guys Jun 27 at 16:46
  • 1
    $\begingroup$ Managed to squeeze out 3 more units, so now you do the same :) $\endgroup$ – SE - stop firing the good guys Jun 27 at 17:45
  • 2
    $\begingroup$ @SE-stopfiringthegoodguys but I only need 2 more units! $\endgroup$ – Weather Vane Jun 27 at 19:17
  • 1
    $\begingroup$ @SE-stopfiringthegoodguys you upped the game with your max area, but I've now pipped you by 1. My first answer was (at the time) the largest but of course you deserve the green check because I made no attempt at the smallest area here. $\endgroup$ – Weather Vane Jun 29 at 22:50
  • 1
    $\begingroup$ I did, but it's a bit cheap since you did 93% of the work. $\endgroup$ – SE - stop firing the good guys Jun 29 at 23:31

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.