Turbo the snail sits on a point on a circle with circumference $1$. Given an infinite sequence of positive real numbers $c_1, c_2, c_3, \dots$, Turbo successively crawls distances $c_1, c_2, c_3, \dots$ around the circle, each time choosing to crawl either clockwise or counterclockwise. Determine the largest constant $C > 0$ with the following property: for every sequence of positive real numbers $c_1, c_2, c_3, \dots$ with $c_i < C$ for all $i$, Turbo can (after studying the sequence) ensure that there is some point on the circle that it will never visit or crawl across.
Problem
Source: EGMO 2023/4
Tags: EGMO 2023, EGMO, combinatorics, game, ilostthegame
17.04.2023 01:01
We claim that $C=\tfrac{1}{2}$. If $C>\tfrac{1}{2}$, then let $c$ be a real number in $(\tfrac{1}{2},C)$. Let $a_i=c$ for odd $i$ and $a_i=\tfrac{1}{2}$ for even $i$. If Turbo crawls twice in the same direction, it will travel a distance of $c+\tfrac{1}{2}>1$ in these two moves, covering the whole circle. Thus, Turbo must alternate between crawling $c$ units in one direction and $\tfrac{1}{2}$ units in the other direction. For any positive integer $N$, Turbo will move a net distance of $N(c-\tfrac{1}{2})$ units after $2N$ moves. Let $N$ be sufficiently large so that the net distance Turbo travels in this direction is more than $1$. This means Turbo visits all points on the circle, a contradiction. If $C=\tfrac{1}{2}$, then Turbo can choose a point $A$ on the circle other than its starting position and always walk in the direction away from it. The distance Turbo needs to walk to reach $A$ at each move is at least $\tfrac{1}{2}$, so Turbo will never reach the point.
17.04.2023 03:25
The answer is $C= \frac{1}{2}$ For $C= \frac{1}{2}$, consider the following strategy for Turbo. Choose an arbitrary point $X$ (which is not Turbo's starting point), and always jump in the direction of $Y$ which is the antipode of $X$. Indeed, this strategy works by induction. Now, assume $C > \frac{1}{2}$. Consider the following construction to guarantee every point is covered. First, start off the sequence with \[\frac{1}{2}, \frac{1}{4}, \frac{1}{2}\]This will guarantee that turbo will have crawled across every point, except some interval $T_0$ of length $\frac{1}{4}$, and that turbo will be standing right on an endpoint of $T_0$. Now, let the next number in the sequence be the distance from any endpoint of $T_0$ to the antipode of the midpoint of $T_0$. This forces Turbo to the antipode of the midpoint of $T_0$, otherwise, he must cover $T_0$ and, by extension, the whole circle. From here, choose some $\frac{1}{2} < \alpha < C$ and make turbo move a distance of $\alpha$. This reduces the size of the interval of uncovered points by exactly $\alpha-\frac{1}{2}$. Let $T_1$ be the new set of uncovered points. Then, do the exact same process we did on $T_0$ to $T_1$. In general we have \[ \text{length of }T_k = \frac{1}{4} - k \left ( \alpha - \frac{1}{2} \right ) \]which is negative for sufficiently large $k$. $\blacksquare$
17.04.2023 14:18
17.04.2023 17:40
The answer is $C=\tfrac{1}{2}$. For $C=\tfrac{1}{2}$ Turbo simply picks an arbitrary point $P$ (other than the starting point). Clearly at no point will the two arcs with length $c_i$ intersect, so one of them will not contain $P$, and Turbo will simply walk along that arc. For $C>\tfrac{1}{2}$, let $n$ be a massive integer such that $\tfrac{1}{2}+\tfrac{1}{2n}<C$. Then select the infinite sequence $\tfrac{1}{2}+\tfrac{1}{2n},\tfrac{1}{2},\tfrac{1}{2}+\tfrac{1}{2n},\tfrac{1}{2},\ldots$. Let turbo start at point $P$. If at any point Turbo elects to make two moves in the same direction then it will clearly move through every point on the circumference of the triangle, so it must alternate directions. WLOG let the first move be counterclockwise, so then after the second move it is $\tfrac{1}{2n}$ clockwise from his starting point, and after two more it will be $\tfrac{2}{2n}$ clockwise, and so on, until after $2n$ moves it will be $\tfrac{n}{2n}$ clockwise, i.e. at the antipode $P'$. It is clear that in his next move, Turbo will visit the clockwise semicircular arc "starting" at $P'$. Furthermore,Turbo visits the clockwise semicircular arc "starting" at $P$ in his first move, so he will visit every point along the circumference, as desired. $\blacksquare$
17.04.2023 17:50
By the way, if we horribly misread and then misremember the question as Stating that instead of not covering some point on the circle, there is a specific point $P$ on the circle (determined before everything else) that Turbo wishes to avoid Stating that the sequence is chosen after Turbo picks his starting position then the answer is still $C=\tfrac{1}{2}$, since the strategy for $C=\tfrac{1}{2}$ outlined above clearly still works, but the problem as a whole is made weaker. However, interestingly, if $C>\tfrac{1}{2}$ then we only need three terms of the sequence (possibly less) to make Turbo visit $P$. Let $P'$ be the antipode of $P$. If Turbo starts closer to $P'$ than $P$, first instruct it to move $\tfrac{1}{2}$, so now they're at least as close to $P$ as $P'$. Then make Turbo move a distance equal to that between its current position and $P'$ (measured along the minor arc): clearly it must end up on $P'$, else it moves through $P$. Then make Turbo move $\tfrac{1}{2}$ again, so it ends up on $P$.
17.04.2023 20:17
Sol:-We prove that largest $C=0.5$. Step 1 Proving $C=0.5$ works Proof Let $D$ be the initial point on the circle at which turbo stands and $D'$ be its antipode.$DD'$ divides the circle into $2$ semicircles. Let the left one be $k$ , right one be $j$ as shown in the diagram. If Turbo moves according to the following $3$ rules he ensures that he never reaches $D'$. (i)When Turbo stands on $D$ he can either move clockwise or anticlockwise. (ii)When Turbo stands on any point on $k$ other than $D$ he moves clockwise. (iii)When Turbo stands on any point on $j$ other than $D$ he moves anticlockwise. Since all $c_i<0.5$ the above rules indeed ensure that Turbo never reaches $D'$. Step 2 Proving $d=C>0.5$ doesn't work. Proof:- Let $N>0$ denote the length of distance still not covered by Turbo at some time. Let $P,Q$ be variable points separating the uncovered distance from covered distance. We first prove that we can reduce the uncovered distance from $N$ to less than $\frac{N}{2}$ in a few steps and still standing on $P$ or $Q$. First choose $0.5<c_1<d$ this covers more than half of the circle (forming major arc $PQ$).Now at any time when Turbo is on $P$ or $Q$ if $s$ the length of the major arc $PQ$ choose $c_i=\frac{s}{2}$ at that moment This either reduces the uncovered distance from $N$ to less than $\frac{N}{2}$ or moves Turbo to Midpoint of major arc $PQ$. In the latter case we can choose $d>c_i>0.5$ which again reduces the uncovered distance to less than $\frac{N}{2}$. Now from above we can reduce $N$ to less than $\frac{N}{2^v}$. Choosing large enough $v$ we have $\frac{N}{2^v}$ to be extremely small, if the length of major arc $PQ$ is $t$ at this time then choose $c_i=\frac{t}{2}$ which either forces Turbo to complete the circle(as $\frac{N}{2^v}$ can be made as small as we want) or makes him to move at the midpoint of major arc $PQ$.At this time u choose $d>c_i>0.5+\frac{N}{2^v}>0.5$ (again as $\frac{N}{2^v}$ can be made as small as we want) which forces Turbo to complete the circle.So we are done
17.04.2023 22:00
Let us prove that the largest constant is $C=\frac{1}{2}$. This is indeed works, because Turbo can simply follow this strategy : - He chooses a point $X$ different from the point he's sitting on at the beginning. He then rotates the circle so that $X$ lies on top, and he draws the diameter passing through $X$ ; -Then, from now on, if Turbo lies on a point $P$ in the left "half" of the circle, he hops towards the right half from the bottom (i.e. counterclockwise). Similarly, if he lies on a point in the right half, he hops clockwise around the circle. Finally, if he lies on the antipode of $X$, he flips a coin to decide whether he's going clockwise or counterclockwise. This way, if Turbo lies on a point $P\ne X$ and needs to crawl $c_i<C=\frac{1}{2}$ units around, then he shall not pass through point $X$. A quick induction finishes. Now let's prove $\frac{1}{2}$ is the best bound. Indeed, suppose FTSOC that there exists such a constant $C>\frac{1}{2}$. Turbo then chooses his favorite constant $A$ such that $\frac{1}{2}<A<C$, and decides to put $c_i=A$ if $i$ is odd, and $c_i=1-A$ otherwise (note that we indeed have $A,1-A<C$ by construction). This way, he will never make two consecutive crawls in the same direction, because if he did then he would crawl $A+1-A=1$ unit around the circle, i.e. he would pass through every single point of the circle. It follows that after the first crawl he has travelled a distance of $A$ units, then after the third crawl he travelled a distance of $(A-(1-A)+A)=A+(2A-1)$, then right after the fifth crawl he has travelled in total a distance of $A-(1-A)+A-(1-A)+A=A+2(2A-1)$,... By induction, we get that he crawled a distance of $A+k(2A-1)$ in total during the crawls $c_1,c_2,\ldots,c_{2k+1}$. For $k$ large enough this implies that he crawled a distance $>1$, i.e. he passed through every point on the circle, a contradiction. $\square$
18.04.2023 10:03
This is an easier version of Serbian MO P2 from 2019.
22.04.2023 02:22
If $C = 0.5$, then Turbo can choose any point $X$ on the circle other that the one it starts and guarantee not to visit this point. To see why, note that before each move one of Turbo's two paths to $X$ along the circle $ \geq 0.5$. Since $c_i < 0.5$, Turbo can always take the longer path and not visit $X$ at any time. If $C > 0.5$, then let $C = 0.5 + \varepsilon$ for some $\varepsilon > 0$ and $$c_{2k - 1} = 0.5 - \frac{\varepsilon}{2k} \quad \text{and} \quad c_{2k} = 0.5 + \frac{\varepsilon}{2k}$$for all sufficiently big $k \geq N$ where $N$ is chosen so that all these numbers are positive. Note that the the sum of any two consecutive numbers in this list $\geq 1$. So any two crawls on the same direction would make full circle and visit all points. But if any two consecutive craws are on the opposite direction, then after move $2N-1$ Turbo will travel $$c_{2N - 1} - c_{2N} + c_{2N + 1} - c_{2N + 2} + \cdots = -\frac{\varepsilon}{N} - \frac{\varepsilon}{N + 1} - \dots \to -\infty$$which means he will make full circle again. So any $C > 0.5$ does not work.
12.05.2023 09:08
The answer is $C=\tfrac{1}{2}.$ To see why this works, let $P$ be the starting position of Turbo, and pick an arbitrary point $D \neq P$ on the circumference of the circle. Let $D'$ be the antipode of $D.$ Plot the circle onto the coordinate plane such that $DD'$ aligns with the $y$-axis, with the $y$-coordinate of $D$ being greater than $D'.$ If Turbo's position is right of $DD',$ then it moves clockwise, and if Turbo's position is left of $DD',$ then it moves counterclockwise. This guarantees Turbo to never reach point $D.$ We now show all $C> \tfrac{1}{2}$ fail. Pick some $c \in (\tfrac{1}{2}, C).$ Let all $a_i=c$ for odd $i$ and $a_i=\tfrac12$ for even $i.$ Observe that if Turbo moves in the same direction two moves in a row, it traverses over the entire circle. Thus, to avoid some point on the circle that it will never visit or crawl across every other move must be in opposing directions. Observe that after $2n$ turns, Turbo traverses a distance of $n(c-\tfrac{1}{2}).$ Picking sufficiently large $n$ gives a contradiction, as desired.
07.06.2023 17:27
The answer is $C=\frac{1}{2}$. To see that this is possible, simply note that Turbo can always choose a direction so to not cross the point diametrically opposite to his starting point. To see that $C>\frac{1}{2}$ fails, consider the sequence $c_1, c_2, c_3, c_4, \dots = \frac{1}{2}, \frac{1}{2}+\epsilon, \frac{1}{2}, \frac{1}{2}+\epsilon, \dots$. It is clear that Turbo cannot go in the same direction in two consecutive rows without losing; however, if he keeps alternating, he will also lose, after $N>\frac{1}{2\epsilon}$ turns.
31.08.2023 22:28
We claim the answer is $C=\frac{1}{2}$. First, we will prove that for any $C > \frac{1}{2}$, you can make Turbo hit every point on the circle. Consider a small $\epsilon > 0$ such that $\frac{1}{2}+\epsilon < C$, which exists since $C> \frac{1}{2}$. Then we can use the sequence $c_{2k-1}=\frac{1}{2}$, $c_{2k}=\frac{1}{2}+\epsilon$ for $k$ in the positive integers. Turbo must go in a different direction at each turn, because if it did two turns in the same direction then it would have travelled $\frac{1}{2}+\frac{1}{2}+\epsilon > 1$, which means it would have hit every single point. By moving in opposite directions every turn, after $2N$ turns Turbo will have visited $\frac{1}{2}+N\epsilon$ of the circumference. By picking very large $N$ Turbo will eventually visit the entire circumference. Now we will prove that for $C=\frac{1}{2}$ Turbo can ensure there is a point he never hits. Pick an arbitrary point on the circle. No matter where Turbo is on the circle, he will have a minor arc and a major arc to that point. The major arc is guaranteed to have length at least $\frac{1}{2}$. Since the $c_i$s are all $< \frac{1}{2}$, by travelling on the major arc Turbo will not hit that point. Therefore, he can simply travel on the major arc from his current location to the point and he will never hit it. $\blacksquare$
13.01.2024 18:16
Okay I did in April, 2023. But I never wrote it... I've written it, and I feel it should be correct? Solution: The answer is $C = \frac{1}{2}$. As a regular proof style, we first show it works and then prove it is the only possible solution. For any point $X$ on circle, $X'$ will denote its antipode. Every referred arc is a directed arc in the solution. We first show $C > 0.5$ fails. In this case, there clearly is some $\epsilon > 0$ such that $c_i = 0.5 + \epsilon$. Consider the alternating sequence \[\frac{1}{2} + \epsilon, \frac{1}{2}, \frac{1}{2} + \epsilon, \frac{1}{2} \ldots \]Given this sequence, Turbo will traverse through every point no matter what he tries. Fix $A_1$ to be the starting point, then $A_2$ lies outside $\widehat{A_1A_2}$. The next move will take $A_2$ to $A_2'$. As the sequence repeats itself, $A_{i}'$ will move $\epsilon$ away from $A_{i-1}$ towards direction of $\widehat{A_{i-1}A_i}$. In $\left\lceil \frac{1}{\epsilon} \right\rceil$ moves, Turbo would have covered the circle. It is time to show that $C < 0.5$ works. This is easier. Every time you hit a number in the sequence where going in either direction(clockwise or counterclockwise) would lead to traversing the full circle, turn around in the other direction. This works since this time turning around the other direction won't cover the entire circle since half rotations are not allowed. $\blacksquare$
27.05.2024 09:16
So easy! ans $C=\frac{1}{2}$ and induction
21.06.2024 21:14
GOOD SOLUTÄ°ON
11.01.2025 20:40
The answer is $C = \boxed{\frac12}$. Notice that $C = \frac12$ works because there never exists a time where Turbo is forced to go to the antipode of his starting point. There always exists a direction in which he can travel away from it. To show $C > \frac12$ does not work, consider an arbitrarily small $\epsilon$ such that $\frac12 + \epsilon < C$. Consider the alternating sequence $\frac12, \frac12 + \epsilon, \frac12, \frac12 + \epsilon, \dots$. Let the starting point be $A$. The first move brings you to the antipode. The second move then must either complete the circle as desired or bring you a distance $\epsilon$ from the other side of $A$ as your first move. Now the process continues, this time starting at this point $\epsilon$ from $A$. Turbo will keep oscillating back and forth, and it is clear that after $2n$ moves if he keeps avoiding completeing the circle, he will be a distance $n \epsilon$ from $A$. Then it is clear that an arbitrarly large $n$ will cover the entire circle, done.