Beautiful problem - fits into the category of combinatorial geometry of numbers:-) Any even $ n\ge4$ works, and any odd $ n$ fails. Let $ A_i(x_i,y_i)$, $ i = \overline{1,n + 1}$, $ A_{n + 1} = A_1$ be the sequence of vertices of our polygon. Since $ A_iA_{i + 1}$ is odd, $ x_{i + 1} + y_{i + 1}\not\equiv x_i + y_i\pmod2$. Then if $ n$ is odd, from one side $ x_1 + y_1\equiv x_n + y_n$. On the other side $ A_n$ and $ A_1$ are consecutive vertices, so the above incongruency must hold. Let now $ n$ be even. I assume there are several ways... We will construct an $ n$-gon $ A_1A_2\ldots A_n$, so that $ Ox\|A_1A_n\|A_2A_{n - 1}\|\ldots$ and $ A_1A_n\cap A_2A_{n - 1}\cap\ldots\neq\emptyset$. We use induction. Assume we have constructed such a convex polygon $ A_1A_2\ldots A_{2k - 2}$, where $ n = 2k$. Let $ M$ be a lattice point whose $ Ox$ coordinate lies both on $ A_1A_n$ and $ A_{k - 1}A_k$ (such a point exists, since $ A_1A_n\cap A_2A_{n - 1}\cap\ldots\neq\emptyset$. Consider the line $ d$ through $ M$ parallel to $ Oy$. Clearly, we can pull the right side of the polygon (wrt $ d$) by any number even number of units, and obtain an also good polygon. Call this transformation a $ T$-extension if after applying it the side $ A_{k - 1}A_k$ becomes equal to $ T$, where $ T$ is obviously odd. So having constructed a convex $ A_1A_2\ldots A_{2k - 2}$, let $ \alpha_i = \angle(A_{i + 1}A_i,Ox)$ for $ i = 2,\ldots,k - 1$ and $ \beta_i = \angle(A_iA_{i + 1},Ox)$ where $ i =k, k + 1,\ldots,n - 1$ and all angles are taken acute. From the convexity of our polygon $ \alpha_2 > \alpha_3 > \ldots > \alpha_{k - 1}$ and $ \beta_{n - 1} > \beta_{n - 2} > \ldots > \beta_k$. Define $ \theta = \min\{\beta_k,\alpha_{k - 1}\}$. We will show that there is a $ T$-extension and two points $ X$ and $ Y$ so that $ A_{k - 1}XYA_k$ is a trapezium with $ XY$, $ A_{k - 1}X$ and $ YA_k$ all odd and $ \max(\angle(XA_{k - 1},Ox),\angle(YA_k,Ox)) < \theta$. The last condition will ensure the convexity of $ A_1\ldots A_{k - 1}XYA_k\ldots A_{2k - 2}$. Let $ A = A_{k - 1}$, $ B = A_k$. A $ T$-estension makes $ AB$ of length $ T$, where $ T$ is odd, arbitrarily large. Let $ m = 6k + 3$ for some $ k$. Note that $ (6k + 3)^2 + (18k^2 + 18k + 4)^2 = (18k^2 + 18k + 5)^2$ and $ (6k + 3)^2 + (6k^2 + 6k)^2 = (6k^2 + 6k + 3)^2$. So it is worth taking the altitude of the trapezium $ AXYB$ equal to $ 6k + 3$. Clearly $ AX = 18k^2 + 18k + 5$ and $ YB = 6k^2 + 6k + 3$, which are odd numbers. Note also that $ XY = AB - (18k^2 + 18k + 4) - (6k^2 + 6k)$, so it is odd. Moreover this proves the base of the induction - the case $ n = 4$. Since $ \tan\angle XAB = \frac {6k + 3}{18k^2 + 18k + 4}$ and $ \tan\angle{YBA} = \frac {6k + 3}{6k^2 + 6k + 2}$, for sufficiently large $ k$, we'll have that these values are less than $ \tan\theta$, ensuring the angles are less than $ \theta$. It is quite clear they are different hence $ AX\neq BY$. Moreover, for big enough $ k$, $ AX,BY >$ all other sides except $ XY$ and $ A_1A_{2k - 2}$ which, by means of a sufficiently large extension (enough large to cover all our requirements), can become the largest sides of $ A_1A_2\ldots A_{k - 1}XYA_kA_{k + 1}\ldots A_{2k - 2}$.

Actually this problem is very easy(even to the degree of trivial). It was also on one of the quizzes of the 2008 USA Black MOSP and was solved by almost all people.

Similarly as above we show that $n$ is even and greater then 2. I do the construction in different way. At first we prove following lemma: Lemma "I said that" : For every even $n\ge4$, even positive number $s$ and odd positive numbers $l_1<l_2,<dots<l_{n-2}$ there are odd positive numbers $K,k_1,k_2,\dots,k_{n-2}$ such that numbers $l_1k_1,l_2k_2,\dots,l_{n-2}k_{n-2}$, $Ks^2-1$ and are all pairwise different and \[sK=l_1k_1+l_2k_2+\dots+l_{n-2}k_{n-2}.\] Proof of the lemma : Let $L=l_2+l_2+\dots+l_{n-2}$. Notice that $L$ is odd. Then just put $k_i=l_1$ for all $1<i\le n-2$ and $K=K'l_1$. Then we'll get $sK'=L+k_1$. Obviously for any choice of $K'$ we get unique odd $k_1$. Now just use odd $K'$ which is so high, that $Ks^2-1$ and $l_1k_1=l_1(sK'-L)$ don't have the same value (it's possible, because $s\ne0\neK$) and they are neither equal to any of $k_il_i$. Two of $k_il_i$-s obviously don't have the same value, because $l_{i+1}>l_i$. $\square$ Back to the problem. We'll just take $n-1$ rightangle triangles with sides $4a,4a^2-1$ and $4a^2+1$. First one we want to put on $x$-axis by its odd side. The rest we want to put from top of this triangle whole the way down, one after another, with even side horizontal. And in order to make it work, we just simply find odd coefficients to multiply all the triangles, which exist because I said that. Q.E.D.

khina wrote: The vectors have commas because latex can't do spaces FYI, $\LaTeX$ can do spaces, although its implementation is a bit clunky. \[ (3\,4)\qquad (3\; 4)\qquad (3\;\;4)\qquad(3\;\;\;4) \]

I believe latex can also do spaces if you insert a tilde, as such: $3~4~5$ (Compare this to the same latex without spaces, which is $345$)