Proposed by Tejaswi Navilarekallu, also the author of the infamous turbo snail problem, a big oops

+) South Korean TST #6 Can be solved by some observations of circles, and little double-counting

Comment: This is a really hard problem but, the idea comes from basic observation, which is the main lemma. Honestly, I think this problem is easier than other C7.

Another way to get the idea of the 2 disjoint cliques: Note that we can toggle the circles s.t. all points are yellow. With a little help from the coloring scheme from 2014 C9, color a vertex orange if in even number of circles, and purple in in odd number of circles. Now look at a circle, the other circles will intersect this circle at 2 points, so we define an interval on the circle as an arc that is inside another circle. Thus, each vertex on this circle is either at the clockwise endpoint of an interval(Start from a point inside the interval and travel clockwise until reach an endpoint), or a counterclockwise endpoint of an interval. If a vertex is orange, and on clockwise endpoint, color this vertex red. If a vertex is purple, and on counterclockwise endpoint, color this vertex red. Otherwise color this vertex blue. It is easy to see that this works by inducting on the number of circles. Also, if a vertex is on a counterclockwise endpoint with respect to 1 circle it is on, then it is on a clockwise endpoint with respect to the other circle. Thus, all points are yellow. Then do the flippy thingy and you get the 2 cliques. Also, I did a dumb thing with the double counting, if we have k>=1032 red circles, 2018-k blue circles. We have $k^2-k+2$ regions defined by red circles, the blue circles must break all the red regions without forming a blue region inside any red region. Thus, given any red region, the number of blue intersections inside this region is 1 less than the number of blue circles going through this region. So $2k(2018-k)-2 \binom{2018-k}{2}>=k^2-k+2$. This turns out to be exactly the same as the equations above.

OMG. Actually solved! Consider a pair of circles. Call the area enclosed by both their hug. Any circle must obviously enter the hug and exit it an equal number of times. By parity, this means any pair of circles either has two yellow vertices or none. Consider a triplet of circles. Call the area enclosed by all three the heart. Any circle must obviously enter the heart and exit it an equal number of times. By parity, this means the heart must have three yellow vertices or one yellow vertex. Now draw the graph connecting any two yellow-hugged circles. By the heart, yellow-hugging is an equivalence relation, so if one circle has 2061 yellow points, it hugs 1031 other circles. Hence 1032 circles are all mutually yellow. 986 other circles are not necessarily in this clique. It is well known that such a graph must be a union of two disjoint cliques. Therefore at least 1032 circles lie in a clique, and all the remaining circles lie in a clique. Thus there are at most $1032 \cdot 986 = 1017552$ non-yellow pairs. Now within a region, by traveling on the outer edge, a non-yellows vertex can only occur if the two intersecting circles are in opposite cliques, so by parity, there must be at least two non-yellow edges in a region if there are any. Each non-yellow pair creates two non-yellow vertices, which each creates at most four non-yellow vertex-region pairs. Hence there are at most $8 \cdot 1017552 = 8140416$ non-yellow vertex-region pairs. However, every region requires at least two vertex-region pairs, and by simply inducting on the number of regions using the fact that each new circle adds a number of regions at least equal to the number of intersections it creates, the total number of finite regions is at least $2018^2-2018+1 = 4070307$. If every region has a non-yellow vertex, then the total number of non-yellow vertex-region pairs is at least $2 \cdot 4070307 = 8140614$. This is a contradiction since we have at most $8140416$ non-yellow vertex-region pairs, so we are done.

Replace $2018$ with $n$ for convenience. Consider the graph with vertices as the vertices in the problem and draw an edge if there's a arc connecting them not passing through any other vertices. Consider any cycle in the graph and define a yellow flip to be a vertex $v$ which is part of the cycle, yellow and such that if the cycle is of the form $\cdots avb \cdots$, then $av$ and $bv$ are arcs of different circles. The main claim is the following: Claim: In any cycle, the number of yellow flips has the same parity as the length of the cycle. Proof: Suppose we're currently on a red vertex, next we alternate colors to blue, unless its a yellow flip. Since eventually we must return back to red, considering parities proves the claim. $\square$ Let every vertex not colored yellow be colored black. Note that in every region, if we travel along its boundary, every time, we switch circles, and therefore yellow flip is equivalent to yellow vertex in this case. This means the number of yellow vertices in a region is the same parity as the number of vertices in it, which means there are an even number of black vertices. If the problem is false, then every region has a nonzero number of black vertices and so at least $2$. Observe that every vertex is part of exactly $4$ regions. Say there are $B$ black vertices and $R$ regions. Count the number of pairs $(R,v)$ where $v$ is a black vertex of region $R$, it is at least $2R$ by the above statement. But on the other hand, it is also exactly $4B$, which gives us that $4B \ge 2R \implies B \ge \frac{R}{2}$. Now, see that our graph is a planar graph with $2 \binom{n}{2} = n(n-1)$ vertices and since all of them have degree $4$, we have $2n(n-1)$ edges. By Euler's formula for planar graphs $F+V-E = 2$, we have that there must be exactly $E+2-V = 2n(n-1) + 2 - n(n-1) = n(n-1) + 2$ regions. Therefore we have that $B \ge \frac{n^2 - n + 2}{2} = 2035154$. Consider the intersections of two circles (Say $X,Y$) and a cycle that starts at one intersection, travels along the arc of one circle, reaches the other intersection and then returns back through the other circle. See that every other circle intersects these two arcs the same number of times mod $2$ and therefore the cycle length is even. This means (since the only possible yellow flips are at $X,Y$) that either both $X,Y$ are yellow or both black. Now consider a new graph $G$ with circles as vertices and an edge if both of them have their intersection yellow. The problem tells us that there is a circle with degree at least $1031$. Suppose two circles $C_1, C_2$ are connected by an edge to $C_3$. Let $A = C_1 \cap C_2, B = C_2 \cap C_3, C = C_1 \cap C_3$ (consider the intersections closest to the "middle" of all the circles). Look at a cycle $A \rightarrow B \rightarrow C$, by similar reasoning as above, we have that the cycle length is odd and so an odd number of $A,B,C$ are yellow but since $B,C$ are yellow, $A$ must be too. Therefore, the graph is a union of disjoint cliques. Suppose there were at least three cliques, then select a circle from each of them and their intersection has $0$ yellow points, which is impossible since it has to be odd. This means there are two cliques, and the problem says one of them has size at least $1032$ So, the number of yellow edges is at least $\binom{1032}{2} + \binom{986}{2} = 1017601$ and so at least $2 \times 1017601 = 2035202$ yellow points. But since there were at least $2035154$ black points, we have that there are at least $4070356 > 4070306 = 2 \binom{2018}{2}$ vertices, which is a contradiction. We're done. $\blacksquare$

Note that, since the area enclosed by the intersection of two circles is closed, any two circles either have 0 or 2 yellow intersections as each arc must "enter" and "exit" the area. Now, suppose that circles $\omega_1,\omega_2,\omega_3$ intersect at points $A,B,C$, and call the region formed by arcs $AB,AC,BC$ an arcangle. Claim: Each arcangle has either $1$ or $3$ yellow vertices. Proof: We will proceed with induction on $n$, the number of circles that intersect the arcangle. The base case $n=0$ is obvious. For the inductive step, each additional circle intersects an arcangle at an even number of points (as, again, the arcangle is closed). Then, if the circles intersects an arc only once (intersecting an arc twice won't change the colors of $A,B$ or $C$), it will intersect another arc only once (assume WLOG that they are arcs $AB, AC$). The color of $A$ would be toggled in both circles that pass through it, hence A can't become yellow, or become non-yellow afterward. Now, consider the graph $G$ on $2018$ nodes formed by the $2018$ circles, such that there is an edge between two circles iff they intersect in yellow. The graph can have at most $2$ connected components, as else if we pick a node each from $3$ different connected components, any arcangle formed by them has no yellow vertices, contradiction. Also, if a connected component has any node $X$ not adjacent to another node $Y$ in the connected component, then along a path from $X$ to $Y$, consider the first node $Z$ that $X$ isn't adjacent to, and suppose the path moves from $W$ to $Z$. Then, any arcangle formed by nodes $X,W,Z$ has two yellow vertices, contradiction. Hence, $G$ consists of two cliques. We know that there are $2018^2-2018+1=4070307$ regions in total (by, say, induction). Each polygon formed by arc segments must contain either zero or at least two non-yellow vertices, since in the latter case, it contains circles from both cliques, and arcs belonging to circles in different cliques would intersect at least twice. Suppose that the cliques have size $r$ and $2018-r$ with $r\ge 1009$; the condition we're given is equivalent to a node in $G$ having degree at least $1031$, or $r\ge 1032$. There are a total of $2r(2018-r)$ non-yellow vertices, and each vertex is a part of $4$ regions, hence there are at most $\frac{2r(2018-r)\cdot 4}{2}\le 4\cdot 1032\cdot 986=4070208<4070307$ regions containing non-yellow points.

In what follows, let $n=2018$. Denote $G$ by the graph over all circles where two circles in $G$ are connected iff at least one intersection is yellow. To understand this better, we prove the following lemma. Lemma: The number of yellow points on the circumference of the face $F$ inside all of the distinct circles $\omega_1, \ldots, \omega_k$ for $k=2, 3$ has the same parity as $k$. Proof. Let an arbitrary circle $\omega$ intersect $F$ at points $v_1, \ldots, v_i$ in clockwise order, and draw an arrow from $v_m$ to $v_{m+1}$ along the arc between those points for each $m$. Color an arrow light green if it is inside $F$ and dark green if it is outside $F$. The key idea is that the color of the arrows alternate. Therefore we are done by parity reasons. Now we can characterize $G$ in the following two claims. Claim: Each connected component of $G$ is complete. Proof. This is equivalent to showing that if $\omega_1$ and $\omega_2$ have both intersection points yellow, and if the same applies to $\omega_1$ and $\omega_3$, then $\omega_2$ and $\omega_3$ have both intersection points yellow. However, this is clear by the $k=2$ case of the lemma. Claim: $G$ has at most two disjoint connected components. Proof. An equivalent formulation of this claim is to show that at most $2$ circles can have both intersections not yellow. Assume for contradiction that there are three circles such that there pairwise intersections are non-yellow colors. By the $k=3$ case of the lemma, this is impossible, and we are done. Assume for contradiction that there is no circle through at least $2061$ yellow vertices. By Euler's formula, the number of faces is at least $n^2-n+2$. Let $G = K_a \: \sqcup \: K_{n-a}$, so that the number of non-yellow vertices is exactly $a(n-a)$. We double count the number of ordered pairs $(v, F)$ of vertices and faces where $v$ lies on $F$. Note that the number of such pairs for fixed $v$ is at most $4$, and the number of such pairs for fixed $F$ is at least $2$. Thus, \[ 4(a(n-a)) > 2(n^2-n+2), \]but noting that $a < \lceil \tfrac{2061}{2} \rceil = 1031$, it follows that \[ 4 \cdot 1030 \cdot 988 > 2(2018^2-2018+2), \]which is absurd. Hence we are done.

Weird! This is a global argument. Sorry for no diagrams, I don't want to learn asy. Here are some claims that I'll use for the main computation. You can convince yourself of these pretty easily by drawing a few pictures. 1. If two circles intersect at a yellow point, both intersections are yellow. 2. Any face has an even number of non-yellow vertices Now call a circle "yellow" if it intersects the main circle (the one with $2061$ yellow points) at a yellow point, and green otherwise. We also have the following three claims. 3. Any two yellow circles intersect at a yellow point 4. Any two green circles intersect at a yellow point 5. Every point is part of $4$ faces. We can calculate with Euler's Formula that the total number of faces is $2+E-V=2+4034\cdot 2018-2018\cdot2017=2+2018\cdot 2017$. If the problem statement is false, then there are at least $4+2(2018)(2017)$ non-yellow vertices on faces (2 for each face), except for the fact that this quadruple counts (because each vertex is on $4$ faces). This means that there are at least $1+{{2018}\choose {2}}$ non-yellow vertices. By the problem statement, there are at least $1031$ yellow circles and $986$ green circles. Let the exact numbers be $y$ and $g$. Then the total number of yellow points is at least $2062+2{{y}\choose{2}}+2{{g}\choose{2}}$. By Jensen this is at least $2062+2{{1031}\choose{2}}+2{{986}\choose{2}}$. Comparing this with the bound from earlier, we get a contradiction. Remark: In general, I think the $2061$ should be replaced with about $n+\sqrt{n}$ for this argument to work. Onto G shortlist :skull:. Expecting lots of bashes.

DAYUM THIS PROBLEM IS BEAUTIFUL, hint 40\% helped EXTENSIVELY though ``and if i could solve a single problem, that was considered a successful day. but i am constantly amazed by the students who have much better work ethic than I do'' (evanchen.cc, lightly edited). this certainly applies to me, rip trying to do 6.5 hrs of math on weekend per day and 4.5 per weekday Let red=1, blue=0, and yellow happens when the sum of it's \emph{coordinates} (x,y) that represent the colors sum to odd. For obvious parity reasons remark that in any $m\ge2$-curve-gon, the number of other points on the arcs the m-gon subtends is even (call these points \emph{irrelevant}), so $$\text{no. of yellow points}\equiv\sum_{\text{m coordinates}}\equiv m+\sum_{\text{irrelevant}}\equiv m\pmod 2$$since irrelevant sum is 2m-irrelevant reds/blues which is even due to even number of intersections with m-gon; equivalently number of NON yellow points is even. In fact, observe that [*]If every face has at least one non-yellow vertex, then there are at least $\binom n2 + 1$ non-yellow vertices; this follows from computing $$F=E-V+2=2-2\binom n2+2n(n-1)=n(n-1)+2$$combined with our remark implying each face has at least two non-yellow vertices, and every vertex only contributes in four faces, double counting finishes. [*]If some circle $\omega$ has $k$ yellow vertices, then $k$ is even and the entire picture has at least $k + 2 \binom{k/2}{2} + 2\binom{n-1-k/2}{2}$ yellow vertices; this follows from the remark on m=2 and casework on if a pair of points is both yellow points or both non-yellow points with the remark on m=3 (so that any two circles that each have double yellow or any two that each have double non-yellow have two pairwise yellow). The problem is now evident, as if FTSOC every face had at least 1 non-yellow, then computing \[ 2\binom n2 \ge \binom n2 + 1+ k + 2 \binom{k/2}{2} + 2\binom{n-1-k/2}{2} \]gives a contradiction for $n = 2018$ and $k \ge 2062$ (since $k$ is even). $\textbf{Remark}$ [Motivational and for completeness]. Unfortunately again, I didn't spend enough time really ``digesting'' the problem statement, and turned to hints too quickly. Had I spent longer, I think I would've came up with some thinking as follows: We should prove a relationship between total no. of points with lower bound on no. of yellow and non-yellow; this helps us investigate the no. of yellow vertices per an m-gon. From there it was easy to gain momentum, especially the fact that 2018 is not special so we should generalize. can someone tetll me how to do those bullet point itemize thingies? i never understodd that

A truly remarkable problem! It is probably my hardest combo problem I've ever solved. We begin with some basic observations. Claim 1: Consider any two circles. If one of their intersection is yellow, the other intersection is yellow. Proof. Call the area enclosed by both of two circles their coverage. Then any circle enter the coverage and exit the coverage equally, so by parity reasons, the other intersection must be yellow. $\blacksquare$ Claim 2: For any three distinct circles, there are exactly $2$ or $6$ yellow points in their $6$ intersection points. Proof. Let $\omega_1, \omega_2, \omega_3$ be the our three circles and let $x, y, z$ be the circular arcs of $\omega_1, \omega_2, \omega_3$. Since every circle other that $\omega_i$ must intersect the cycle $x \cup y \cup z$ even number of times, so erasing it doesn't change the parity of yellow points in cycle $x \cup y \cup z$. Thus, we may assume that there are only $\omega_1, \omega_2, \omega_3$ in the plane. If there are only three circles in the plane, one can check that there are $2$ or $6$ yellow points. $\blacksquare$ Now we will show that there is a region whose vertices are all yellow. Let $G$ be a graph on 2018 circles, and we'll connect 2 vertices in $G$ if and only if two circle representing two vertices in $G$ intersect each other with yellow point. By Claim 2, it's clear that $G$ is the union of 2 complete graph. Since there is a circle that has at least $2061$ yellow points, so one of the components in $G$ has at least $1032$ vertices. Thus, there are at least $2 \cdot 1032 \cdot 986$ non-yellow points. For the sake of contradiction, assume that there isn't any region whose vertices are all yellow. Note that every vertex belongs to exactly $4$ regions, including outer region. Refer to Euler's formula, there are exactly $2018^2 - 2018 + 2$ region, including the outer region. Since every two circles mutually intersect each other, so it's clear that every region has at least $2$ non-yellow points. Therefore, the number of pair $(v, V)$, where $v$ is non-yellow vertex and $V$ is some region that contains $v$, is at least $2 \cdot (2018^2 - 2018 + 1)$. (Excluding the outer region) On the other hand, every non-yellow vertex is a part of 4 region, so the number of pairs we're counting is at most $4 \cdot 2 \cdot 986 \cdot 1032$, so we get $2 \cdot (2018^2 - 2018 + 1) \le 4 \cdot 2 \cdot 1032 \cdot 986$, a contradiction. $\blacksquare$