Local Mathematical Competitions

We claim the answer is $2n^2+4n+1$. A model is $$K=\{(0,0)\}\cup \{(i,0);1\le i\le n\}\cup \{(0,i);1\le i\le n\},$$ when $$W=\{(a,-b);0\le a,b\le n\}\cup \{(-a,b);0\le a,b\le n\}.$$ It is left to prove that $|W|\le 2n^2+4n+1$ for any set $K$. What the statement of the problem describes is a connected graph $G=(K,E)$ of order $2n+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,\dots ,A_{2n}$ such that the graph $G_k:=G[A_0,A_1,\dots ,A_k]$ is connected for every $1\le k\le 2n$; this can be done through LEMMA. The vertices of a finite connected graph $G$ can always be enumerated, say as a sequence $v_0,\dots ,v_{|G|-1}$, so that $G_k:=G[v_0,\dots ,v_k]$ is connected for every $1\le k\le |G|-1$. Proof. Pick any vertex as $v_0$, and assume inductively that $v_0,\dots ,v_k$ have been chosen for some $0\le 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 neighbor in $G_k$ the next vertex of $P$. The connectedness of every $G_k$ follows by induction on $k$. $\square$

Moreover, if we just keep the edges through which $A_{k+1}$ has the (selected) neighbor in $G_k$, then $G_k$ is a tree, and so $G_{2n}$ 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_{2n}$ is a tree, it follows $h+v=2n$. The point $A_0$ contributes $2n+1$ vectors $\overrightarrow{A_0{A}_i}$. Now, for $0\le k\le 2n$, each point $A_{k+1}$ contributes at most $(2n+1)-x$ new vectors, where $x=h$ if the vertex is horizontal, respectively $x=v$ 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|\le (2n+1{)}^2-h^2-v^2$. But $h^2+v^2\ge \frac{1}{2}(h+v{)}^2=2n^2$, hence $|W|\le (2n+1{)}^2-2n^2=2n^2+4n+1$.