8
$\begingroup$

This is problem 23.2.8.4 from 66 MOSCOW MATHEMATICAL OLYMPIADS (author: N. Konstantinov).

"A snail crawls along a straight line, always forward, at a variable speed. Several observers in succession follow its movements during $6$ minutes. Each person begins to observe before the preceding observer finishes the observation and observes the snail for exactly one minute. Each observer noticed that during his (her) minute of observation the snail has crawled exactly $1$ meter. Prove that during $6$ minutes the snail could have crawled at most $10$ meters."

I have also found a solution that reads as follows:

"We will show that if there are $n ≥ 10$ people watching, then the snail can crawl at most $n$ metres. Certainly, the snail cannot crawl further than this, since each person watches the snail crawl exactly one metre. To show that the snail can in fact crawl $n$ metres, suppose that all $n$ people watch the snail remain stationary during the first $(n − 10)/(n − 1)$ hours. After that, the n people take turn to watch the snail crawl one metre in $9/(n−1)$ hours. Then each person has watched the snail for $(n − 10)/(n − 1) + 9/(n − 1) = 1$ hour and the snail has crawled for a total of $(n − 10)/(n − 1) + 9n/(n − 1) = 10$ hours, during which it travels $n$ metres."

Can anyone help me understand the solution? First of all, the solution mentions hours, I guess the guy means "minutes", but let's disregard this. What does it have to do with people watching? What is $(n − 10)/(n − 1)$? ...and all the rest, of course!

$\endgroup$
  • $\begingroup$ i think it says for $n\geqslant 10$, snail can crawl at most 10 metres, so it doesn't matter how many $n\geqslant 10$ people watching. I think the least amount of observers equal to the most amount of metres the snail can crawl in our OP. Maximum $2(t-1)$ metres for integer $t$ $\endgroup$ – serg_1 Jun 28 '17 at 10:20
  • $\begingroup$ I still don't get it... By the way, the solution I posted was published to a magazine, so I guess it must be somewhat reasonable! $\endgroup$ – Sal.Cognato Jun 28 '17 at 21:18
  • $\begingroup$ "Each person begins to observe before the preceding observer finishes to observe..." how much before? If it could be arbitrarily before, then there it would be $\infty$ observers.. $\endgroup$ – Vitor C Goergen Jun 30 '17 at 23:22
1
$\begingroup$

I have also found a solution that reads as follows:

"... To show that the snail can in fact crawl $n$ metres, suppose that all $n$ people watch the snail remain stationary during the first $(n − 10)/(n − 1)$ hours. After that, the n people take turn to watch the snail crawl one metre in $9/(n−1)$ hours ..."

This doesn't sound like a solution to the posted problem. Those $n$ observers described in the quoted solution are not observing for one continuous minute each, but rather for two time intervals of $(n-10)/(n-1)$ and $9/(n-1)\,$, respectively, which add up to one minute, indeed, but are not contiguous. The stated problem, however, implies that each minute of observation is continuous.


Hint for the problem as posted:  say the first observer starts watching at $t_1 = 0$ and ends at $t_1+1$. By the stated condition, at least one, and possibly more than one observers will start watching no later than $t_1+1\,$. Let $t_2$ be the time when the latest of those observers starts. Then let $t_3$ be the latest time when a third observer starts watching no later than $t_2+1$. It must be that $t_3 \gt t_1+1$ otherwise the third observer would have been chosen in place of the second one. Define $t_4, \cdots t_{n}$ in a similar way, where $n$ is the number of "essential" observers after dropping redundancies. Then:

$$ t_1 \lt t_2 \le t_1+1 \lt t_3 \le t_2+1 \lt t_4 \le t_3+1 \lt \cdots \\ \cdots \lt t_{n-1} \le t_{n-2}+1 \lt t_n = 5\le t_{n-1} + 1 \lt t_n+1=6 $$

By construction, no $3$ of the $n$ intervals $[t_1,t_1+1], [t_2, t_2+1], \cdots, [t_{n}, t_{n}+1]$ have a common point. Since they are all unit length and inside $[0,6]$ it follows that $n \lt 2 \cdot 6 = 12\,$ $\,\iff n \le 11\,$.

The case $n=11$ can be eliminated by noting that it would require the $6$ disjoint intervals $[t_1,t_1+1],[t_3,t_3+1] \cdots, [t_{11},t_{11}+1]$ to fit inside $[0,6]\,$, meaning they would have to all be adjacent, but that contradicts the construction.

This leaves $n \le 10\,$, therefore the total distance is at most $10$ meters since $\le 10$ observers counted $1$ meter each during (possibly overlapping) minutes that covered the entire $6$ minute run.

The snake can attain the $10$ meter maximum, if for example the $10$ observers start each watching at 0:00, 0:20, 1:10, 1:30, 2:20, 2:40, 3:30, 3:50, 4:40, 5:00 and the snake crawls $1$ meter every time that only one of the observers is watching. In the picture below, the gray bars are the minutes each observer watched, while the snake crawled $1$ meter during each of the $10$ colored boxes.

snake


[ EDIT ] In answer to the question posted in a comment: "what if we also asked for the minimum distance crawled".

Not a full proof, but I believe that a line of reasoning similar to the above would give the minimum at $4$ meters, which can be attained for the observers laid out like the gray bars in the image below, with the snake crawling $1/2$ meter during each of the $8$ colored boxes.

snake-min

$\endgroup$
  • $\begingroup$ Thank you for your answer! Can you please clarify why we eliminate 11 and 12? Also I do not understand the last paragraph :( $\endgroup$ – Sal.Cognato Jun 30 '17 at 13:10
  • 1
    $\begingroup$ @Sal.Cognato I reworked the case $11$ and added a picture to clarify. $\endgroup$ – dxiv Jun 30 '17 at 17:01
  • $\begingroup$ I am getting closer now :) Do we have a condition saying that no two observers can watch the snail crawl simultaneously? Is this because "Each person begins to observe before the preceding observer finishes the observation and observes the snail for exactly one minute"? Also, if they were watching for, say, 20 or 30 minutes instead of 6, would it still be 10 meters? $\endgroup$ – Sal.Cognato Jul 1 '17 at 8:48
  • $\begingroup$ @Sal.Cognato There can be (an in fact there must be) multiple observers watching at the same time. But the central point of the proof is that, no matter how many observers overall, it is possible to extract a subset of $n$ observers such that the odd-numbered observers watch during minutes which do not overlap. From that, it follows that there can be at most $5$ odd-numbered observers, or $10$ total, so the max distance is $10$ meters. Then, the given example shows that this maximum is actuallly attainable. $\endgroup$ – dxiv Jul 1 '17 at 17:13
  • $\begingroup$ @Sal.Cognato If the time were $t$ minutes, instead of $6$, the same argument would show that the snake can crawl at most $2(t-1)$ meters. $\endgroup$ – dxiv Jul 1 '17 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.