Bariz - Problem

Singular

18.03.2006 11:30

2003*4 A line segment of length k passes through at most $\lfloor k \rfloor$ lattice points. (*) Consider the square around the outside of the array. It has 2003*4 points. If one has a convex figure with more lattice points, its convex hull is contained within or on the square, and its perimeter is smaller (you can think of the smaller figure as coming from the square through a series of cuts, each cut by the triangle inequality decreasing the perimeter.) Then, by (*), this smaller figure with smaller perimeter passes through at most a number of points less than 2003*4. Thus 2003*4 is maximal.

cauchyguy

18.03.2006 14:45

I think you misread the problem. The question asks for the largest number of vertices a polygon could have, not the maximum number of lattice points on the boundary. This problem is quite difficult. Only one person solved it, I think.

suweijie

22.04.2006 18:06

I guess the answer is 2008.

spdf

30.07.2006 15:27

cauchyguy;if you know the solution;please post it

Deedlit

08.08.2006 20:18

The answer is 561. First, note that, if we trace the perimeter of the polygon clockwise, we only move to the right on the upper section of the polygon, and only to the left on the lower section. So the total movement horizontally is at most 2003 * 2 = 4006. Similarly, the total movement vertically is at most 4006, and the total movement period is at most 8012. Let n be the number of vertices; consider the n vectors that move each vertex to the next vertex clockwise. Clearly no two vectors can be pointed in the same direction. Let us list all possible vectors (i,j) with integral coordinates in order of "length" |i| + |j|, except that for each collection of vectors V_i,j = {(ci, cj), c in N} with GCD (i, j) = 1, we only choose the vector (i, j). So we are only choosing the vectors (i, j) with i and j relatively prime. The first four vectors are (1, 0), (-1, 0), (0, 1), and (0, -1). The number of vectors of length m is four times the number of such vectors with both coordinates positive; the latter number is phi(m). So the are 4 phi(m) vectors of each length m >= 2. After some calculation, we find that 4 + 4 Sum [m = 2 to 21] m phi (m) = 7988. 4 + 4 Sum [m = 2 to 21] phi (m) = 560. In other words, the minimal sum of the lengths of the a collection of 560 integral vertices with no scalar multiples is 7988. Note that by symmetry, the sum of these 560 vectors is zero; therefore we can construct a convex polygon by ordering them in terms of the angle they make with the positive x-axis. Further, by symmetry, the total movements in the horizontal and vertical directions are the same, and equal 7988/2 = 3884. So the polygon has height and width 1997, and so fits within a 2004 by 2004 lattice. As 8012 - 7988 = 24, there cannot be a convex polygon of 562 vertices or more, since that would require a minimum total movement of 7988 + 22 * 2 = 8032. But we can make a convex polygon with 561 vertices: for example, remove the vectors (5, 16) and (10, -11), and add the vectors (-1, 21), (-5, -17), and (21, 1). Both sets of vectors add up to (15, 5), and the sum of the lengths is 12 greater for the second set in both the horizontal and vertical directions. So, we can form a convex polygon from our new set using the same procedure as before, and the height and width increase to 2003, so it fits perfectly in a 2004 by 2004 lattice.

math154

30.05.2013 10:03

The hardest part of the problem seems to be the construction for $n=561$, so I've included some (quite sketchy) motivation for that below. I'm not really a big fan of these kinds of detail-oriented/random construction problems, though.

Let $f(\langle{x,y}\rangle) = |x|+|y|$ and $S_k = \phi(1)+\cdots+\phi(k)$, $T_k = 1\phi(1)+\cdots+k\phi(k)$ for $k\ge1$. Fix $n\ge4$ and suppose there exists an $n$-gon $P = A_1A_2\ldots A_n$ (ordered clockwise), WLOG (for convenience) with minimal area. Then letting $\vec{v_i} = \overrightarrow{A_iA_{i+1}}$ (indexing mod $n$), we see that (1) $v_i$ must have coprime coordinates for all $i$; (2) for any coprime nonnegative integers $a,b$, the vectors $\langle\pm a,\pm b\rangle$ each appear at most once; (3) when centered at the origin, $v_1,v_2,\ldots,v_n$ run clockwise in that order. For $j>0$, there exist at most $4\phi(j)$ indices $i$ with $f(v_i) = j$ (this is a ``coincidence'' for $j=1$). If $4S_m \le n < 4S_{m+1}$ ($m\ge1$), then \begin{align*} 4(2003) \ge 2X+2Y &= \sum_{i=1}^{n}f(v_i) \ge (m+1)(n-4S_m) + \sum_{k=1}^{m}k(4\phi(k)) \\ &= (m+1)(n-4S_m) + 4T_m, \end{align*}where $X,Y$ are the horizontal and vertical ``diameters'' of $P$, respectively. ($X$ is the sum of the $x$-coordinates of all $v_i$ with nonnegative $x$-coordinates.) The first 22 values of the totient function are \[ 1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,10, \] which allow us to compute $S_7=18$, $S_{11} = 42$, $S_{15}=72$, $S_{21}=140$, $T_7=91$, $T_{11}=236+91=327$, $T_{15}=408+327=735$, $T_{17}=400+735=1135$, $T_{20}=610+1135=1745$, $T_{21}=1997$, $T_{22}=2217>2003$. In particular, $m\le 21$. Furthermore, if $n\ge 4S_{21}$, then $4(2003-1997) \ge 22(n-4S_{21})$ implies $n-4S_{21} \le 1$, so $n\le 4\cdot140 + 1$. If $n=560$, we have an obvious construction: take the $560 = 4S_{21}$ coprime vectors $w_i$ with $1\le f(w_i) \le 21$, and label them $v_1,\ldots,v_n$ in clockwise order. Then by symmetry, $\sum v_i = 0$ and the corresponding polygon $P$ has $X=Y=T_{21}=1997$. If $n=561$, we cannot use all of the $v$ with $f(v)\le21$, or else the $v_i$ cannot sum to zero. Thus we may (a) replace two $f(v)=21$ with $f(v)=22$ (so we have three $22$); (b) replace one $f(v)=21$ with a $f(v)=22$ or $f(v)=23$, or (c) replace one $f(v)=20$ with a $f(v)=22$. (b), (c) seem a bit restrictive (as we only get two vectors to play with, although in some sense we do get ``close'' with things like $(16,-6),(-6,17)$, remove $(10,11)$), so we try (a) instead. The key here is to think in terms of the difference $2003-1997=6$: if we remove a vector $\langle{r,s}\rangle$ with $r>0$, this gives us an additional $r$ ``room'' to work with in the positive $x$-direction (so $r+6$ total). Furthermore, in (a) we have to end up with $X=Y=2003$, so we need to use exactly $r+6$ total. One natural choice is to remove $\langle{a,21-a}\rangle$ and $\langle{-(21-b),-b}\rangle$ with $a,b>0$ and take $\langle{a+6,\pm(16-a)}\rangle$, $\langle{\pm(16-b),-(b+6)}\rangle$. Then it's easy to see we must have $-(16-a)$ and $+(16-b)$, so the final vector must be $\langle{-11,11}\rangle$. Similarly, if we try to use $\langle{a+6,-(16-a)}\rangle$ and $\langle{-(a-5),27-a}\rangle$, we're left with $\langle{a+b-32,10-a-b}\rangle$. But and these three vectors (which must have both coordinates odd, since $22$ is even) add up to $\langle{a+b-21,21-a-b}\rangle$, we must have $a+b-21,21-a-b$ odd. This in turn forces $a+b-32,10-a-b$ both even. Thus we'll want our two removed vectors to share a sign in at least one coordinate: remove some $\langle{a,21-a}\rangle$, $\langle{b,-(21-b)}\rangle$ with $a,b>0$. This time, we take $\langle{-(a-5),27-a}\rangle$ (so $a>5$; note that doing something with $-(27-b)$ instead is analogous). Our negative $x$-coordinates are limited to $-6$ (and thus $-5$, by parity), so $a<11$, which leaves us $a=8,10$ (as $a\perp 21$). Also, since our negative $x$-coordinate sum of $-6$ must be ``split'' between two of the three vectors, we must have $\langle{a+b+6,-(16-a-b)}\rangle$, and thus $\langle{-(11-a),-(11+a)}\rangle$. Comment. We have $S_m\approx \frac{3}{\pi^2}m^2 + O(m\log{m})$ and $T_m\approx \frac{2}{\pi^2}m^3 + O(m^2\log{m})$ using Mobius inversion, where $\frac{2}{\pi^2}\approx\frac15$. (Note $\frac{21^3}{5} < 2003 < \frac{22^3}{5}$.) So in general, the answer is $\Theta(N^{2/3})$ in an $N\times N$ lattice grid (we have an obvious construction for $n=4S_m$ when $N=T_m+1$). Also see China TST 2005 for a problem using this asymptotic bound.