Local to global: ISL 2018 C7

(This is Glen.)

There hasn't been a post written for this week, so I figured I'd scroll through AoPS and try a problem that looked interesting. This ended up being:

(ISL 2018 C7) Consider $2018$ pairwise crossing circles no three of which are concurrent. These circles subdivide the plane into regions bounded by circular edges that meet at vertices. Notice that there are an even number of vertices on each circle. Given the circle, alternately colour the vertices on that circle red and blue. In doing so for each circle, every vertex is coloured twice - once for each of the two circle that cross at that point. If the two colours agree at a vertex, then it is assigned that colour; otherwise, it becomes yellow. Show that, if some circle contains at least $2061$ yellow points, then the vertices of some region are all yellow.

In theory, the 2018 shortlist was the one that I had early access to (since I was an Observer in 2019), but I don't remember trying this problem. I was probably too busy bashing my way through the geometry shortlist. Anyway. here's my attempt at a problem that I probably should have solved years ago.

Preliminary thoughts

• I was drawing a picture as I read the question, which is the standard 3-circle Venn diagram:

• At this point, I'd only read half the problem, so I was trying to two-colour the vertices such that no two adjacent vertices on a circle have the same colour, but quickly ran into a problem (see the circled vertices). I was confused until I read on and realised that each vertex has a colouring for each circle that it belongs to, and this issue basically forces some vertices in our picture to be yellow.

• Actually, more accurately, we failed to two-colour that picture above, because there's a region with an odd number of vertices. So every odd-sided region has at least one yellow vertex.

• We can probably do something stronger: imagine we walk around a region. Each time we go from one vertex to the next, we switch colours. Each time we hop onto a different circle, we switch colours if that vertex was yellow. So, since we switch colours and even number of times as we go around, we have:

Observation 1a: The number of yellow vertices around a region is the same parity as the total number of vertices around that region.

• This is really powerful! Instead of having to consider three different colours, we can just consider yellow directly. Does this lose any information? Well, given a choice of yellow vertices which satisfies Observation 1a, we can just greedily colour everything red/blue and the condition we imposed is exactly what we needed to never get stuck.

• This has to be on the right track.

• Let's try to find a legal example for this Venn diagram.

• There isn't any region with all its vertices yellow, but that's because we didn't have very many yellow vertices. In the question, there's also some assumption about a lower bound.

• Actually, looking at this picture, both the yellow vertices belong to the same pair of circles. Is this true in general?

• If we consider a region bounded by an arc of each of the circles (the middle part of the 2-circle Venn diagram), each other circle must intersect these an even number of times, since you must exit the region for each time you enter it. So, if we compare the red/blue colourings on both the circles, then these two vertices are either both matched or both mismatched! In other words, we have:

Observation 2a: The two intersections of any two circles are either both yellow or both not yellow.

• This is very reminiscent of one of the key observations for IMO 2016/6. 

Some counting, more observations

•  How many vertices are there in total? Well, each pair of circle intersects at most twice, so we have $V \le 2\binom{n}2 = n(n-1)$ where $n=2018$. Wait, actually, the question says that the circles are pairwise crossing, so we have equality, i.e. $$V = n(n-1).$$

• What about the number of regions? We can use $V-E+F=2$. Each edge links two vertices and each vertex has four edges, so $E=2V$, which tells us that $$F=V+2=n^2-n+2.$$

• What does the number $2061$ even mean? It looks like it's off from $2018$ by roughly some square root? Indeed, $2018+44=2062$, so it's roughly there.

• Actually, by Observation 2a, we can replace $2061$ with $2062$, so it's exactly $n+\lfloor\sqrt{n}\rfloor$.

• Now, each circle has $2(n-1)$ vertices, the lower bound means that some circle has slightly ($\sim\sqrt{n}$) more than half of its vertices being yellow.

• If two of these are on the same triangular region, then the last vertex of that region must also be yellow, so we're done. Does this always exist?

• How many triangular regions are there? We have $F\approx V$, and since each vertex belongs to $4$ regions, then each region must have around $4$ vertices on average. So we don't expect there to be very many triangles.

• Maybe we could look locally? We could invert and turn our circle with $\ge 2062$ yellow vertices into a line so it becomes easier to draw:

• The vertex that's the nearest to the line probably has to belong to a triangular region, but that doesn't say very much.

• What if we just look at two adjacent yellow vertices?

• If no circles go through that triangular region drawn above, then the top vertex has to be yellow, which is a contradiction. But each circle must either pass through both arcs once or one of the arcs twice, and either way, the top vertex should still remain yellow.

• Let's try to be more rigorous. Suppose we walk around that triangular region (or rather, union of regions). Each time we move along an edge, the colour swaps. Each time we change circles on a yellow vertex, the colour swaps. But there is an odd number of edges by the previous observation, so we must change circles on a yellow vertex an odd number of times. Since we change circles exactly $3$ times, this forces the last vertex to also be yellow. Hence:

Observation 2b: If two circles intersect a third circle on adjacent yellow vertices, the intersections of these two circles are also yellow.

• But in fact, this argument tells us something stronger. We can repeat the argument above for any cycle that bounds a (connected) union of regions. Then, this directly gives us a stronger version of Observation 1a:

Observation 1b: The number of vertices in a cycle has the same parity as the number of yellow vertices that the cycle turns on.

• In other words, yellow vertices that are on the "edges" (e.g. the long arcs in the example above) don't count, because their effects cancel out.

• But now, nothing is stopping us from applying this to generalise Observation 2b to the case with non-adjacent yellow vertices, and we get:

Observation 2c: If two circles intersect a third circle on yellow vertices, then these two circles also intersect on yellow vertices.

• Let $k$ be half the number of yellow vertices on our chosen circle, so $k\ge 1031$. Then, there are at least $$k + 2\binom{k}2 = k(k+1)$$ yellow vertices in total.

• Since $k\sim\frac{n}2$, this is roughly $\frac14$ of the total edges. That doesn't quite feel right. Are there more yellow vertices?

• Let's look again at the example from before.

• If we take either of the top circles to be our "main circle", we don't get anything interesting. But if the bottom one is the "main circle", we see that the other two circles both intersect it at non-yellow vertices.

• Right, looking at Observation 1b, we can in fact determine the colour of every single vertex, just by using the arguments from before the appropriate region:

Observation 2d: Fix a main circle. Two circles intersect on yellow vertices iff they both intersect the main circle on yellow vertices, or on non-yellow vertices.

• In other words, the colours of the vertices on the main circle determine the colours of all the vertices! That's incredibly powerful. 

• Now, we can count exactly the number of yellow vertices: it's $k(k+1) + 2\binom{n-1-k}2$. This formula is a little gross, so replace $k$ with $k+1$, so now $k\ge 1032$. Then, the number of yellow vertices is equal to $$k(k-1) + (n-k)(n-k-1).$$

• Here's a cool observation that follows from this that unfortunately didn't end up being useful:

Observation 3: Each circle has exactly $2(k-1)$ or $2(n-k-1)$ yellow vertices.

• This comes from repeating the same argument with another circle as the main circle, and then noting that $k(k-1) + (n-k)(n-k-1)$ is convex.

• In fact, double-counting with the total number of yellow vertices, this even tells us how many circles have $2(k-1)$ yellow vertices and how many have $2(n-k-1)$. But again, this doesn't end up being useful.

Profit

• Since $k\ge 1032 > \frac{n}2$, this gives us a lower bound on the total number of yellow vertices. This makes intuitive sense: if there are lots of yellow vertices, then we should be able to find a region with only yellow vertices. How to we make this precise?

• Maybe we could consider the non-yellow vertices instead. We have an upper bound on the number of these. Explicitly, this is:

• Now we want to find a lower bound on the number of non-yellow vertices, so we can get a contradiction. Each region has to have at least two of these (by Observation 1a), so this is at least

• Here, the $\frac14$ is because each vertex belongs to $4$ faces, so we're overcounting by a factor of $4$.

• Hence, we have shown that:

Observation 4:

• Now, we just need to plug $k=n+\sqrt{n}$ or something and find a contradiction...that looks disgusting.

• Arithmetic seemed to me to be the lesser evil, so I multiplied a bunch of 3- and 4-digit numbers by hand.

• To be honest, I'm slightly pleasantly surprised that I got these both right. Anyway, we have our contradiction, so we're done!

Post-mortem

That was nice: there are a couple of fairly simple observations to make, and it's a matter of strengthening and generalising these to get a very surprising result, that the colours of all the vertices are only determined by one circle. It definitely helped that I've done IMO 2016/6 before. Even so, it seems a little easy for a C7: you don't have to introduce any new structures; it's just a repeated application of one key idea. I certainly found this easier than the C5 (the last problem in NTST 2019), which was in turn much easier than the C4 (the infamous anti-Pascal IMO 2018/3).

I guess a place to get stuck would be getting scared off by the weird $2061$. Something one might try to do would be to try to reverse-engineer what the final bound should look like from $n+\sqrt{n}$. I didn't try that because I didn't want to do algebra with square-roots in it, so I don't know how that works out. I also wasn't quite sure if I'd get something off because of rounding errors. In general, I'm not a fan of playing "guess the quadratic".

In the light of Observation 3, there's a slightly more diabolical formulation: we could change our question condition to saying that one circle has at most $1971$ yellow vertices, which makes the problem look even more counterintuitive. I think this version would have been pretty funny.