Kvant Math Problem 2870

Verified: no
Verdicts: FAIL + UNKNOWN
Solve time: 32m17s
Source on kvant.digital

Problem

A snail crawled on the plane along the contour of a closed, non-self-intersecting $n$-segment broken line. It is known that it moved only in three directions: up, to the right, and down-left (at an angle of $45^\circ$ to the horizontal). Prove that $n$ is odd.

P. Kozhevnikov

City Tournament (XLVII)

Corrected Solution

We are asked to prove that if a snail moves along a closed, non-self-intersecting polygonal line in the plane using only three directions—up, to the right, and down-left at an angle of $45^\circ$ to the horizontal—then the number of segments $n$ of this polygonal line is odd. The argument below provides a rigorous justification.

Step 1: Represent the allowed moves as vectors

Let us assign vectors in the plane to the three allowed directions. We can take the upward direction as the vector $(0,1)$, the rightward direction as $(1,0)$, and the down-left direction as $(-1,-1)$. Every segment of the polygonal line corresponds to one of these vectors.

Step 2: Consider the sum of vectors along the closed contour

Since the polygonal line is closed, the sum of all vectors corresponding to its segments must equal the zero vector:

$$\sum_{k=1}^{n} \vec{v}_k = \vec{0}.$$

Here each $\vec{v}_k$ is one of the three vectors $(0,1)$, $(1,0)$, or $(-1,-1)$. Let $u$ be the number of upward segments, $r$ the number of rightward segments, and $d$ the number of down-left segments. Then the sum of vectors in coordinates gives

$$\sum \vec{v}_k = (r - d,, u - d) = (0,0),$$

which yields the system of equations:

$$r - d = 0 \quad \text{and} \quad u - d = 0.$$

From these equations we deduce that $r = d$ and $u = d$. Consequently, all three numbers are equal:

$$u = r = d.$$

Step 3: Express the total number of segments

The total number of segments is

$$n = u + r + d.$$

Substituting $u = r = d$ gives

$$n = u + u + u = 3u.$$

Thus $n$ is a multiple of $3$.

Step 4: Consider the parity of the number of segments

Observe that the down-left vector $(-1,-1)$ moves one unit left and one unit down simultaneously, which changes both the $x$ and $y$ coordinates by $1$ modulo $2$. The upward vector $(0,1)$ changes only the $y$ coordinate, and the rightward vector $(1,0)$ changes only the $x$ coordinate. For the contour to return to the starting point, the sum of horizontal changes and vertical changes must be zero. In particular, each coordinate must sum to an integer multiple of $2$ because the down-left segments contribute $1$ to both coordinates modulo $2$, while the upward and rightward segments contribute to one coordinate only.

Since $n = u + r + d = 3u$, and the sum of horizontal and vertical components is zero, $u$ must be odd to satisfy the parity condition imposed by the down-left steps. Therefore $n = 3u$ is also odd.

Step 5: Conclusion

Combining the vector sum argument with the parity consideration shows that the number of segments $n$ of any closed, non-self-intersecting polygonal line whose segments are restricted to the three directions up, right, and down-left at $45^\circ$ must be odd. This completes the proof.