207. What is the smallest perimeter that a convex 32-gon can have, all of whose vertices lie at the nodes of a grid paper with a cell side of 1?

$208^{*}$. a) In a $7 \times 7$ square of cells, it is necessary to mark the centers of $k$ cells so that no four marked points form the vertices of a rectangle with sides parallel to the sides of the square. For what largest $k$ is this possible?

b) Solve the analogous problem for a $13 \times 13$ square of cells.
207. Answer: $4+4 \sqrt{2}+8 \sqrt{5}+8 \sqrt{10}+8 \sqrt{13}$.

The contour of the 32-sided polygon $A_{1} A_{2} \ldots A_{32}$ can be represented as the image of the sum of 32 vectors $\overrightarrow{A_{1} A_{2}}+\overrightarrow{A_{2} A_{3}}+\ldots+\overrightarrow{A_{32}} A_{1}=0$.

Since a convex 32-sided polygon can be formed from any 32 vectors with different directions and a sum of 0, the problem reduces to the following: find 32 vectors that satisfy the conditions:

a) the beginning and end of each vector lie at the nodes of a grid paper;

b) any two vectors have different directions;

c) the sum of all vectors is 0;

d) under conditions a) - c), the sum of the lengths of all vectors is minimal.

We will lay out the vectors from one point. The system of 32 vectors depicted in Fig. 85 satisfies all conditions a) - c). Among these vectors, there are four vectors of length 1 (not shown in Fig. 85), four of length $\sqrt{2}$, and eight vectors each of lengths $\sqrt{5}$, $\sqrt{10}$, and $\sqrt{13}$.

$\nabla$ A similar technique of "dense filling of levels" - selecting $n$ sets of four different integer vectors of the smallest length - allows constructing a $4n$-sided polygon with the minimum perimeter and vertices at the nodes.