IMO 2000

Key idea: $M$ turns out to be the midpoint of $PQ$, and $E$ is the mirror image of $M$ in the line $AB$. So $E$ sits on the perpendicular bisector of $PQ$.

We work in the usual picture, with $C$, $M$, $D$ in this order on a line parallel to $AB$, and $N$ between the lines $AB$ and $CD$. (The points $M$ and $N$ lie on the same side of $AB$; the point $E$ lies on the other side.)

Step 1: $M$ is the midpoint of $PQ$. Let line $NM$ meet $AB$ at $K$. The power of $K$ with respect to the first circle is $KA^2=KM\cdot KN$, and with respect to the second it is $KB^2=KM\cdot KN$. So $KA=KB$: $K$ is the midpoint of $AB$.

Now look from $N$. The points $P$, $M$, $Q$ lie on line $CD$, which is parallel to $AB$, and $P$, $M$, $Q$ lie on the lines $NA$, $NK$, $NB$. The scaling about $N$ that carries line $AB$ to line $CD$ sends $A\mapsto P$, $K\mapsto M$, $B\mapsto Q$. Scalings keep midpoints, so $M$ is the midpoint of $PQ$.

Step 2: $E$ is the reflection of $M$ in $AB$. The line $AB$ is tangent to the first circle at $A$, so the angle between $AB$ and the chord $AM$ equals the inscribed angle on that chord: $$\angle BAM=\angle ACM .$$ Since $E$ lies on ray $CA$ beyond $A$ and $AB\parallel CM$, corresponding angles give $\angle BAE=\angle ACM$. So $\angle BAE=\angle BAM$: the line $AB$ bisects the angle $EAM$. In the same way $\angle ABE=\angle ABM$.

The triangles $ABE$ and $ABM$ share the side $AB$, have equal angles at $A$ and at $B$, and lie on opposite sides of $AB$. So each is the mirror image of the other in $AB$, and $E$ is the reflection of $M$.

Finish. A point and its reflection are joined by a line perpendicular to the mirror, so $EM\perp AB$. Since $PQ\parallel AB$, also $EM\perp PQ$. Together with Step 1, the line $EM$ is the perpendicular bisector of $PQ$. Every point on it is equally far from $P$ and $Q$, so $PE=QE$.

Key idea: write the numbers as ratios. The inequality becomes a classical fact about three numbers that may or may not be the sides of a triangle.

Since $ABC=1$, we can write $A=\dfrac xy$, $B=\dfrac yz$, $C=\dfrac zx$ with $x,y,z>0$ (take $x=1$, $y=\frac1A$, $z=\frac1{AB}$). Then $$A-1+\frac1B=\frac xy-1+\frac zy=\frac{x-y+z}{y},$$ and in the same way the other two factors are $\dfrac{y-z+x}{z}$ and $\dfrac{z-x+y}{x}$. So we must show $$(x-y+z)(y-z+x)(z-x+y)\le xyz .$$

At most one factor is negative. The sum of any two factors is $2x$, $2y$ or $2z$, which is positive. So two factors can’t both be negative. If exactly one is negative, the left side is negative and we are done.

All factors at least zero. Pair them: $$(x-y+z)(x+y-z)=x^2-(y-z)^2\le x^2,$$ and similarly the other two pairs are at most $y^2$ and $z^2$. Multiplying the three pair inequalities (all sides are nonnegative) gives $$\big[(x-y+z)(y-z+x)(z-x+y)\big]^2\le x^2y^2z^2,$$ and taking square roots finishes the proof. Equality holds for $x=y=z$, that is, $A=B=C=1$.

Key idea: compare the gain of the rightmost position with the gain of the total. The quantity $\Phi=NR-S$ (the sum of the distances from every point to the rightmost one) decides everything.

Let $R$ be the largest position and $S$ the sum of all positions, so $\Phi=NR-S\ge0$. A move takes a point at $b$ and a point at $a>b$, and puts the first point at $a+k(a-b)$. Write $g=a-b>0$.

• $S$ grows by exactly $(1+k)g$.
• $R$ grows by at most $kg$: the new point is $a+kg\le R+kg$.

If $k<\frac1{N-1}$, the points stay bounded. In one move, $\Delta R\le kg=\dfrac{k}{1+k}\Delta S$, so $$\Delta\Phi=N\,\Delta R-\Delta S\le\Big(N-\frac{1+k}{k}\Big)\Delta R=-c\,\Delta R,\qquad c=\frac1k+1-N>0 .$$ (If $\Delta R=0$ then $\Delta\Phi=-\Delta S<0$, which also fits.) Since $\Phi$ starts at some value $\Phi_0$ and never goes below $0$, the total increase of $R$ over all moves is at most $\Phi_0/c$. The points can never pass $R_0+\Phi_0/c$.

If $k\ge\frac1{N-1}$, they can go as far as we like. Always jump the leftmost point $b$ over the rightmost point $R$. Then $g=R-b$, the new rightmost position is $R+kg$, and $$\Phi_{\text{new}}=N(R+kg)-\big(S-b+R+kg\big)=\Phi-g+(N-1)kg\ \ge\ \Phi .$$ So $\Phi$ never drops below its starting value $\Phi_0>0$ (the points are not all equal). In particular the leftmost and rightmost points never coincide, so the move is always allowed. Also $\Phi$ is a sum of $N$ distances, each at most $g$, so $g\ge\Phi/N\ge\Phi_0/N$. Each move raises $R$ by $kg\ge k\Phi_0/N$, a fixed positive amount. After enough moves, every point can be pushed past any mark: once $R$ is huge, one more round of jumps moves each point beyond the old $R$.

Key idea: equal sums such as $x+(y+1)=(x+1)+y$ are forbidden across different pairs of boxes. This forces either the pattern of remainders mod $3$, or the split $\{1\},\{100\},\{2,\dots,99\}$.

Call the boxes $X,Y,Z$. The trick works exactly when the three sets of sums $X+Y$, $Y+Z$, $Z+X$ (one card from each of two boxes) are pairwise disjoint.

Both families work. If the boxes hold the numbers $\equiv0,1,2\pmod3$, the three kinds of sums are $\equiv1,0,2\pmod3$, all different. If the boxes are $\{1\}$, $\{100\}$, $\{2,\dots,99\}$, the sums are $101$, the range $3$–$100$, and the range $102$–$199$. In each family the boxes can be assigned in $3!=6$ ways, so we get $12$ ways. It remains to show there are no others.

Lemma. Suppose $x\in X$ and $x+1\in Y$ with $X\ne Y$, and $z$ is in the third box $Z$. Then $z+1\in X$ (if $z<100$) and $z-1\in Y$ (if $z>1$).

Proof. $x+(z+1)=(x+1)+z$, and the right side is a $Y{+}Z$ sum. If $z+1$ were in $Y$ or $Z$, the left side would be an $X{+}Y$ or $X{+}Z$ sum, which is not allowed. So $z+1\in X$. Similarly $(x+1)+(z-1)=x+z$ is an $X{+}Z$ sum, so $z-1$ must be in $Y$.

Case 1: three consecutive numbers $t,t+1,t+2$ sit in three different boxes. Say $t\in X$, $t+1\in Y$, $t+2\in Z$. Then $t+3\in X$: if $t+3\in Z$, then $(t+3)+t=(t+1)+(t+2)$ is both a $Z{+}X$ and a $Y{+}Z$ sum; if $t+3\in Y$, it is both an $X{+}Y$ and a $Y{+}Z$ sum. By the mirror argument $t-1\in Z$. Repeating forward and backward, the boxes follow the remainders mod $3$. That is the first family.

Case 2: no three consecutive numbers are in three different boxes. Since every box is used, somewhere $x$ and $x+1$ are in different boxes $X\ne Y$. By the Lemma, a card $z$ of the third box with $1<z<100$ would have $z-1\in Y$, $z\in Z$, $z+1\in X$, which Case 2 forbids. So the third box is contained in $\{1,100\}$. This holds for every “change point” $x,x+1$.

The third box can’t be $\{1,100\}$: the change point $1,2$ would then have a third box avoiding both $1$ and $100$, so it would be empty. So it is a single card, say $\{1\}$ (the case $\{100\}$ is the mirror image under $n\mapsto101-n$). Now $1,2$ is a change point, and its third box is inside $\{1,100\}$ but doesn’t contain $1$. So it is $\{100\}$, and the remaining box holds $2,\dots,99$. That is the second family.

So there are exactly $12$ ways.

Key idea: build $N$ one prime at a time. The factor $t^2-t+1$ of $t^3+1$ always brings a new prime.

Call $N$ good if $N$ is odd, $3\mid N$ and $N\mid 2^N+1$. For example $N=3$ is good, since $3\mid 9$. We show: if $N$ is good, there is a good number with exactly one more prime factor. Starting from $3$ and applying this $1999$ times gives a good number with exactly $2000$ prime factors, so the answer is yes.

Step 1: $3N$ is good. Let $t=2^N$. Then $2^{3N}+1=t^3+1=(t+1)(t^2-t+1)$. We know $N\mid t+1$. Also $3\mid t+1$, so $t\equiv-1\pmod 3$ and $t^2-t+1\equiv3\equiv0\pmod 3$. So $3N\mid 2^{3N}+1$.

Step 2: a new prime. Write $t^2-t+1=(t+1)^2-3t$. Since $9\mid(t+1)^2$ but $9\nmid 3t$, exactly one factor $3$ divides $t^2-t+1$. So $t^2-t+1=3m$ with $3\nmid m$, and $m>1$ because $t\ge8$. Any common divisor of $t+1$ and $t^2-t+1$ divides $(t+1)^2-(t^2-t+1)=3t$, and since $t+1$ is odd and prime to $t$, it divides $3$. So $m$ is coprime to $t+1$. Take a prime $p\mid m$. Then $p\ne3$, $p\nmid t+1=2^N+1$, hence $p\nmid N$ (because $N\mid 2^N+1$), and $p\mid 2^{3N}+1$.

Step 3: $p\cdot 3N$ is good. Let $N'=3N$, which is good by Step 1, with $p\mid 2^{N'}+1$ and $p\nmid N'$. Since $p$ is odd, $2^{N'}+1$ divides $2^{pN'}+1$. So both $N'$ and $p$ divide $2^{pN'}+1$, and they are coprime, so $pN'\mid 2^{pN'}+1$. The number $pN'$ is odd and divisible by $3$, and it has exactly one more prime factor than $N$.

Let $\alpha_1,\alpha_2,\alpha_3$ be the angles at $A_1,A_2,A_3$, $I$ and $r$ the incenter and inradius, $O$ and $R$ the circumcenter and circumradius.

Key idea: the reflection of $K_1K_2$ in $L_1L_2$ is the image of the side $A_1A_2$ under the homothety with center $I$ and ratio $-\cos\alpha_3$. So the three new lines are the sides of a copy of the triangle, scaled by $\frac rR$ and turned half around, whose corners lie at distance $r$ from $I$.

Step 1: a map that sends $A_1A_2$ to $K_1K_2$. Let $\phi$ be the reflection in the bisector of the angle at $A_3$, followed by the homothety with center $A_3$ and ratio $\cos\alpha_3$ (positive, as the triangle is acute). The reflection moves $A_1$ onto ray $A_3A_2$, and the homothety brings it to distance $A_3A_1\cos\alpha_3$ from $A_3$. In the right triangle $A_1K_1A_3$ that distance is $A_3K_1$, so $\phi(A_1)=K_1$. Likewise $\phi(A_2)=K_2$, so $\phi$ maps line $A_1A_2$ onto line $K_1K_2$. The incenter is on the bisector, so $\phi(I)=I^*$, the point of segment $A_3I$ with $A_3I^*=A_3I\cos\alpha_3$.

Step 2: the reflection in $L_1L_2$. Since $A_3L_1=A_3L_2$, the line $L_1L_2$ is perpendicular to the bisector $A_3I$. In the right triangle $A_3L_1I$, $A_3L_1=A_3I\cos\frac{\alpha_3}2$, so $L_1L_2$ crosses the bisector at distance $A_3L_1\cos\frac{\alpha_3}2=A_3I\cos^2\frac{\alpha_3}2$ from $A_3$. Let $\sigma$ be the reflection in $L_1L_2$. On the bisector it sends the point at distance $d$ from $A_3$ to the point at distance $2A_3I\cos^2\frac{\alpha_3}2-d=A_3I\,(1+\cos\alpha_3)-d$. In particular $\sigma(I^*)=I$.

Step 3: the composite is a homothety at $I$. $\sigma\circ\phi$ is a similarity. Its linear part is a reflection in the direction of the bisector, then a reflection in the perpendicular direction, times $\cos\alpha_3$. Two reflections in perpendicular lines make a half turn, so the linear part is $-\cos\alpha_3$ times the identity. A similarity with this linear part that fixes $I$ is the homothety $H_3$ with center $I$ and ratio $-\cos\alpha_3$. Therefore $$\sigma(K_1K_2)=\sigma\big(\phi(A_1A_2)\big)=H_3(A_1A_2).$$ The new line is parallel to $A_1A_2$, at distance $r\cos\alpha_3$ from $I$, on the side of $I$ toward $A_3$ (the line $A_1A_2$ is at distance $r$ from $I$, on the other side).

Step 4: the new triangle. Let $h(X)=I-\frac rR\,(X-O)$. Because the triangle is acute, $O$ lies inside it at distance $R\cos\alpha_3$ from $A_1A_2$. So $h$ maps line $A_1A_2$ to the line parallel to it at distance $\frac rR\cdot R\cos\alpha_3=r\cos\alpha_3$ from $I$, on the side toward $A_3$. That is the line from Step 3. The same holds for the other two pairs of lines. So the three new lines are the sides of the triangle $h(A_1)h(A_2)h(A_3)$, and $$|h(A_i)-I|=\tfrac rR\,|A_i-O|=r .$$ The three new lines form a triangle whose vertices lie on the incircle. $\blacksquare$