\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Twitch 013.1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 13}
\maketitle
\section*{Problem}
There are $n$ pairwise intersecting circles in the plane,
no three passing through the same point and no two tangent.
The $n$ circles dissect the plane into
some number of regions bounded by circular arcs.
We assign a direction (clockwise or counterclockwise)
to each of the $n$ circles and count $C$,
the number of regions $R$ such that the boundary of $R$
can be traveled along the directions of edges.
Prove that if $n$ is sufficiently large,
then this assignment could be done such that
$C > \frac{4}{11\pi} n^2$.
\section*{Video}
\href{https://www.youtube.com/watch?v=6DxiStGJQb0&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/6DxiStGJQb0}}
\newpage
\section*{Solution}
Take any intersection point as a vertex.
We use \[ V-E+F=2 \] in the usual way.
Here $V = n(n-1)$ and $E = n(2n-2)$; hence the number of faces is
\[ F = n(2n-2) - n(n-1) + 2 = n^2 - n + 2 \]
We now do the assignment randomly by coin flip.
Suppose the regions have $a_1, a_2, \dots, a_m$ sides,
$m = n^2-n+2$ (including unbounded).
Then the expected number of good regions from this
(possibly including the unbounded face) is
\[ \sum_{i=1}^m \frac{1}{2^{a_i-1}} \]
where \[ \mathbb E[a_i] = \frac{2E}{F} = \frac{4n(n-1)}{n^2-n+1} \approx 4 \]
Thus by Jensen inequality,
one can get at least $(1/8-o(1))n^2$ good regions.
\end{document}