Polygon with integer vertices

Question

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

Answer 1

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$.