IMO 2014

Key idea: one integer sequence $d_n$ captures both inequalities, and it strictly decreases from a positive start. It crosses zero exactly once.

Let $d_n=(a_0+a_1+\dots+a_n)-na_n$ for $n\ge1$.

• The left inequality $na_n<a_0+\dots+a_n$ says $d_n>0$.
• The right inequality $a_0+\dots+a_n\le na_{n+1}$ says $(a_0+\dots+a_{n+1})-(n+1)a_{n+1}\le0$, that is, $d_{n+1}\le0$.

So we need exactly one $n\ge1$ with $d_n>0\ge d_{n+1}$.

Now $d_{n+1}-d_n=a_{n+1}-(n+1)a_{n+1}+na_n=n(a_n-a_{n+1})<0$, so the integers $d_1,d_2,\dots$ strictly decrease. Also $d_1=a_0>0$. A strictly decreasing integer sequence goes below $0$ eventually, so there is a first index $m$ with $d_m\le0$, and $m\ge2$. Then $n=m-1$ works, and no other $n$ does: for smaller $n$, $d_{n+1}>0$; for larger $n$, $d_n\le0$.

Key idea: an empty $k\times k$ square exists whenever $k^2<n$, by a pigeonhole on blocks of columns. For the matching example, write positions in base $\ell$ and swap the two digits.

Let $k=\lfloor\sqrt{n-1}\rfloor$, so $k^2\le n-1$ and $(k+1)^2\ge n$. Rows and columns are numbered from $0$.

An empty $k\times k$ square always exists. Let the rook of column $0$ be in row $r$. Choose $k$ consecutive rows that include row $r$. These rows hold $k$ rooks: one in column $0$, and $k-1$ others. Columns $1,\dots,n-1$ contain $\lfloor\frac{n-1}k\rfloor\ge k$ disjoint blocks of $k$ consecutive columns. The $k-1$ other rooks meet at most $k-1$ of these blocks, so one block has no rook in the chosen rows. That gives an empty $k\times k$ square.

A board with no empty $(k+1)\times(k+1)$ square. Let $\ell=k+1$.

For $n=\ell^2$. Write a row as $a\ell+b$ with digits $0\le a,b<\ell$, and put its rook in column $b\ell+a$. This is a permutation. Take an $\ell\times\ell$ square with rows from $a_0\ell+b_0$ and columns from $\beta\ell+\alpha$. Its rows are $(a_0,b)$ for $b\ge b_0$ and $(a_0+1,b)$ for $b<b_0$. Its columns are $(\beta,a)$ for $a\ge\alpha$ and $(\beta+1,a)$ for $a<\alpha$. The rook of row $(A,B)$ is in column $(B,A)$. We look for a row in the square with $B=\beta$, $A\ge\alpha$, or with $B=\beta+1$, $A<\alpha$.

• If $\beta\ge b_0$: rows with $B=\beta$ and $B=\beta+1$ have $A=a_0$. If $a_0\ge\alpha$, the first kind works. If $a_0<\alpha$, the second kind works, provided $\beta+1<\ell$; and if $\beta=\ell-1$, the square fits on the board only when $\alpha=0\le a_0$.
• If $\beta<b_0$: the row with $B=\beta$ has $A=a_0+1$, which works if $a_0+1\ge\alpha$. Otherwise $a_0+1<\alpha$; the row with $B=\beta+1$ has $A=a_0$ or $a_0+1$, both less than $\alpha$, so it works.

So every $\ell\times\ell$ square contains a rook.

For $n<\ell^2$. Start from the $\ell^2$ board and delete the last $\ell^2-n$ rows together with the columns of their rooks. What remains is a peaceful board of size $n$. An $\ell\times\ell$ square on it comes from $\ell$ consecutive old rows and a run of old columns at least $\ell$ long. The first $\ell$ of those columns form an old square, which has a rook. Its row was kept, so its column was kept too, and the rook is in the new square.

So $k=\lfloor\sqrt{n-1}\rfloor$ is the answer.

Key idea: the strange angle conditions just say that the circles $CHS$ and $CHT$ have their centres on $AB$ and $AD$. Then the centre of circle $HST$ is where two angle bisectors cross line $AH$, and a short trigonometric computation shows the two crossings are the same point.

Since $AH\perp BD$, the line $BD$ is tangent to circle $HST$ at $H$ exactly when the centre of that circle lies on line $AH$. That is what we prove.

Step 1: centres on the sides. Let $Q$ be the point of line $AB$ with $\angle SCQ=90^\circ$. Triangle $SBC$ has a right angle at $B$, so $\angle CSB$ is acute and $Q$ lies on ray $SB$, beyond $B$. In triangle $SCQ$, $\angle SQC=90^\circ-\angle CSB$. The condition says $\angle SHC=90^\circ+\angle CSB$, so $\angle SQC+\angle SHC=180^\circ$. Segment $SC$ cuts the quadrilateral into triangle $SBC$ and a piece containing $A$ and $T$. $H$ is inside triangle $SCT$, so $H$ is on the side of line $SC$ away from $Q$. Hence $S,H,C,Q$ are concyclic, and since $\angle SCQ=90^\circ$, $SQ$ is a diameter.

So the centre $K$ of circle $SHC$ is the midpoint of $SQ$. It lies on line $AB$, on the ray from $S$ through $B$, so $S$ lies between $A$ and $K$ (or $S=A$). In the same way, the centre $L$ of circle $THC$ lies on line $AD$, and $T$ lies between $A$ and $L$. In particular $$KS=KH=KC,\qquad LT=LH=LC .$$

Step 2: the centre of $HST$. The perpendicular bisector of $HS$ passes through $K$ and bisects angle $SKH$, which is angle $AKH$ (ray $KS$ is ray $KA$). By the angle bisector theorem in triangle $AKH$, it meets segment $AH$ at the point $P$ with $\dfrac{AP}{PH}=\dfrac{AK}{KH}$. Likewise the perpendicular bisector of $HT$ meets $AH$ at $P'$ with $\dfrac{AP'}{P'H}=\dfrac{AL}{LH}$.

If $\dfrac{AK}{KH}=\dfrac{AL}{LH}$, then $P=P'$ is equally far from $H$, $S$ and $T$, so it is the centre of circle $HST$, and it is on $AH$. Since $KH=KC$ and $LH=LC$, it remains to prove $$\frac{KC}{AK}=\frac{LC}{AL}.$$

Step 3: the computation. $B$ and $D$ lie on the circle with diameter $AC$; take $AC=1$. Let $\alpha=\angle BAC$ and $\delta=\angle DAC$. Then $AB=\cos\alpha$ and $AD=\cos\delta$. Also $\angle ABD=\angle ACD=90^\circ-\delta$, so in the right triangle $ABH$ we get $\angle BAH=\delta$ and $AH=\cos\alpha\cos\delta$; similarly $\angle DAH=\alpha$.

Let $k=AK$, with $K$ on ray $AB$. The law of cosines in triangles $AKC$ and $AKH$ gives $$KC^2=k^2-2k\cos\alpha+1,\qquad KH^2=k^2-2k\cos\alpha\cos^2\delta+\cos^2\alpha\cos^2\delta .$$ Setting them equal: $2k\cos\alpha\sin^2\delta=1-\cos^2\alpha\cos^2\delta$. Call the right side $N$; it is positive, so $k>0$ as assumed. Then $$KC^2=k^2+1-\frac N{\sin^2\delta}=k^2-\frac{\sin^2\alpha\cos^2\delta}{\sin^2\delta},$$ because $\sin^2\delta-N=\cos^2\alpha\cos^2\delta-\cos^2\delta=-\sin^2\alpha\cos^2\delta$. Using $k\sin\delta=\dfrac N{2\cos\alpha\sin\delta}$, $$\frac{KC^2}{AK^2}=1-\Big(\frac{\sin\alpha\cos\delta}{k\sin\delta}\Big)^2=1-\Big(\frac{2\sin\alpha\cos\alpha\sin\delta\cos\delta}{N}\Big)^2 .$$ This is symmetric in $\alpha$ and $\delta$, and $N$ is too. The same computation for $L$ (swap the roles of $B$ and $D$) gives the same value for $\dfrac{LC^2}{AL^2}$. So $\dfrac{KC}{AK}=\dfrac{LC}{AL}$, and we are done.

Key idea: the two cevians have the same length, and the doubled points make two similar triangles. Then the angle at the meeting point is $180^\circ-\angle A$, so it is on the circumcircle.

Let $a,b,c$ be the sides and $\alpha=\angle A$.

Lengths. $\angle PAB=\angle C$ and the angle at $B$ is shared, so triangles $BAP$ and $BCA$ are similar: $BP=\dfrac{c^2}a$, $AP=\dfrac{bc}a$, and $\angle APB=\alpha$. In the same way $CQ=\dfrac{b^2}a$, $AQ=\dfrac{bc}a$, and $\angle AQC=\alpha$. So $PM=AP=AQ=QN=\dfrac{bc}a$.

Similar triangles. $M$ is on ray $AP$ beyond $P$, so $\angle BPM=180^\circ-\angle APB=180^\circ-\alpha$. Likewise $\angle NQC=180^\circ-\alpha$. Also $$\frac{BP}{PM}=\frac{c^2/a}{bc/a}=\frac cb,\qquad\frac{NQ}{QC}=\frac{bc/a}{b^2/a}=\frac cb .$$ So triangles $BPM$ and $NQC$ are similar (equal angle between proportional sides), and $\angle PBM=\angle QNC$.

The meeting point. Let $X$ be where $BM$ and $CN$ meet; it lies on the other side of $BC$ from $A$. Then $$\angle XBC+\angle XCB=\angle PBM+\angle QCN=\angle QNC+\angle QCN=180^\circ-\angle NQC=\alpha .$$ So $\angle BXC=180^\circ-\alpha$. A point on the opposite side of $BC$ from $A$ that sees $BC$ at $180^\circ-\alpha$ lies on the circumcircle.

Key idea: after tidying, the coins with denominators $2k-1$ and $2k$ fit into one group. The remaining coins are tiny, and a greedy filling can only fail if every group is nearly full, which the total doesn’t allow.

Keep track of $N$, the number of groups still available, and the total value $V$ of the coins not yet placed. At the start $N=100$ and $V\le N-\tfrac12$.

Tidying. Repeat while possible:

• If there are two coins $\frac1{2k}$, glue them into one “coin” of value $\frac1k$ (they will go to the same group).
• If there are $d$ coins $\frac1d$ (for any $d$, including $d=1$), put them in a group of their own. This uses one group and removes value exactly $1$, so $V\le N-\tfrac12$ still holds.

Each step lowers the number of coins, so this stops. Afterwards: at most one coin $\frac1{2k}$ for each $k$, and at most $d-1$ coins $\frac1d$ for each odd $d$. Also $N\ge1$ unless nothing is left, because $V\ge0$.

The first $N$ groups. Put all coins with denominators $2k-1$ and $2k$ into group $k$, for $k=1,\dots,N$. Its value is at most $$\frac{2k-2}{2k-1}+\frac1{2k}<\frac{2k-2}{2k-1}+\frac1{2k-1}=1 .$$

Small coins. The coins left have denominators at least $2N+1$, so each is at most $\frac1{2N+1}$. Place them one by one into any group where they fit. If some coin fits nowhere, every group has value more than $1-\frac1{2N+1}=\frac{2N}{2N+1}$, and $$V>\frac{2N^2}{2N+1}=N-\frac{N}{2N+1}>N-\frac12,$$ a contradiction. So all coins are placed, in the $N$ groups plus the full groups made earlier. That is at most $100$ groups, each of value at most $1$.

Key idea: take a blue set that cannot be enlarged. Every red line then “almost closes” a blue region, and we charge it to a crossing of two blue lines. A careful look at the four corners at a crossing shows each crossing is charged at most twice, so $n-k\le 2\binom k2$, which gives $k\ge\sqrt n$. This works for every $n$, not only large ones.

A maximal blue set. Call a set of lines good if no bounded region (of the arrangement of all $n$ lines) has all its sides on lines of the set. The empty set is good. Choose a good set $B$ that is maximal: adding any other line makes it bad. Colour $B$ blue and the rest red; let $k=|B|$. We show $n\le k^2$.

Each red line closes a region. Let $\ell$ be red. Since $B\cup\{\ell\}$ is bad but $B$ is good, there is a bounded region $R_\ell$ with all sides on lines of $B\cup\{\ell\}$, one of them on $\ell$. A bounded region is a convex polygon with at least $3$ sides, each on a different line. So $R_\ell$ has exactly one red side, on $\ell$, and at least two blue sides.

The charge. Walk around $R_\ell$ counterclockwise. After the side on $\ell$ comes a side on a blue line $m$, and its far end $P_\ell$ is a corner where $m$ meets the next side’s line, which is blue (it is not $\ell$, because each line gives at most one side). So $P_\ell$ is a crossing of two blue lines. Charge $\ell$ to $P_\ell$; note that $R_\ell$ is one of the four regions with a corner at $P_\ell$, and in the counterclockwise walk around $R_\ell$ we arrive at $P_\ell$ along $m$, coming from the point where $m$ meets $\ell$.

Each crossing is charged at most twice. Let $P$ be a crossing of two lines. Its four rays cut the plane near $P$ into four corners. For a corner bounded by rays $r$ and $r'$, with $r'$ the next ray counterclockwise after $r$, a counterclockwise walk around the region in that corner arrives at $P$ along $r'$ and leaves along $r$. So two neighbouring corners, which share a ray $r$, use it in opposite ways: one arrives along $r$, the other leaves along $r$.

Suppose two neighbouring corners were the regions $R_\ell$ and $R_{\ell'}$ of two red lines charged to $P$, sharing the ray $r$. Say $R_\ell$ arrives along $r$. Its side on $r$ is the edge from $P$ to the next crossing $X$ on $r$, and $X$ lies on $\ell$ (the side before it is on $\ell$). The other region $R_{\ell'}$ leaves $P$ along the same edge $PX$, and at $X$ it turns onto the other line through $X$, which is $\ell$. So $\ell$ is a side of $R_{\ell'}$. But the only red side of $R_{\ell'}$ is on $\ell'$, so $\ell=\ell'$. That is impossible, because each red line was charged once, through one region. So no two neighbouring corners are used, and at most two of the four corners (opposite ones) are.

Counting. There are $\binom k2$ crossings of blue lines, each charged at most twice, and each of the $n-k$ red lines is charged once. So $$n-k\le 2\binom k2=k^2-k,$$ that is, $n\le k^2$ and $k\ge\sqrt n$. The blue set $B$ has at least $\sqrt n$ lines and no bounded region with an all-blue boundary.