Kvant Math Problem 932
The anaconda is an arbitrary polygonal line of total length $10$ contained in the unit square.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m48s
Source on kvant.digital
Problem
In a square cell with a side of 1 m, there is an anaconda 10 m long. Baron Munchausen claims that at any moment he can shoot the anaconda in 6 places with a single shot. Is the Baron exaggerating? (The anaconda can be considered an arbitrary broken line of length 10, located inside the square $1\times1$.)
S. B. Gashkov
Moscow Mathematical Olympiad
Exploration
The anaconda is an arbitrary polygonal line of total length $10$ contained in the unit square. A single shot should be interpreted as a straight line. The question is whether there always exists a line meeting the snake in at least $6$ points.
A first observation is that every line segment of the snake has some projection onto any chosen direction. If we project the whole snake onto a line perpendicular to the shot direction, the total length of the projection cannot exceed the total length $10$ of the snake.
Suppose we choose a family of parallel shooting lines. Every time such a line intersects the snake, it contributes one intersection point. If we integrate the number of intersections over all lines of the family, each segment contributes exactly the length of its projection onto the perpendicular direction. This is the one-dimensional version of Crofton's formula.
To obtain a lower bound on the maximum number of intersections, we need a direction for which the total projected length is large. Since the snake lies in a unit square, a natural choice is the horizontal direction. Let $y(s)$ be the vertical coordinate along the snake parametrized by arc length. Then
$$\int_0^{10} |y'(s)|,ds$$
equals the total vertical variation of the snake and is at most $10$. The average number of intersections with horizontal lines equals precisely the total vertical variation.
This alone does not help, because the vertical variation could be small. We need a direction in which the variation is guaranteed to be large.
Let the endpoints of each segment be $(x_i,y_i)$ and $(x_{i+1},y_{i+1})$. The segment length is
$$\ell_i=\sqrt{(\Delta x_i)^2+(\Delta y_i)^2}.$$
For every segment,
$$|\Delta x_i|+|\Delta y_i| \ge \ell_i.$$
Summing over all segments gives
$$V_x+V_y\ge 10,$$
where $V_x=\sum |\Delta x_i|$ and $V_y=\sum |\Delta y_i|$ are the total variations of the coordinates. Hence at least one of them is at least $5$.
If $V_y\ge5$, the average number of intersections with horizontal lines is at least $5$. Since the square has height $1$, some horizontal line must meet the snake at least $5$ times. Average at least $5$ yields only $5$, not $6$.
The problem asks for $6$, so a sharper counting argument is needed. The snake length is $10$ in a strip of width $1$. If $V_y\ge5$, then the average number of intersections with horizontal lines equals at least $5$. Intersections are counted by a nonnegative integer-valued function $N(y)$. For almost every $y$, the number $N(y)$ is even, except possibly when $y$ coincides with an endpoint level. Indeed, crossing a horizontal line, the curve alternates between entering and leaving the half-plane. Thus values $1,3,5$ occur only on a set of measure zero. Consequently, if the average is at least $5$, some horizontal line must have at least $6$ intersections.
This parity observation is the crucial point.
Problem Understanding
We are given an arbitrary polygonal line of length $10$ contained in a square of side $1$. A shot is a straight line, and Baron Munchausen claims that no matter how the anaconda is placed, there is always a line that intersects it in at least six points.
This is a Type B problem. We must prove the stated claim.
The core difficulty is converting the large total length of the snake into a guaranteed large number of intersections with one straight line. The decisive idea is to compare the snake's length with the total variation of one coordinate and then average intersection counts over a family of parallel lines.
Proof Architecture
Lemma 1. If $V_x$ and $V_y$ denote the total variations of the $x$ and $y$ coordinates along the polygonal line, then $V_x+V_y\ge10$.
Sketch. For each segment, $|\Delta x|+|\Delta y|$ is at least the Euclidean length of the segment; summing over all segments gives the claim.
Lemma 2. At least one of $V_x,V_y$ is at least $5$.
Sketch. This follows immediately from Lemma 1.
Lemma 3. For a polygonal line, the integral of the number $N(y)$ of intersections with the horizontal line $Y=y$ equals $V_y$.
Sketch. Each segment contributes to the integral exactly the vertical length $|\Delta y|$ of that segment.
Lemma 4. For almost every $y$, the number $N(y)$ is even.
Sketch. A horizontal line not passing through a vertex meets the polygonal line transversally; intersections occur in enter-exit pairs.
The hardest step is Lemma 4 together with the deduction that an average value at least $5$ forces some value at least $6$.
Solution
Let the anaconda be represented by a polygonal line of total length $10$ contained in the unit square.
For each segment of the polygonal line, let $\Delta x$ and $\Delta y$ be the changes of its coordinates. Since
$$\sqrt{(\Delta x)^2+(\Delta y)^2}\le |\Delta x|+|\Delta y|,$$
summing over all segments yields
$$10\le V_x+V_y,$$
where
$$V_x=\sum |\Delta x|, \qquad V_y=\sum |\Delta y|.$$
Hence at least one of $V_x$ and $V_y$ is not smaller than $5$. Interchanging the coordinate axes if necessary, assume
$$V_y\ge5.$$
For $y\in[0,1]$, let $N(y)$ denote the number of intersection points of the anaconda with the horizontal line $Y=y$.
Consider one segment of the polygonal line. If its endpoints have vertical coordinates $a$ and $b$, then the horizontal line $Y=y$ intersects this segment for exactly those $y$ between $a$ and $b$. Therefore the contribution of this segment to
$$\int_0^1 N(y),dy$$
is precisely $|a-b|=|\Delta y|$.
Summing over all segments,
$$\int_0^1 N(y),dy=V_y.$$
Since $V_y\ge5$,
$$\int_0^1 N(y),dy\ge5.$$
Now consider values of $y$ that are not equal to the vertical coordinate of any vertex of the polygonal line. There are only finitely many excluded values. For such a $y$, every intersection with the horizontal line is transversal. Moving along the polygonal line, each time it crosses the line $Y=y$ it passes from one side of the line to the other. Consequently the intersections occur in pairs, and $N(y)$ is even.
Thus, for almost every $y$,
$$N(y)\in{0,2,4,6,\ldots}.$$
Assume that every horizontal line met the anaconda in at most $4$ points. Then for almost every $y$ we would have
$$N(y)\le4,$$
which would imply
$$\int_0^1 N(y),dy\le4.$$
This contradicts
$$\int_0^1 N(y),dy\ge5.$$
Hence there exists a value of $y$ for which
$$N(y)\ge6.$$
The horizontal line $Y=y$ is a straight line intersecting the anaconda in at least six points. Therefore Baron Munchausen's claim is correct.
This completes the proof.
∎
Verification of Key Steps
The identity
$$\int_0^1 N(y),dy=V_y$$
must be checked segment by segment. A segment with endpoint heights $a$ and $b$ intersects exactly those horizontal lines whose levels belong to the interval between $a$ and $b$. The measure of that interval is $|a-b|$. Summing over all segments counts every intersection exactly once, yielding the formula.
The parity statement requires excluding horizontal lines through vertices. For a level $y$ not equal to any vertex height, every crossing changes the sign of $Y-y$. Starting and ending on one side or the other, the number of sign changes must be even. Without excluding vertex levels, tangencies or passages through vertices could spoil this argument.
The deduction from average at least $5$ to existence of a line with at least $6$ intersections uses the parity restriction. Without parity, an average of $5$ would only imply the existence of a level with at least $5$ intersections. Since almost every value of $N(y)$ is even, the largest value below $6$ is $4$. Hence average at least $5$ forces some value at least $6$.
Alternative Approaches
Instead of horizontal lines, one may consider both horizontal and vertical lines simultaneously. Since $V_x+V_y\ge10$, one of the two averages,
$$\int_0^1 N_h(y),dy=V_y, \qquad \int_0^1 N_v(x),dx=V_x,$$
is at least $5$. The rest of the argument is identical. This formulation emphasizes the symmetry of the square.
Another approach uses integral geometry. Averaging the number of intersections with lines of a fixed direction gives the total projection length of the curve onto the perpendicular direction. Since the sum of the projection lengths onto the coordinate axes is at least the total length $10$, one direction has average intersection count at least $5$. The parity argument then upgrades $5$ to $6$. The coordinate-variation proof is preferable because it avoids any machinery beyond elementary geometry and integration.