I heard that the strategy for this problem was to move the circles...

We claim the number of cycles has the same parity as $n$. The circles divide the plane into regions, and we can colour the regions red and blue so that no 2 region with the same colour share a common edge (or arc). WLOG the region outside is red. Now note that Turbo will always travel with the red region on his left, and the blue region on his right. Now we colour each edge of each circle as such: if the region with that edge in the interior of the circle is red, colour the edge purple; otherwise colour it green. Now note that Turbo will always alternate between purple and greed edges. From here we can consider moving the circles, and analyse what happens when a circle moves to intersect another circle, or when it passes through an intersection. By some case whack we can show that the number of cycles remain the same modulo 2, and we are done. But we shall present an invariant proof instead. We shall start with the $n$ circles as $n$ clockwise cycles. Note that the cycles will always alternate between purple and green edges. Each time, we pick a crossing of the cycles, and uncross it in such a way that the new paths will still alternate between purple and green. After we are done with all the crossings, the final cycles are the path Turbo takes. For each edge of a cycle (with a direction), we call that edge a moonwalk if the direction of the edge has the blue region on its left and red on its right. We claim that \[\text{\#crossings}+\text{\#cycles}+\text{\#moonwalks}\pmod{2} \]is an invariant (everytime we uncross a crossing). This can be checked as depicted in my awesome illustration below. Note that direction of cycles does not matter as every cycle alternates between purple and green edges hence has even number of edges and number of moonwalks modulo 2 won't change. At the end, there will be 1 cycle and no crossings or moonwalks, so the invariance is 1. It suffices to count at the start. For each crossing, there will be 2 moonwalks with that crossing as endpoint, and each moonwalk will have 2 crossings on each endpoint. Thus number of crossings and moonwalks are the same at the start, and the invariance is $n$. And we are done.

A rather sketchy proof as I'm on mobile: As an alternate approach: Note the reversibility of the paths implying the possible decompisition of the circles into cycles. Similar to the above proof, the aim is to shift circles while showing that the parity of the number of cycles is conserved, specifically when a circle is shifted through an intersection between two other circles or when it is removed from another circle entirely. For any circle, we can find a path that removes it from the region contained within the other $n-1$ circles, such that multiple instances of the aforementioned events never occur simultaneously. The latter event, removing from another circle entirely, is quite easily seen to preserve the number of cycles. In order to do so, we consider the 4 ways 'into the junction'(I will call these things nodes) formed by the intersection between the 2 circles in question. Note that the connection between the nodes within the junction are invariant, and hence the cycles involving the junction are invariant, thus the number of cycles remains constant. For the former event, we note that the region formed by the intersection of the 3 circles in question is a triangle (of sorts), and we can consider the 6 nodes of the triangle and their connection. These nodes are connected as 3 pairs by connections outside of the junction. We note that the clockwise order of the nodes remains constant before and after the operation is performed (passing our circle through the intersection of the other 2) and that each node is connected to an adjacent node within the junction. Exactly which adjacent node it is connected to changes after the operation is performed. Note furthermore that no node may be connected to a node that's neither the other node on the same arc, nor an adjacent node, as this would connect two nodes with exactly 1 node in between. That node in between would be unable to connect with any other node without intersecting that connection. With these restrictions on the ways the nodes may connect, we can check that any external connection of the nodes that result in 2 cycles involving the junction will continue to only have 2 cycles involving the junction after the operation is performed, preserving the parity. Hence, when we delete a ring, it alternates the parity of the number of cycles. Induction finishes.

A related problem: KöMaL A.427. http://www.komal.hu/verseny/feladat.cgi?a=feladat&f=A427&l=en

joyce_tan wrote: The latter event, removing from another circle entirely, is quite easily seen to preserve the number of cycles. In order to do so, we consider the 4 ways 'into the junction'(I will call these things nodes) formed by the intersection between the 2 circles in question. Note that the connection between the nodes within the junction are invariant, and hence the cycles involving the junction are invariant, thus the number of cycles remains constant. You missed out an important case here, when one of the circle is just barely inside the other. In this case you can have 2 cycles to 2 cycles, or 1 cycle to 3.

Here is my solution (hoping it's correct!) Let's consider a generic configuration with $2k$ circumferences which intersect two by two in $2k(2k-1)$ distinct points in total (let's call $\mathfrak{P}$ the set of this points). The aim of what will follow will be to find a cycle that doesn't cover all circumferences and that Turbo can tread respecting the rule described in the text. Let's color with blue or red each region of the plane defined by the configuration of circumferences (included the infinite region around the configuration) in such a way that the infinite region is blue and adiacent regions are colored with different colors (it's well-known that we can do this). Let's call $barrier$ each not ordered couple of regions $\left(\alpha,\beta\right)$ with just a point $A$ in common ($A\in\mathfrak{P}$) and with the following property: the two circles (and not circumferences!) $\Omega$ and $\Gamma$ which intersects in $A$ are such that $\alpha\subseteq\Omega\cap\Gamma$ and $\beta\not\subseteq\Omega\cup\Gamma$. Now let's consider the graph $G$ where the verteces represent the red regions and where the two verteces associated with the red regions $\alpha$ and $\beta$ are connected by an arc iff $\left(\alpha,\beta\right)$ is a $barrier$. Lemma: $G$ is not a tree graph (hence it has cycles or it's disconnected). Thanks to Euler's formula, if we showed that $\left\vert V\right\vert\equiv\left\vert E\right\vert\pmod{2}$ (where $V$ and $E$ are the set of vertex and the set of arches in $G$ respectively) the lemma would be demonstrated. Maybe there is a cool way to show this, however here is a way maybe boring to formalize (infact the following is just a sketch) but quite direct to think. Let's consider a configuration where the $2k$ circles are with same radius and tangent to two parallel lines (and as always they intersect two by two in $2k\left(2k-1\right)$ distinct points in total). In this case thanks two the orizontal and the vertical simmetry it's evident that the number of verteces of the associated graph $G$ is pair. Besides in a similar way it's easy to see that also $\left\vert E\right\vert$ is pair. Now from this configuration we wish to reach the generic configuration with $2k$ circles by moving and dilating circles and prove that the parity of $\left\vert V\right\vert-\left\vert E\right\vert$ is constant. Evidently it suffices to prove that the parity doesn't change when the dilatation or the moving of a circle $\Omega$ exceeds a "critical point", that is when $\left\vert\Omega\cap\mathfrak{P}\right\vert$ increases (or decreases) by $1$. And this is easy (just few cases to be analyzed), infact when a critical point is exceeded almost all $G$ remains unchanged. Now thanks to the lemma it remains to analyze two cases: $1)$ $G$ has a cycle. So for definition of $G$ it's easy to note that if Turbo begins in the space delimited by the "chain" of regions which compose the cycle, then he can't go out this delimited space. $2)$ $G$ is disconnected. So it has two disjointed subgraphes $G_1$ and $G_2$. Then it's easy to note that if Turbo begins on a side of a region which is a vertex in $G_1$ then he won't be able to reach sides of regions in $G_2$, and viceversa. This should end the proof.

Can someone please provide EGMO style hints (like say 7~8 hints) to this problem ? I am desperate to solve this C9. Also, still now I have made no progress, but still my progress is like this: 1. It looks like that the number of cycles is congruent to the number of circles modulo $2$

. We can associate to each pathsegment a set $\{S, T \}$, where $S$ is the corresponding area in which the path is, and $T$ is the circle of which the path is. So for example $\{C_1C_4C_2, C_3\}$ would correspond to the segement of the circle $C_3$ which is inside the region formed by $C_1 \cap C_4 \cap C_2$. Doing this, we can clean the circle structure from the problem, but this looks very clunky.

, and then study how the coloring is affected when we add another circle to it. 4. It looks like after partioning the circles into union of cycles, we can arrange the direction of the paths in such way such that in the boundary of the entire figure, turbo always moves in anticlokcwise direction. Can someone please give some hints/etc if any of the above approaches work ?

Disclaimer: This proof might not make sense because I have no diagrams sorry... We can color the regions as follows: red if in even number of circles or blue if in odd number of circles. Likewise, similarly coller the vertices and edges. Note that Turbo alternates between red and blue edges so assume that he travels cw on red and ccw on blue. Then we see that Turbo with a blue region to his right side, red region to his left.(i.e. he travels cw around the blue regions, ccw around the red regions) First look at the blue regions, Claim: Turbo can pass from moving around a blue region to another blue region iff the 2 regions share some blue vertex. (Draw a diagram and you will see why) Assuming that Turbo covers all circles, he must go to every single region, so if we look at the graph where each blue region is a vertex, each blue vertex is an edge connecting the 2 regions, then it must be a connected component. Same thing with red regions. Let r be number of red vertices, R be number of red regions. Same with b,B. Note that r+b=R+B-2, so we must have r=R-1. b=B-1(Both graphs are trees). Thus, r+R is odd. Claim: r+R is the same parity as n. We can do this by performing induction on number of circles.(i.e. adding a circle and hope that parity of R+r flips) Note that when we add the (n+1)th circle, we add 2n vertices, 2n regions, and then we flip the color of all regions and points inside the circle. It is easy to see that the number of new red vertices is even, and number of new red regions is n. Now we just need to find the parity of the sum of total regions and vertices inside this new circle and hope that it is the opposite parity of n.(Flipping a region/vertex color changes the parity of R+r) We can show this with another induction where we start with the new circle, and inductively add the other n circles back.(Showing that each time we add another circle, it changes the parity of the sum of the number of regions and vertices in the (n+1)th circle) When the add an old circle back, the number of regions added is 1 more than the number of vertices add, so the sum must be odd. Thus, the sum of the number of regions + vertices in the (n+1)th circle flips every time, so it must have the opposite parity of n. Thus, if n is even, R+r is even so r cannot be R-1. @Below: sorry

pandadude wrote: Disclaimer: This proof might not make sense because I have no diagrams sorry... We can color the regions as follows: red if in even number of circles or blue if in odd number of circles. Likewise, similarly coller the vertices and edges. Note that Turbo alternates between red and blue edges so assume that he travels cw on red and ccw on blue. Then we see that Turbo with a blue region to his right side, red region to his left.(i.e. he travels cw around the blue regions, ccw around the red regions) First look at the blue regions, note that Turbo can pass from moving around a blue region to another blue region iff the 2 regions share some blue vertex. So if we look at the graph where each blue region is a vertex, each blue vertex is an edge connecting the 2 regions, then it must be a connected component. Same thing with red regions. Let r be number of red vertices, R be number of red regions. Same with b,B. Note that r+b=R+B-2, so we must have r=R-1. b=B-1. Thus, r+R is odd. So now we just need to show that r+R is the same parity as n. We can do this by performing induction on number of circles.(i.e. adding a circle and hope that parity of R+r flips) Note that when we add the (n+1)th circle, we add 2n vertices, 2n regions, and then we flip the color of all regions and points inside the circle. It is easy to see that the number of new red vertices is even, and number of new red regions is n. Now we just need to find the parity of the sum of total regions and vertices inside this new circle and hope that it is the opposite parity of n.(Flipping a region/vertex color changes the parity of R+r) We can show this with another induction where we start with the new circle, and inductively add the other n circles back.(Showing that each time we add another circle, it changes the parity of the sum of the number of regions and vertices in the (n+1)th circle) When the add an old circle back, the number of regions added is 1 more than the number of vertices add, so the sum must be odd. Thus, the sum of the number of regions + vertices in the (n+1)th circle flips every time, so it must have the opposite parity of n. Thus, if n is even, R+r is even so r cannot be R-1. Please write in paragraphs. A long paragraph often makes understanding unnecessarily hard, especially an explanation lacking images.

Let $G$ be a directed graph (with doubled edges allowed) so that every vertex in $G$ has indegree and outdegree both equal to two. We define a journey to be a partition of the edges into a bunch of cycles. We note that a journey can be thought of as a series of joints, or triples $a\to b\to c$ so that $a,b,c$ appear in that order in a cycle. (Technically, we should think about this as $u\to b\to v$ where $u,v$ are edges ending and beginning at $b$, but is should be pretty clear what's going on). We define a swap at a vertex $u$ to be the following operation: If in our original journey our cycles contained $a\to u \to b$ and $c\to u \to d$, then these joints with $a\to u\to d$ and $c\to u\to b$ (while preserving the other joints). It's clear that a swap toggles the number of cycles modulo $2$. Define an edge to be an arc of a circle between two consecutive turns. Note (say, by black/white coloring regions) that if Turbo's path covers all circles, then the path is an Eulerian tour and therefore induces such a graph $G$ as described above. Furthermore, we note that both in-edges (resp. out-edges) adjacent a vertex $u$ lie on the same circle. So, if we perform a toggle at every vertex, then since we have $2\binom n2$ (even) vertices, the number of cycles is still odd. But now, we see that Turbo's path turns into a bunch of cycles, on each of which he preserves orientation (i.e. goes from clockwise to clockwise, etc.). The final step is to orient the cycles (i.e. flip the direction of the edges) so that all cycles are clockwise. Then, applying swaps at every vertex (so that the number of cycles is still odd) makes it so that the cycles are precisely the $n$ circles, hence $n$ is odd. $\blacksquare$

Replace every intersection of circles by two arcs, indicating the direction of moving. We obtain several simple closed curves, which are possible paths of snail. Now define for circles analogue of Reidemeister moves type $2,3$ as on the first picture (circle intersect other circle without passing through cross of two circles, and circle passes through such cross). By considering all possible positions of arcs (in small enough neighborhood) one may see, that second type changes number of curves by $0$ or $\pm 2$ (second picture, dashed line shows curve path outside of considering neighborhood). In third type we work with some region formed by three arcs - all possible cases are on the picture $3.$ We can now consider only one kind of arcs in given neighborhood, which clearly has only two possible reciprocal pairs of ways to close the curves (picture $4$). Thus third type changes number of curves by $0$ or $\pm 2$. Now move all circles in such way, that they don't intersect in pair. Then $n$ has the same parity, as the number of curves in this configuration. The conclusion follows.

If you try some small examples, you'll have the feeling that the snail is just traversing around some area. And it's also fairly easy to come up with a graph that shows the original problem is not the best condition.