Let $(x_i,y_i)$ be the coordinates of the points of the polygon, with $i \in \{1,2,\ldots, n \}$. Assume that at the first move we draw a horizontal segment, alternating from horizontal to vertical segments from there. Moreover, WLOG assume that $x_1=y_1=0$ (else we may translate the polygon). Then, $x_{i+1}=x_i$ if $i$ is even and $x_{i+1}=x_i \pm 1$ otherwise. Similarly, $y_{i+1}=y_i$ if $i$ is odd and $y_{i+1}=y_i \pm 1$ otherwise. Let $e_i,j_i \in \{-1,1 \}$ be such that $x_{i}=x_{i+1}+e_i$ for all odd $i$ and $y_{i+1}=y_i+j_i$ for all even $i$. Firstly, note that $n$ must be a multiple of $4$. Indeed, note that the sum of all $e_i$ must be zero, since we end up at the origin. However, since we have a total of $\dfrac{n}{2}$ $e_i$'s, we must have that $\dfrac{n}{2}$ is even, and so $n$ is a multiple of $4$. We invoke the shoelace formula (thanks to Panagiotis Liampas for suggesting the use of this formula). Then, we have $\displaystyle E=\sum_{i=1}^{n} \dfrac{(y_i+y_{i+1})(x_i-x_{i+1})}{2},$ and since the summands for $i$ even are all zero, we only have to care for the summands with $i$ odd. Then, $\displaystyle E=\sum_{1 \leq i \leq n, \, i \,\,\, {\rm even}} y_ie_i,$ and since $y_{i+2}=y_{i+1}=y_i+j_i$ for all even $i$, we obtain that $\displaystyle E=\sum_{1 \leq i \leq n, \, i \,\,\, {\rm even}} (j_0+j_2+\ldots+j_{i-2})e_i$. Now, note that if we change a $j_i$ from $-1$ to $1$ or vice versa, the parity of $E$ doesn't change. So, we may assume that all $j_i$ are $1$. Similarly, we may assume the same for all $e_i$. Therefore, $\displaystyle E \equiv \sum_{1 \leq i \leq n, \, i \,\,\, {\rm even}} \dfrac{i(i-2)}{4}=\sum_{i=1}^{n/2} (i^2-i)=$ $=\dfrac{n(n+2)(n-5)}{24},$ and so $E$ is even if and only if $16 \mid n(n+2)(n-5),$ or equivalently (note that $4 \mid n$), $8 \mid n$, i.e. the perimeter of the polygon is a multiple of $8$, as desired.

Dang, sniped... Annihilated by the shoelace formula. The number of moves is divisible by $4$ as we must have had an equal even number of horizontal and vertical moves in order to go back to the origin. Let the points in counter-clockwise order (this may require considering the path in reverse) be $A_{0} = (0, 0), A_{1} = (x_{1}, y_{1}),\dots, A_{0} = A_{4n}=(x_{4n}, y_{4n})$. WLOG let the first move be horizontal and denote $\varepsilon_{i} = x_{2i-1}-x_{2i-2}$ and $\delta_{i} = y_{2i} - y_{2i-1}$ for all $1\leq i\leq 2n$. Clearly $\varepsilon_{i}, \delta_{i} \in\{+1,-1\}$ and $\sum\limits_{i=1}^{2n} \varepsilon_{i} = \sum\limits_{i=1}^{2n} \delta_{i} = 0$. Therefore the area of $A_{0}A_{1}\dots A_{4n-1}$ is given by \[S = \frac{1}{2} \begin{vmatrix} 0 & 0 \\ x_{1} & y_{1} \\ x_{2} & y_{2} \\ \vdots & \vdots \\ x_{4n-1} & y_{4n-1} \\ x_{4n} & y_{4n} \end{vmatrix} = \frac{1}{2} \begin{vmatrix} 0 & 0 \\ \varepsilon_{1} & 0 \\ \varepsilon_{1} & \delta_{1} \\ \varepsilon_{1}+\varepsilon_{2} & \delta_{1}\\ \varepsilon_{1}+\varepsilon_{2} & \delta_{1}+\delta_{2}\\ \vdots & \vdots \\ 0 & \sum\limits_{i=1}^{2n-1} \delta_{i} \\ 0 & 0 \\ \end{vmatrix} = \sum\limits_{k=1}^{2n-1} \left(\sum\limits_{i=1}^{k} \varepsilon_{i}\right) \left(\sum\limits_{j=1}^{k} \delta_{j}\right) - \sum\limits_{k=1}^{2n-1} \left(\sum\limits_{i=1}^{k} \varepsilon_{i}\right) \left(\sum\limits_{j=1}^{k-1} \delta_{j}\right) = \sum\limits_{k=1}^{2n-1} \delta_{k}\sum\limits_{i=1}^{k}\varepsilon_{i} \]The last expression is the sum of $\binom{2n-1}{2} = n(2n-1)$ summands $\varepsilon_{i}\delta_{j} = \pm 1$ so its parity is equal to that of $n(2n-1)$. Therefore $S$ is even iff $n$ is even, i.e. the number of moves (or, equivalently, perimeter) $4n$ is divisible by $8$.

This problem is very beautiful. Certainly a shame it wasn't on the test. Is this one of the rare BMO Belukhov problems? I recall that after our TST, every one of the Romanian IMO team members had a different solution. In particular, I remember that I had the idea to make transformations on the shape by reflecting some adequately chosen unit squares, which leaves the area unchanged modulo 2 and the perimeter unchanged overall. Somebody else considered the diagonals of some of the unit squares and expressed the area and the perimeter using those. The other people found more or less the official solutions, which I will post below: Solution 1. Color the horizontal gridlines of the lattice red and blue alternatively. Let there be $r{}$ red segments on the perimeter and $s{}$ red segments in the interior of the shape. We see that every fourth segment on the perimeter of the shape will be red, therefore we have $P = 4r$. Also, every square has exactly one red edge, thus $A = r + 2s$. Hence $A \equiv r \bmod 2$ from which the result follows. Solution 2.Color the lattice unit squares black and white in a chessboard manner. The alternation of vertical and horizontal segments means that all squares with an edge on the perimeter and lying within the shape are of the same color, say black. Any internal edge within the shape lies between a white and black square, so if the number of white squares within the shape is $W$, the number of edges of the chessboard lying inside the shape is $4W$. If the total number of squares in the shape is $A{}$, then $4A$ counts every edge on the perimeter once, and every internal edge twice, so the perimeter has length $P = 4A - 8W$, which is a multiple of eight if and only if $A{}$ is even. Solution 3. We have as many horizontal perimeter edges as vertical, so it is enough to show that the area is even if and only if the number of vertical perimeter edges is a multiple of four. In each horizontal strip of height 1, pair the vertical perimeter edges in order from left to right. (We can do so because there must be an even number of vertical perimeter edges in every such strip.) Let us assume that we have $P{}$ such pairs. Thus, we need to show that the area is even if and only if $P{}$ is even. As in Solution 2, every such pair of perimeter edges encloses a consecutive set of squares of the shape with the first and last of these squares being, without loss of generality, black. So each such pair accounts for an odd number of squares inside the shape and therefore the area is even if and only if $P{}$ is even as required. Solution 4.By Green’s Theorem the area of the shape is equal to \[\int_C x \ dy\]where $C{}$ is the boundary of the shape traversed anticlockwise. We partition $C{}$ into its line segments of length 1. Each such line segment contributes 0 to the integral if it is horizontal and $\pm a{}$ to the integral if it is on the vertical line $x = a{}$. Every two consecutive vertical line segments contribute \[\pm a \pm (a \pm 1) \equiv 1 \bmod 2,\]so the area is even if and only if the number of vertical line segments is divisible by four, which happens if and only if the perimeter is divisible by eight, since there is an equal number of horizontal and vertical line segments

The shape is a Jordan curve, so it has an interior. Shoot a laser from every segment into the interior of the curve, and let it stop when it hits the boundary again. The perimeter is equal to twice the number of lasers, and the sum of lengths of the lasers is equal to twice the area. Showing that every laser has odd length will prove the problem. The proof of this just relies on the fact that you make an equal number of horizontal moves as you do vertical ones before reaching the opposite side that the laser hits.

gvole wrote: The shape is a Jordan curve, so it has an interior. Shoot a laser from every segment into the interior of the curve, and let it stop when it hits the boundary again. The perimeter is equal to twice the number of lasers, and the sum of lengths of the lasers is equal to twice the area. Showing that every laser has odd length will prove the problem. The proof of this just relies on the fact that you make an equal number of horizontal moves as you do vertical ones before reaching the opposite side that the laser hits. Actually, it's way cleaner to only consider vertical lasers (or equivalently only horizontal lasers).

@gvole There's no need for Jordan's theorem in order to show that a lattice polygon has an interior Also, what you described is the third solution in #5.

I know, this was just a neat way to write it up and visualize it.

This was P5 on the UK TST. Very cool problem