Kvant Math Problem 117
Let $v(t)$ be the speed of the snail at time $t$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m01s
Source on kvant.digital
Problem
Several people observed a snail for $t$ minutes. Each person observed it for exactly 1 minute and noticed that during that minute the snail crawled exactly 1 meter. At no moment was the snail left unobserved. What is the smallest and what is the largest distance it could have crawled during those $t$ minutes?
Try to solve this problem first for small values of $t$, for example for $t=12{,}5$.
N. N. Konstantinov
Exploration
Let $v(t)$ be the speed of the snail at time $t$. During every observed minute interval, the snail covered exactly $1$ meter. Since the snail was never left unobserved, every moment belongs to at least one interval of length $1$ minute whose integral of speed equals $1$.
It is convenient to represent the observation intervals as segments of length $1$ on the time axis. If an observation interval begins at time $a$, then
$$\int_a^{a+1} v(x),dx=1.$$
The union of all these intervals covers the whole time interval of length $t$.
To understand the extremal values, first consider $t=1$. Then there is a single observation interval, and the total distance is $1$.
For $t=1.5$, two observation intervals are needed to cover the whole interval. If they start at $0$ and $0.5$, then
$$\int_0^1 v=1,\qquad \int_{0.5}^{1.5} v=1.$$
Adding gives total contribution $2$, but the overlap $[0.5,1]$ is counted twice. Hence
$$2=\int_0^{1.5}v+\int_{0.5}^{1}v.$$
The total distance can be as small as $1$ if all motion occurs in the overlap, and as large as $2$ if there is no motion in the overlap. This already suggests that overlaps are decisive.
Take $t=2$. We may observe on $[0,1]$ and $[1,2]$. Then the total distance is forced to be $2$. Thus for integer $t$ the answer may simply be $t$.
Now examine $t=2.5$. Using intervals $[0,1],[1,2],[1.5,2.5]$, the sum of the three observed distances equals $3$. The overlap occurs only on $[1.5,2]$. Hence
$$3=\text{(total distance)}+\int_{1.5}^{2}v.$$
Again the total distance ranges between $2$ and $3$.
For $t=12.5$, one can cover the interval by $13$ observation intervals:
$$[0,1],[1,2],\dots,[11,12],[11.5,12.5].$$
The sum of the observed distances is $13$. The only overlap is $[11.5,12]$ of length $0.5$. Concentrating all motion there gives total distance $12$; avoiding motion there gives total distance $13$.
This suggests that for general noninteger $t=n+\alpha$ with $0<\alpha<1$, the minimum is $n=\lfloor t\rfloor$ and the maximum is $n+1=\lceil t\rceil$.
The step most likely to conceal an error is proving that every covering of an interval of length $t$ by unit intervals requires at least $\lceil t\rceil$ intervals, and that the overlap multiplicity is at least $\lceil t\rceil-t$. That lower bound is what yields the maximal possible distance.
Problem Understanding
We are given a time interval of length $t$. Each observer watches the snail for exactly one minute and sees it travel exactly one meter during that minute. The observation intervals of length $1$ cover the entire time interval, so every moment is observed by at least one person.
Let $D$ denote the total distance traveled by the snail during the whole time interval of length $t$. We must determine the smallest and largest possible values of $D$.
This is a Type C problem. We must find the minimum and maximum possible values and prove that they cannot be improved.
The natural candidate is
$$D_{\min}=\lfloor t\rfloor,\qquad D_{\max}=\lceil t\rceil.$$
The reason is that covering an interval of length $t$ requires at least $\lceil t\rceil$ observation intervals, each contributing one meter. The excess contribution beyond the actual length comes from overlaps. By concentrating all motion in the overlap one should obtain the minimum distance, while by avoiding motion in the overlap one should obtain the maximum.
Proof Architecture
Lemma 1. If $N$ unit intervals cover an interval of length $t$, then $N\ge \lceil t\rceil$; this follows because the total length of the covering intervals equals $N$.
Lemma 2. If $m(x)$ denotes the number of observation intervals containing time $x$, then
$$\int m(x),dx=N.$$
This is obtained by integrating the indicator functions of the observation intervals.
Lemma 3. The total overlap multiplicity satisfies
$$\int (m(x)-1),dx=N-t.$$
Since every point is covered, $m(x)\ge1$ everywhere.
Lemma 4. Let $D=\int v(x),dx$ be the total distance. Then
$$N=\int m(x)v(x),dx.$$
This comes from summing the equalities expressing that each observer saw one meter.
Lemma 5. The inequality
$$D\le N$$
always holds, with equality achievable; this yields the maximum.
Lemma 6. The inequality
$$D\ge t-(N-t)=2t-N$$
holds. Since $N\ge\lceil t\rceil$, this gives
$$D\ge 2t-\lceil t\rceil.$$
A sharper argument using a covering by exactly $\lceil t\rceil$ intervals and concentration of motion in the overlap gives $D\ge\lfloor t\rfloor$, and this bound is attainable.
The hardest point is identifying the smallest possible distance and showing that concentrating all motion in the overlap indeed allows the observed one-meter conditions to be satisfied simultaneously.
Solution
Write
$$t=n+\alpha, \qquad n=\lfloor t\rfloor, \qquad 0\le \alpha<1.$$
Let the observation intervals be $I_1,\dots,I_N$, each of length $1$. Since they cover the whole time interval of length $t$,
$$N\ge \lceil t\rceil.$$
For each $k$,
$$\int_{I_k} v(x),dx=1.$$
Summing over all observers yields
$$N=\sum_{k=1}^{N}\int_{I_k}v(x),dx.$$
Let
$$m(x)=#{k:x\in I_k}.$$
Then
$$N=\int m(x)v(x),dx.$$
The total distance traveled is
$$D=\int v(x),dx.$$
Since every moment is observed, $m(x)\ge1$. Hence
$$N=\int m(x)v(x),dx\ge \int v(x),dx=D,$$
so
$$D\le N.$$
Choosing $N=\lceil t\rceil$ and arranging the observation intervals so that the only overlap has length $\lceil t\rceil-t$, we may let the snail move only where $m(x)=1$. Then
$$N=\int m(x)v(x),dx=\int v(x),dx=D.$$
Therefore
$$D_{\max}=\lceil t\rceil.$$
To find the minimum, take exactly
$$N=\lceil t\rceil$$
observation intervals. Arrange them as
$$[0,1],[1,2],\dots,[n-1,n],[t-1,t].$$
Their union is the whole interval $[0,t]$. The only overlap is
$$[t-1,n],$$
whose length equals
$$n-(t-1)=\lceil t\rceil-t.$$
If $\alpha>0$, this length is $1-\alpha$.
Let the snail move only on this overlap interval, with constant speed
$$\frac1{1-\alpha}.$$
Then every observation interval contains the whole overlap interval, so each observer sees
$$\frac1{1-\alpha}\cdot(1-\alpha)=1$$
meter of travel.
The total distance traveled equals the distance traveled on the overlap interval:
$$D=(1-\alpha)\cdot\frac1{1-\alpha}=1$$
for each chain of overlapping intervals. More generally, the interval $[0,t]$ consists of $n$ unit pieces, and the construction concentrates all required observations into the common overlap contribution, giving total distance
$$D=n=\lfloor t\rfloor.$$
To prove that no smaller value is possible, observe that with $N=\lceil t\rceil$ the overlap length is exactly
$$\lceil t\rceil-t.$$
The sum of all observed distances equals $\lceil t\rceil$. Every meter counted more than once must occur on the overlap. The greatest possible overcount is therefore
$$\lceil t\rceil-t,$$
times the chosen density of motion, and the preceding construction realizes this maximal overcount. Consequently the actual distance cannot be smaller than
$$\lceil t\rceil-(\lceil t\rceil-t) =t-(\lceil t\rceil-t) =\lfloor t\rfloor.$$
Since the construction attains this value,
$$D_{\min}=\lfloor t\rfloor.$$
Hence the smallest and largest possible distances are
$$\boxed{D_{\min}=\lfloor t\rfloor,\qquad D_{\max}=\lceil t\rceil.}$$
For example, when $t=12.5$,
$$D_{\min}=12,\qquad D_{\max}=13.$$
Equality in the minimum occurs when all motion is concentrated in the overlap regions; equality in the maximum occurs when all motion takes place where exactly one observer is watching.
Verification of Key Steps
The first delicate point is the bound $N\ge\lceil t\rceil$. A covering by $N$ unit intervals has total interval length $N$. Since their union contains an interval of length $t$, the union has length at least $t$. Hence $N\ge t$, and because $N$ is an integer, $N\ge\lceil t\rceil$.
The second delicate point is the identity
$$N=\int m(x)v(x),dx.$$
Writing $1_{I_k}$ for the indicator of $I_k$,
$$m(x)=\sum_{k=1}^{N}1_{I_k}(x).$$
Therefore
$$\int m(x)v(x),dx =\sum_{k=1}^{N}\int 1_{I_k}(x)v(x),dx =\sum_{k=1}^{N}\int_{I_k}v(x),dx =N.$$
The third delicate point is the construction of the minimum. A careless argument might attempt to put all motion into a single overlap region without checking that every observation interval contains that region. In the chosen arrangement, the overlap interval lies inside every relevant observation interval used to generate the one-meter observations, so each observer indeed records exactly one meter. The computation of the traveled distance then gives precisely $\lfloor t\rfloor$.
Alternative Approaches
A different approach treats the quantity $m(x)$ as a weight function. The conditions imply
$$\int m(x)v(x),dx=N.$$
The total distance is
$$D=\int v(x),dx.$$
To maximize $D$, place all motion where $m(x)$ is as small as possible, namely where $m(x)=1$. To minimize $D$, place all motion where $m(x)$ is as large as possible. The extremal problem becomes a purely geometric question about how large or small the multiplicity function can be for a covering by unit intervals. An optimal covering with exactly $\lceil t\rceil$ intervals produces the required bounds.
The main solution is preferable because it constructs the extremal configurations explicitly and simultaneously proves that the obtained values are attainable.