Turbo the snail sits on a point on a circle with circumference 1. Given an infinite sequence of positive real numbers c1,c2,c3,…, Turbo successively crawls distances c1,c2,c3,… 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 c1,c2,c3,… with ci<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=12. If C>12, then let c be a real number in (12,C). Let ai=c for odd i and ai=12 for even i. If Turbo crawls twice in the same direction, it will travel a distance of c+12>1 in these two moves, covering the whole circle. Thus, Turbo must alternate between crawling c units in one direction and 12 units in the other direction. For any positive integer N, Turbo will move a net distance of N(c−12) 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=12, 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 12, so Turbo will never reach the point.
17.04.2023 03:25
The answer is C=12 For C=12, 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>12. Consider the following construction to guarantee every point is covered. First, start off the sequence with 12,14,12This will guarantee that turbo will have crawled across every point, except some interval T0 of length 14, and that turbo will be standing right on an endpoint of T0. Now, let the next number in the sequence be the distance from any endpoint of T0 to the antipode of the midpoint of T0. This forces Turbo to the antipode of the midpoint of T0, otherwise, he must cover T0 and, by extension, the whole circle. From here, choose some 12<α<C and make turbo move a distance of α. This reduces the size of the interval of uncovered points by exactly α−12. Let T1 be the new set of uncovered points. Then, do the exact same process we did on T0 to T1. In general we have length of Tk=14−k(α−12)which is negative for sufficiently large k. ◼
17.04.2023 14:18
17.04.2023 17:40
The answer is C=12. For C=12 Turbo simply picks an arbitrary point P (other than the starting point). Clearly at no point will the two arcs with length ci intersect, so one of them will not contain P, and Turbo will simply walk along that arc. For C>12, let n be a massive integer such that 12+12n<C. Then select the infinite sequence 12+12n,12,12+12n,12,…. 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 12n clockwise from his starting point, and after two more it will be 22n clockwise, and so on, until after 2n moves it will be n2n 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. ◼
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=12, since the strategy for C=12 outlined above clearly still works, but the problem as a whole is made weaker. However, interestingly, if C>12 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 12, 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 12 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 ci<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 N2 in a few steps and still standing on P or Q. First choose 0.5<c1<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 ci=s2 at that moment This either reduces the uncovered distance from N to less than N2 or moves Turbo to Midpoint of major arc PQ. In the latter case we can choose d>ci>0.5 which again reduces the uncovered distance to less than N2. Now from above we can reduce N to less than N2v. Choosing large enough v we have N2v to be extremely small, if the length of major arc PQ is t at this time then choose ci=t2 which either forces Turbo to complete the circle(as N2v 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>ci>0.5+N2v>0.5 (again as N2v 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=12. 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≠X and needs to crawl ci<C=12 units around, then he shall not pass through point X. A quick induction finishes. Now let's prove 12 is the best bound. Indeed, suppose FTSOC that there exists such a constant C>12. Turbo then chooses his favorite constant A such that 12<A<C, and decides to put ci=A if i is odd, and ci=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 c1,c2,…,c2k+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. ◻
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 ≥0.5. Since ci<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+ε for some ε>0 and c2k−1=0.5−ε2kandc2k=0.5+ε2kfor all sufficiently big k≥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 ≥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 c2N−1−c2N+c2N+1−c2N+2+⋯=−εN−εN+1−⋯→−∞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=12. To see why this works, let P be the starting position of Turbo, and pick an arbitrary point D≠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>12 fail. Pick some c∈(12,C). Let all ai=c for odd i and ai=12 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−12). Picking sufficiently large n gives a contradiction, as desired.
07.06.2023 17:27
The answer is C=12. 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>12 fails, consider the sequence c1,c2,c3,c4,⋯=12,12+ϵ,12,12+ϵ,…. 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>12ϵ turns.
31.08.2023 22:28
We claim the answer is C=12. First, we will prove that for any C>12, you can make Turbo hit every point on the circle. Consider a small ϵ>0 such that 12+ϵ<C, which exists since C>12. Then we can use the sequence c2k−1=12, c2k=12+ϵ 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 12+12+ϵ>1, which means it would have hit every single point. By moving in opposite directions every turn, after 2N turns Turbo will have visited 12+Nϵ of the circumference. By picking very large N Turbo will eventually visit the entire circumference. Now we will prove that for C=12 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 12. Since the cis are all <12, 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. ◼
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=12. 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 ϵ>0 such that ci=0.5+ϵ. Consider the alternating sequence 12+ϵ,12,12+ϵ,12…Given this sequence, Turbo will traverse through every point no matter what he tries. Fix A1 to be the starting point, then A2 lies outside ^A1A2. The next move will take A2 to A′2. As the sequence repeats itself, A′i will move ϵ away from Ai−1 towards direction of ^Ai−1Ai. In ⌈1ϵ⌉ 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. ◼
27.05.2024 09:16
So easy! ans C=12 and induction
21.06.2024 21:14
GOOD SOLUTİON
11.01.2025 20:40
The answer is C=12. Notice that C=12 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>12 does not work, consider an arbitrarily small ϵ such that 12+ϵ<C. Consider the alternating sequence 12,12+ϵ,12,12+ϵ,…. 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 ϵ from the other side of A as your first move. Now the process continues, this time starting at this point ϵ 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ϵ from A. Then it is clear that an arbitrarly large n will cover the entire circle, done.