HMMT February

For convenience, we take all indices modulo $n$. Let $[n]$ be the set $\{1,2, \ldots, n\}$. Also, let $M=\max \left(a_{1}, \ldots, a_{n}\right), d=\frac{1}{2} \sum_{i}\left|a_{i}-a_{i+1}\right|$, and $M^{\prime}=\max (M, d)$. We claim that $M^{\prime}$ is the answer. Let $\Omega$ be the circumcircle of the polygon. First let's prove that $m \geq M^{\prime}$. Obviously $m \geq M$. Also, there must be at least $\left|a_{i}-a_{i+1}\right|$ circles crossing $\Omega$ between $P_{i}$ and $P_{i+1}$, and a circle can cross $\Omega$ at most twice. Thus $m \geq d$. We will present two ways to arrive at a construction. Inductive construction. We use induction on $\sum_{i} a_{i}$. If all the $a_{i}$ are zero, then the problem is trivial. Now assume that not all the $a_{i}$ are zero the idea is that we are going to subtract 1 from a consecutive subset of the $a_{i}$ so that the value of $M^{\prime}$ goes down by 1. There are two cases. First of all, if $a_{i}=0$ for some $i$, then we can choose such an $i$ so that $a_{i+1}>0$. Then, let $j$ be the minimal positive integer so that $a_{i+j}=0$. Then subtract 1 from $a_{i+1}, \ldots, a_{i+j-1}$. It is clear that $d$ decreases by 1. If $a_{i+j}=a_{i+j+1}=\cdots=a_{i}=0$, then $M$ also goes down by 1. If not, then $M<d$, so $M^{\prime}$ goes down by 1 anyway. The second case is when $a_{i}>0$ for all $i$. If all the $a_{i}$ are the same then we are done by subtracting 1 from everything. If not, we can find $i, j$ with $j>i+1$ so that $a_{i}=M, a_{j}=M$, and $a_{i+1}, a_{i+2}, \ldots, a_{j-1}<M$. Then subtract 1 from the complement of $a_{j}, a_{j+1}, \ldots, a_{i-1}$. Then $M$ goes down by 1 and $d$ goes down by 1. Non-inductive construction. We will prove that if $M \leq d$, then we may choose $m=d$. If $M>d$, then since $d \geq M-\min \left(a_{1}, \ldots, a_{n}\right)$ we can subtract $M-d$ from every $a_{i}$, draw $M-d$ circles containing every point, and apply the below construction. Let $a_{i}^{\prime}=a_{i}-\min _{j}\left(a_{j}\right), A_{h}=\left\{i \mid a_{i}^{\prime}<h, a_{i+1}^{\prime} \geq h\right\}, B_{h}=\left\{i \mid a_{i}^{\prime} \geq h, a_{i+1}^{\prime}<h\right\}$. Also, let $s_{h}=\left|A_{h}\right|=\left|B_{h}\right|$. Note that $d=\sum_{h} s_{h}$ and that $s_{h}>0 \Longrightarrow h \leq \max \left(a_{i}^{\prime}\right)$. For $h \leq \max \left(a_{i}^{\prime}\right)$ and $1 \leq j \leq s_{h}$, define an arrangement of circles $C_{h}^{(j)}$ as follows: let the elements of $A_{h}$ and $B_{h}$ be $a_{1}, b_{1}, a_{2}, b_{2}, \ldots$ in order. Then for each $i \leq s_{h}$ add a circle covering the points in the interval $\left(a_{i}, b_{i+j}\right.$ ]. One can show that point $P_{i}$ is covered by circles $j$ times if $a_{i}^{\prime} \geq h$ and $j-1$ times otherwise. Now, for some choice of $j_{h}$ for all $h$, consider taking $\bigcup_{h} C_{h}^{\left(j_{h}\right)}$. Then, $P_{i}$ is covered by circles $\sum_{h} j_{h}+a_{i}-M$ times. If we choose the $j_{h}$ so that $\sum_{h} j_{h}=M$, which can be shown to be possible, we are done.