
Problem 5. Let $n$ be a given positive integer. Say that a set $K$ of points with integer coordinates in the plane is connected if for every pair of points $R, S \in K$, there exist a positive integer $\ell$ and a sequence $R=T_{0}, T_{1}, \ldots, T_{\ell}=S$ of points in $K$, where each $T_{i}$ is distance 1 away from $T_{i+1}$. For such a set $K$, we define the set of vectors

$$
\Delta(K)=\{\overrightarrow{R S} \mid R, S \in K\}
$$

What is the maximum value of $|\Delta(K)|$ over all connected sets $K$ of $2 n+1$ points with integer coordinates in the plane?

Russia, Grigory Chelnokov


Solution. We claim the answer is $2 n^{2}+4 n+1$. A model is $K=\{(0,0)\} \cup\{(i, 0) ; 1 \leq i \leq n\} \cup\{(0, i) ; 1 \leq i \leq n\}$, when $W=\{(a,-b) ; 0 \leq a, b \leq n\} \cup\{(-a, b) ; 0 \leq a, b \leq n\}$. It is left to prove that $|W| \leq 2 n^{2}+4 n+1$ for any set $K$.

What the statement of the problem describes is a connected graph $G=(K, E)$ of order $2 n+1$, whose vertices are the points in $K$, while the edges are the horizontal/vertical segments of length 1 that connect (some of) these points. The key to the proof is to sequence the elements of $K$ as $A_{0}, A_{1}, \ldots, A_{2 n}$ such that the graph $G_{k}:=G\left[A_{0}, A_{1}, \ldots, A_{k}\right]$ is connected for every $1 \leq k \leq 2 n$; this can be done through

Lemma.[2] The vertices of a finite connected graph $G$ can always be enumerated, say as a sequence $\nu_{0}, \ldots, v_{|G|-1}$, so that $G_{k}:=G\left[v_{0}, \ldots, v_{k}\right]$ is connected for every $1 \leq k \leq|G|-1$.

Proof. Pick any vertex as $v_{0}$, and assume inductively that $v_{0}, \ldots, v_{k}$ have been chosen for some $0 \leq k<|G|-1$. Now pick a vertex $v \in G-G_{k}$. As $G$ is connected, it contains a $v-v_{0}$ path $P$. Choose as $v_{k+1}$ the last vertex of $P$ in $G-G_{k}$; then $v_{k+1}$ has as neighbour in $G_{k}$ the next vertex of $P$. The connectedness of every $G_{k}$ follows by induction on $k$.

Moreover, if we just keep the edges through which $A_{k+1}$ has the (selected) neighbour in $G_{k}$, then $G_{k}$ is a tree, and so $G_{2 n}$ is a spanning tree of $G$. Call the vertex horizontal (vertical) if the edge that connects him is horizontal (vertical). Denote by $h$, respectively $v$, the number of horizontal, respectively vertical vertices; since $G_{2 n}$ is a tree, it follows $h+\nu=2 n$. The point $A_{0}$ contributes $2 n+1$ vectors $\overrightarrow{A_{0} A_{i}}$. Now, for $0 \leq k \leq 2 n$, each point $A_{k+1}$ contributes at most $(2 n+1)-x$ new vectors, where $x=h$ if the vertex is horizontal, respectively $x=\nu$ if the vertex is vertical, since those vectors $\overrightarrow{A_{k+1} A_{i}}$, with ends at the corresponding edges
of same direction, will be duplicated by the vectors determined by the opposite parallel sides of the parallelograms created, which have already been accounted for.

Therefore the total number of distinct vectors will be $|W| \leq(2 n+1)^{2}-h^{2}-v^{2}$. But $h^{2}+v^{2} \geq \frac{1}{2}(h+v)^{2}=2 n^{2}$, hence $|W| \leq(2 n+1)^{2}-2 n^{2}=2 n^{2}+4 n+1 .[3]$
