IMO 2013

Key idea: induction on $k$. One factor $1+\frac1m$ can always be split off so that the remaining fraction is of the same type with $2^{k-1}-1$ on top and about half the denominator.

Base. For $k=1$, take $m_1=n$.

Step. Suppose the claim holds for $k-1$ and every $n$. Note $$1+\frac{2^{k-1}-1}{t}=\frac{2t+2^k-2}{2t}.$$

• $n=2t$ even. $$1+\frac{2^k-1}{2t}=\frac{2t+2^k-1}{2t}=\frac{2t+2^k-2}{2t}\cdot\frac{2t+2^k-1}{2t+2^k-2}=\Big(1+\frac{2^{k-1}-1}{t}\Big)\Big(1+\frac1{2t+2^k-2}\Big).$$
• $n=2t-1$ odd. $$1+\frac{2^k-1}{2t-1}=\frac{2t+2^k-2}{2t-1}=\frac{2t+2^k-2}{2t}\cdot\frac{2t}{2t-1}=\Big(1+\frac{2^{k-1}-1}{t}\Big)\Big(1+\frac1{2t-1}\Big).$$

In both cases the first factor is a product of $k-1$ factors $1+\frac1{m_i}$ by the induction hypothesis (with $t$ in place of $n$), and the second factor is one more, with a positive integer denominator. That gives $k$ factors.

Key idea: on a circle with alternating colors, every color change needs its own crossing, and a line crosses the circle only twice. Conversely, pairs of same-colored points can be fenced off by thin strips, and one extra line at the convex hull handles the odd one out.

Lower bound. Place the $4027$ points on a circle in the order $R,B,R,B,\dots,R,B,B$. No three points of a circle are collinear. Each of the $2013$ red points has blue points on both sides, so there are $4026$ arcs between neighbors of different colors. For such neighbors $P,Q$, some line must separate them, so it crosses the chord $PQ$. A line entering the region between the chord and the short arc $PQ$ through the chord must leave through the arc. So each of these $4026$ arcs is crossed by some line, and a line meets the circle at most twice. So at least $2013$ lines are needed.

Strips. For two points $P,Q$ of the configuration, take the two lines parallel to $PQ$ at a tiny distance on either side. If the distance is small enough, the strip between them contains no other point of the configuration (no three are collinear). So these two lines cut $P$ and $Q$ off from all other points.

Upper bound. Look at the convex hull.

• If some vertex of the hull is red, one line cuts that red point off from the rest. Pair the other $2012$ red points into $1006$ pairs and use two strip lines for each pair: $1+2012=2013$ lines. Every region containing a red point lies inside a strip or inside the cut-off part, and these contain only red points. Every other region contains only blue points.
• If every hull vertex is blue, take two neighboring hull vertices; one line cuts these two blue points off. Pair the remaining $2012$ blue points with strips: again $2013$ lines, and now every region with a blue point contains only blue points, and the rest only red.

So $2013$ lines always suffice, and the answer is $k=2013$.

Key idea: the perpendicular bisectors of the sides of $A_1B_1C_1$ pass through the midpoints of the arcs $BAC$, $CBA$, $ACB$. If the circumcenter $Q$ were on the circumcircle and away from these three points, $A_1B_1C_1$ would be acute, so $Q$ would lie inside it, which is impossible. So $Q$ is one of the arc midpoints, and a length computation then forces a right angle.

Let $a,b,c$ be the sides, $s$ the semiperimeter, $\alpha,\beta,\gamma$ the angles, and $\Gamma$ the circumcircle with radius $R$. Equal tangents give $$BA_1=s-c,\ \ CA_1=s-b,\qquad CB_1=s-a,\ \ AB_1=s-c,\qquad AC_1=s-b,\ \ BC_1=s-a .$$ Let $A_0$ be the midpoint of the arc $BAC$ of $\Gamma$, and define $B_0$, $C_0$ in the same way. These are three different points.

Step 1: $A_0B_1=A_0C_1$. Compare triangles $A_0BC_1$ and $A_0CB_1$. We have $A_0B=A_0C$ and $BC_1=CB_1=s-a$. Also $\angle A_0BC_1=\angle A_0BA=\angle A_0CA=\angle A_0CB_1$, as inscribed angles on the chord $A_0A$ ($B$ and $C$ are on the same side of it; if $A_0=A$, then $b=c$ and the claim is clear). So the triangles are congruent and $A_0B_1=A_0C_1$. Thus $A_0$ is on the perpendicular bisector of $B_1C_1$. In the same way $B_0$ is on the one of $C_1A_1$, and $C_0$ on the one of $A_1B_1$.

Step 2: $Q$ is $A_0$, $B_0$ or $C_0$. Suppose $Q$ is on $\Gamma$ but is none of them. Then the perpendicular bisectors of $B_1C_1$ and $C_1A_1$ are the lines $QA_0$ and $QB_0$. The angle of $A_1B_1C_1$ at $C_1$ equals an angle between these two lines (each side is perpendicular to one of them), so it is the inscribed angle on the chord $A_0B_0$ or its supplement. That chord cuts off an arc of $2\big(\tfrac\alpha2+\tfrac\beta2\big)=\alpha+\beta$: indeed $A_0$, $B_0$ are the points opposite the midpoints of the arcs $BC$ and $CA$ that avoid $A$ and $B$, and those midpoints are $\alpha+\beta$ apart (through $C$). So the angle at $C_1$ is $90^\circ-\tfrac\gamma2$ or $90^\circ+\tfrac\gamma2$. In the same way the angles at $A_1$ and $B_1$ are $90^\circ\mp\tfrac\alpha2$ and $90^\circ\mp\tfrac\beta2$.

With all minus signs the three angles add up to $270^\circ-90^\circ=180^\circ$, and each plus sign would add something positive. So all signs are minus and $A_1B_1C_1$ is acute. Then its circumcenter $Q$ lies inside it, hence inside triangle $ABC$ (on whose sides $A_1,B_1,C_1$ lie), hence strictly inside $\Gamma$. That contradicts $Q\in\Gamma$.

Step 3: if $Q=A_0$, the angle at $A$ is right. We compute $A_0A_1^2-A_0B_1^2$.

• $A_1$ is on the chord $BC$ and $A_0B=A_0C$, so $A_0A_1^2=A_0C^2-BA_1\cdot A_1C=A_0C^2-(s-b)(s-c)$. (Drop the perpendicular from $A_0$ to the midpoint of $BC$ and use Pythagoras twice.)
• In triangle $A_0CB_1$, by the law of cosines, $A_0B_1^2=A_0C^2+(s-a)^2-2(s-a)\cdot A_0C\cos\angle A_0CA$. Here $A_0C=2R\cos\tfrac\alpha2$ (the arc $A_0C$ is $180^\circ-\alpha$) and $\angle A_0CA=\tfrac{|\beta-\gamma|}2$ (the arc $AA_0$ is $|\beta-\gamma|$). So $$A_0C\cos\angle A_0CA=2R\cos\tfrac\alpha2\cos\tfrac{\beta-\gamma}2=R(\sin\beta+\sin\gamma)=\tfrac{b+c}2,$$ and $A_0B_1^2=A_0C^2+(s-a)^2-(s-a)(b+c)$.

Subtracting, and using $b+c-(s-a)=s$: $$A_0A_1^2-A_0B_1^2=s(s-a)-(s-b)(s-c)=\frac{b^2+c^2-a^2}2=bc\cos\alpha .$$ If $Q=A_0$, then $A_0A_1=A_0B_1$, so $\cos\alpha=0$ and the angle at $A$ is right. If $Q=B_0$ or $Q=C_0$, the angle at $B$ or at $C$ is right.

Key idea: the second meeting point $Z$ of the two circles lies on line $AW$. The diameters through $W$ make $X$, $Z$, $Y$ lie on the perpendicular to $AW$ at $Z$, and a power-of-a-point computation puts $H$ on that perpendicular too.

Let $D$ be the foot of the altitude from $A$, and let $\omega_1$ and $\omega_2$ meet again at $Z$.

$A$ is on the common chord. $\angle BNC=\angle BMC=90^\circ$, so $B,C,M,N$ lie on one circle and $AN\cdot AB=AM\cdot AC$. The left side is the power of $A$ with respect to $\omega_1$ (line $AB$ meets it at $N$ and $B$), and the right side is its power with respect to $\omega_2$. So $A$ lies on the radical axis $WZ$: the points $A$, $Z$, $W$ are collinear.

$X$, $Z$, $Y$ are collinear. $WX$ is a diameter of $\omega_1$, so $\angle WZX=90^\circ$. Likewise $\angle WZY=90^\circ$. So $X$ and $Y$ both lie on the line $\ell$ through $Z$ perpendicular to $ZW$, which is line $AW$.

$H$ is on $\ell$. $\angle BNH=\angle BDH=90^\circ$, so $B,N,H,D$ are concyclic and $AN\cdot AB=AH\cdot AD$. Together with the first step, $$AZ\cdot AW=AH\cdot AD .$$ So $Z,W,D,H$ are concyclic (converse of the power of a point). In that circle, $\angle HZW$ is equal or supplementary to $\angle HDW=90^\circ$, so $HZ\perp AW$, and $H\in\ell$.

Edge cases. If $Z=W$ (the circles touch), $\ell$ is the line through $W$ perpendicular to $AW$, and $AW^2=AH\cdot AD$ makes triangles $AWH$ and $ADW$ similar, so $\angle AWH=\angle ADW=90^\circ$ and again $H\in\ell$. If $W=D$, the equation gives $AZ=AH$, so $Z=H$, which is on $\ell$.

So $X$, $Y$ and $H$ are collinear.

Key idea: first show $f(x)\ge x$ for $x>1$. The fixed point $a$ gives $f(a^n)=a^n$ for all powers, and super-additivity at those huge values squeezes $f(m)\le m$ for integers. Then rationals follow from (i) and (ii).

Step 1: basic facts. By (i) with $x=a$, $y=1$: $af(1)=f(a)f(1)\ge f(a)=a$, so $f(1)\ge1$. By (ii), $f(n)\ge nf(1)\ge n$ for every positive integer $n$. For $x=\frac pq$, (i) gives $f(q)f(x)\ge f(p)>0$, so $f(x)>0$ for all $x$. Then (ii) shows $f$ is strictly increasing: $f(x+y)\ge f(x)+f(y)>f(x)$.

Step 2: $f(x)\ge x$ for $x>1$. For $z\ge1$, $f(z)\ge f(\lfloor z\rfloor)\ge\lfloor z\rfloor>z-1$. By (i) repeatedly (all values are positive), $f(x)^n\ge f(x^n)>x^n-1$. So $f(x)>(x^n-1)^{1/n}$ for every $n$, and letting $n\to\infty$ gives $f(x)\ge x$.

Step 3: $f(m)=m$ for integers. By (i), $f(a^n)\le f(a)^n=a^n$, and by Step 2, $f(a^n)\ge a^n$. So $f(a^n)=a^n$. Fix a positive integer $m$ and take $n$ so large that $a^n-m>1$. Then by (ii) and Step 2, $$a^n=f(a^n)\ge f(a^n-m)+f(m)\ge a^n-m+f(m),$$ so $f(m)\le m$. With Step 1, $f(m)=m$.

Step 4: rationals. Let $x=\frac pq$. By (i), $f(q)f(x)\ge f(p)$, so $f(x)\ge\frac pq$. By (ii) applied $q$ times, $f(p)=f(qx)\ge qf(x)$, so $f(x)\le\frac pq$. Hence $f(x)=x$.

Key idea: the beautiful labellings are exactly the circular orders of the points $0,\alpha,2\alpha,\dots,n\alpha$ (mod $1$). These orders change exactly when $\alpha$ passes a fraction $p/q$ with $q\le n$, and such fractions match the pairs $(x,y)$ counted by $N$. The fractions cut $(0,1)$ into $N+1$ pieces.

Work on a circle of length $1$, with positions read mod $1$ and “clockwise” meaning increasing. A labelling up to rotation is just the clockwise circular order of the labels, and whether two chords cross depends only on that order. Write $\{t\}$ for the fractional part and $\mathrm d(x,y)\in[0,1)$ for the clockwise distance from $x$ to $y$.

Setup. Let $F_n$ be the set of fractions in $(0,1)$ whose lowest-terms denominator is at most $n$. The map $(x,y)\mapsto\frac x{x+y}$ is a bijection from the pairs counted by $N$ onto $F_n$, since $\gcd(x,x+y)=\gcd(x,y)$. The points of $F_n$ cut $(0,1)$ into $N+1$ open intervals; call them the intervals of order $n$. For $\alpha$ in such an interval the points $k\alpha$ ($0\le k\le n$) are distinct; their order is the $\alpha$-order.

Fact 1: $\alpha$-orders are beautiful. If $a+d=b+c$, the reflection $t\mapsto(a+d)\alpha-t$ of the circle swaps $a\alpha$ with $d\alpha$ and $b\alpha$ with $c\alpha$. A chord joining a point to its mirror image is perpendicular to the mirror line. So the chords $ad$ and $bc$ are parallel, and they do not cross.

Fact 2: the order is constant on each interval. Two points $j\alpha$ and $k\alpha$ meet only when $(k-j)\alpha$ is an integer, that is, at a fraction with denominator at most $n$. Inside an interval of order $n$ the points move continuously and never meet, so their order does not change.

Fact 3: splitting. Between $\frac pn$ and $\frac{p+1}n$ (for $1\le p\le n-2$) lies $\frac p{n-1}$. So an interval $I$ of order $n-1$ contains at most one fraction $\frac pn$ in lowest terms. If it does, $I$ is cut into two intervals of order $n$. When $\alpha$ crosses $\frac pn$, the only two points that meet are $0$ and $n\alpha$ (since $n$ must divide $k-j$), so $n\alpha$ jumps from just before $0$ to just after $0$.

Fact 4: different intervals give different orders. Induction on $n$; for $n=1$ there is one interval. If two intervals of order $n$ give the same order, they give the same order of $0,\dots,n-1$, so by induction they lie in one interval $I$ of order $n-1$. By Fact 3 they are the two halves of $I$, and the label $n$ is just before $0$ in one and just after $0$ in the other. That is a contradiction.

Fact 5: if $n\alpha$ is next to $0$, the interval $I$ of order $n-1$ containing $\alpha$ holds some $\frac pn$. Suppose not. Then by Fact 2 (for order $n$) the order of $0,\dots,n$ is the same on all of $I=(r_1,r_2)$. Say $n\alpha$ comes right after $0$, so $\{n\alpha\}<\{k\alpha\}$ for $1\le k\le n-1$. Write $r_1=\frac uq$ in lowest terms, with $1\le q\le n-1$. As $\alpha$ decreases to $r_1$, $\{q\alpha\}=q(\alpha-r_1)\to0$. If $q\nmid n$, then $\{n\alpha\}\to\{nu/q\}\ge\frac1q$. If $q\mid n$, then $\{n\alpha\}=n(\alpha-r_1)>q(\alpha-r_1)$. Either way $\{n\alpha\}>\{q\alpha\}$ for $\alpha$ close to $r_1$, a contradiction. If $n\alpha$ comes right before $0$, the same argument works at $r_2$.

Fact 6: every beautiful labelling is an $\alpha$-order. Induction on $n$; for $n=1$ there is one labelling. Let $L$ be beautiful on $0,\dots,n$. Removing $n$ leaves a beautiful labelling of $0,\dots,n-1$, which by induction is the $\alpha$-order for all $\alpha$ in some interval $I$ of order $n-1$. Fix such an $\alpha$ that is not of the form $\frac pn$, and put $\pi=(n-1)\alpha$.

The only quadruples we need are $j<j+1<n-1<n$ with $0\le j\le n-3$: since $j+n=(j+1)+(n-1)$, the chords $\{j,n\}$ and $\{j+1,n-1\}$ may not cross. In clockwise order, this forbids the patterns $j,\,n-1,\,n,\,j+1$ and $n-1,\,j,\,j+1,\,n$.

In $L$, the label $n$ sits in some gap between neighbouring labels of $0,\dots,n-1$. Suppose this gap is not the one containing the point $n\alpha$, take a point $g$ in it, and suppose some label $k\ne0$ has $\mathrm d(\pi,k\alpha)$ strictly between $\mathrm d(\pi,g)$ and $\alpha=\mathrm d(\pi,n\alpha)$. Note $k\ne n-1$, so $1\le k\le n-2$; let $j=k-1$.

• If $\mathrm d(\pi,g)<\alpha$: going clockwise from $j\alpha=k\alpha-\alpha$, we meet $\pi$ (at distance $\alpha-\mathrm d(\pi,k\alpha)$), then $g$, then $k\alpha$ (at distance $\alpha$). That is the forbidden pattern $j,\,n-1,\,n,\,j+1$.
• If $\mathrm d(\pi,g)>\alpha$: going clockwise from $\pi$, we meet $j\alpha$ (at distance $\mathrm d(\pi,k\alpha)-\alpha$), then $k\alpha$, then $g$. That is the forbidden pattern $n-1,\,j,\,j+1,\,n$.

So between the gap of $n$ in $L$ and the point $n\alpha$ there is no label at all, or only the label $0$. The first case cannot happen, since the gap of $n$ would then be the one containing $n\alpha$ (and if it is that gap, $L$ is the $\alpha$-order). In the second case the gap of $n$ and the point $n\alpha$ are on the two sides of $0$, right next to it. Then $n\alpha$ is next to $0$, so by Fact 5 the interval $I$ contains some $\frac pn$; for $\alpha'$ in $I$ on the other side of $\frac pn$, the point $n\alpha'$ is on the other side of $0$ (Fact 3), and $L$ is the $\alpha'$-order.

Counting. By Facts 1 and 6 the beautiful labellings are exactly the $\alpha$-orders, and by Facts 2 and 4 there is exactly one for each of the $N+1$ intervals of order $n$. So $M=N+1$.