-2

Prove that a convex 1000000-gon with integer vertices (both coordinates integer) has a side of length at least 550.

MathFun
  • 438
  • My thought: First try to find an upper bound for an angle made between two non-collinear integer vectors of length $\leq l$. – Jair Taylor Jun 08 '17 at 22:15

1 Answers1

3

Consider the edges of the polygon directed anti-clockwise. There are $10^6$ edges, and consider each of them as a vector with integral $x$- and $y$-components.

Since the polygon is convex, all individual edges have different directions.

Assume all of these vectors have length less than $550$. If the start points of the vectors are moved to the origin, then the end points of all these vectors falls into the circle with radius $550$.

But there are only around $550^2\pi = 950\ 331$ lattice points inside the circle, and even so, some of those points have the same directions, which means the number of vectors with different directions inside the circle is less than $1\ 000\ 000$.

This contradiction means some of the edges must have a length at least $550$.

peterwhy
  • 22,256
  • very nice! Much nicer than what I had in mind. Although, to be rigorous you would need find an explicit upper bound for the number of lattice points in the circle instead of an approximation. Next question is - can we find a better lower bound on the length? – Jair Taylor Jun 08 '17 at 22:23
  • @JairTaylor If I consider the unit square around each lattice point (for point $(m,n)$, the square that satisfies $m-.5<x<m+.5$ and $n-.5<y<n+.5$), then it appears that I should increase the radius of the circle to $550+\frac{\sqrt2}2$ to cover the entire area of all the unit squares. The area of this circle is $952\ 776$. – peterwhy Jun 08 '17 at 22:34
  • 1
    @JairTaylor This video deals with finding the number of lattice points in a circle using Gaussian Integers to calculate $\pi$ and this video deals with finding the number of distinct Pythagorean triplets. The first video will get you an exact bound for the number of lattice points and the second video will get you the number of distinct vectors with integer components within a circle of radius $r$. – AlgorithmsX Jun 08 '17 at 22:34
  • @AlgorithmsX I have watched both of these videos :) without them I might not be able to come up with this answer. – peterwhy Jun 08 '17 at 22:35
  • Thank you very much for your time. I really appreciate it! – MathFun Jun 08 '17 at 23:10
  • @MathFun If this answer helps, please consider upvoting the answer and/or making this the best answer. – peterwhy Jun 08 '17 at 23:18
  • @peterwhy Thank you very much for your help. But I think there is something wrong here. Some of these vectors can be equal. For example consider the all point (1,i), i=0,..., 549 as its vertices of the polygon! – MathFun Jun 09 '17 at 08:13
  • @MathFun There are two different grids here: (1) the grid where your polygon is, where edges are from one lattice point to another lattice point, forming a loop; and (2) the grid where my $10^6$ vectors are, where all vectors start from the origin and point outwards. In the grid of my vectors, all your vectors $(1,0), (1,1),\cdots, (1,549)$ have different directions, and so can be different edges of the polygon. – peterwhy Jun 09 '17 at 10:10