Problem 1550

1. Initial Setup and Assumptions:
- We are given a closed path on the vertices of an $n \times n$ square, passing through each vertex exactly once.
- We need to prove that there exist two adjacent vertices such that if we cut the path at these points, each resulting piece has a length of at least a quarter of the total path.

2. **Observation on $n$**:
- It is noted that $n$ must be even for such a path to exist. Hence, we write $n = 2m$ for some integer $m$.

3. Graph Representation:
- The closed path divides the area of the square into two parts: inside and outside.
- Consider each square inside the path as a vertex of a graph. Connect two vertices if their corresponding squares are adjacent.
- This graph is a tree (connected and acyclic).

4. Vertices Count Using Pick's Theorem:
- By Pick's Theorem, the number of vertices inside the path is $2n^2 - 1$.

5. Maximum Degree of the Tree:
- The maximum degree of this tree is 4, as each square can be adjacent to at most 4 other squares.

6. Lemma: If the maximum degree of a tree is 4, then there is an edge in it that divides the graph into two parts, each having at least $\frac{n-1}{4}$ vertices.
- Proof of Lemma:
- Let $v$ be an arbitrary vertex and make it the root of the tree.
- Let its neighbors be $v_1, v_2, v_3, v_4$.
- Let the subgraph of our tree with the root $v_i$ be $V_i$.
- By the pigeonhole principle, one of the $V_i$'s has at least $\frac{n-1}{4}$ vertices, say $V_1$.
- If the edge $vv_1$ is not good, $V_1$ must have at least $\frac{3(n-1)}{4}$ vertices except $v_1$.
- Repeat the process for the subgraphs with roots as neighbors of $v_1$.
- This process must stop eventually, yielding a good edge, as otherwise, we would get a graph with infinite vertices.

7. Application of Lemma to the Main Problem:
- There exists an edge $ab$ dividing the graph into two parts, each having at least $\frac{n^2-1}{2}$ vertices.
- This edge cuts the lattice edge between two vertices, say $t$ and $s$.

8. Conclusion:
- Deleting the edge $ab$ results in two trees, each having at least $\frac{n^2-1}{2}$ vertices.
- Using Pick's Theorem, each of the two paths connecting $t$ and $s$ has at least $n^2$ edges.
- Thus, each piece of the path has a length of at least a quarter of the total path.

$\blacksquare$