IMO 2005

Key idea: the hexagon has $120^\circ$ rotational symmetry. Its center lies on $A_1B_2$, and the rotation carries this line to the other two.

Go around the hexagon counterclockwise (reflect the figure if needed), and let $s$ be the common side length. Name the side vectors $$a=\overrightarrow{A_1A_2},\ x=\overrightarrow{A_2B_1},\ b=\overrightarrow{B_1B_2},\ y=\overrightarrow{B_2C_1},\ c=\overrightarrow{C_1C_2},\ z=\overrightarrow{C_2A_1}.$$

Step 1: $a+b+c=0$. The interior of the hexagon is to the left of each side and lies inside the triangle. So $a$ points along line $BC$ in the direction that has $A$ on its left; likewise $b$ along $CA$ with $B$ on its left, and $c$ along $AB$ with $C$ on its left. If $ABC$ is counterclockwise these are the directions of $\overrightarrow{BC},\overrightarrow{CA},\overrightarrow{AB}$; if clockwise, of their opposites. In both cases $a,b,c$ are the triangle’s side vectors scaled by the same factor, so $a+b+c=0$.

Step 2: $x+y+z=0$, and both triples turn by $120^\circ$. All six vectors add to $0$, so $x+y+z=0$. Three vectors of equal length with sum $0$ form an equilateral triangle, so the angle from one to the next is $120^\circ$ or $240^\circ$.

Now use convexity. Walking around, we turn left at each vertex by an angle strictly between $0^\circ$ and $180^\circ$, and the six turns add up to $360^\circ$. The turn from $a$ to $b$ is the sum of two of them, and the same goes for $b\to c$ and $c\to a$. These three totals are each $120^\circ$ or $240^\circ$ and add to $360^\circ$, so each is $120^\circ$. The same argument works for $x\to y\to z\to x$. So with $\rho_0$ the rotation by $120^\circ$ counterclockwise, $$b=\rho_0(a),\quad c=\rho_0(b),\quad y=\rho_0(x),\quad z=\rho_0(y).$$

Step 3: a symmetry. Let $\rho$ be the rotation by $120^\circ$ counterclockwise, about the point $O$ chosen so that $\rho(A_1)=B_1$. Since $\rho$ turns every vector by $120^\circ$, $$\rho(A_2)=B_1+\rho_0(a)=B_1+b=B_2,\qquad \rho(B_1)=B_2+\rho_0(x)=B_2+y=C_1,$$ and in the same way $\rho(B_2)=C_2$, $\rho(C_1)=A_1$, $\rho(C_2)=A_2$. So $\rho$ maps line $A_1B_2$ to $B_1C_2$, and $B_1C_2$ to $C_1A_2$. It is enough to show that $O$ lies on $A_1B_2$; the rotation then puts $O$ on the other two lines as well.

Step 4: $O$ is on $A_1B_2$. $A_1B_1C_1$ is an equilateral triangle with center $O$, so $O$ lies inside the hexagon. Seen from an interior point of a convex polygon, the vertices appear in order of increasing angle. Say $A_1$, $B_1$, $C_1$ are at angles $\theta$, $\theta+120^\circ$, $\theta+240^\circ$. Then $A_2$ is at an angle strictly between $\theta$ and $\theta+120^\circ$.

Also $A_1A_2=A_2B_1=s$, so $A_2$ is on the perpendicular bisector of $A_1B_1$. That line passes through $O$ in the directions $\theta+60^\circ$ and $\theta+240^\circ$. So $A_2$ is in direction $\theta+60^\circ$ from $O$, and $B_2=\rho(A_2)$ is in direction $\theta+180^\circ$, exactly opposite $A_1$. Hence $O$ lies on segment $A_1B_2$, and the three lines meet at $O$.

Key idea: the first $n$ terms always fill a block of $n$ consecutive integers. Since the sequence goes far up and far down, every integer lands in one of these blocks.

No repeats. If $a_i=a_j$ with $i<j$, the first $j$ terms contain two equal numbers, so they don’t leave $j$ different remainders mod $j$. So all terms are different.

Small spread. Take $i<j\le n$ and let $d=|a_i-a_j|>0$. If $d\ge n$, then $d\ge j$, so $a_i$ and $a_j$ are among the first $d$ terms and leave the same remainder mod $d$. That is not allowed. So $|a_i-a_j|\le n-1$ for all $i,j\le n$.

Blocks. The first $n$ terms are $n$ different integers whose largest and smallest differ by at most $n-1$. So they are exactly $n$ consecutive integers.

Every integer appears. Let $m$ be any integer. The positive terms are infinitely many and all different, so they can’t all be below $m$: some term $a_p\ge m$. In the same way some term $a_q\le m$. Let $n=\max(p,q)$. The first $n$ terms form a block of consecutive integers containing $a_q\le m\le a_p$, so they contain $m$.

Each integer appears at least once, and by the first step at most once.

Key idea: replace each denominator by $x^3(x^2+y^2+z^2)$. This can only lower the term, and afterwards all three terms share the same denominator.

Let $S=x^2+y^2+z^2$.

Step 1: a lower bound for each term. Let $D_1=x^5+y^2+z^2$ and $D_2=x^3S=x^5+x^3(y^2+z^2)$. Then $D_2-D_1=(x^3-1)(y^2+z^2)$, and $$\frac{x^5-x^2}{D_1}-\frac{x^5-x^2}{D_2}=\frac{(x^5-x^2)(D_2-D_1)}{D_1D_2}=\frac{x^2(x^3-1)^2(y^2+z^2)}{D_1D_2}\ \ge0 .$$ So $$\frac{x^5-x^2}{x^5+y^2+z^2}\ \ge\ \frac{x^5-x^2}{x^3S}=\frac{x^2-\frac1x}{S}\ \ge\ \frac{x^2-yz}{S},$$ where the last step uses $\frac1x\le yz$, which is $xyz\ge1$.

Step 2: add. Doing the same for $y$ and $z$ and adding, $$\text{sum}\ \ge\ \frac{x^2+y^2+z^2-xy-yz-zx}{S}=\frac{(x-y)^2+(y-z)^2+(z-x)^2}{2S}\ \ge0 .$$

Key idea: every prime divides some term, so no number above $1$ is coprime to all of them. The index $n=p-2$ works for every prime $p\ge5$.

Write $a_n=2^n+3^n+6^n-1$. We have $a_1=10$ and $a_2=48$, so $2$ and $3$ divide terms.

Let $p\ge5$ be prime. By Fermat, $2^{p-1}\equiv3^{p-1}\equiv6^{p-1}\equiv1\pmod p$. So $$6a_{p-2}=3\cdot2^{p-1}+2\cdot3^{p-1}+6^{p-1}-6\equiv3+2+1-6=0\pmod p .$$ Since $p\nmid6$, we get $p\mid a_{p-2}$.

So every prime divides some term. A positive integer coprime to every term has no prime factor: it is $1$. And $1$ is coprime to everything.

Key idea: a single rotation carries side $BC$ onto side $DA$, and it carries $E$ to $F$ for every position. Its center $X$ doesn’t depend on $E$, and it lies on every circle $PQR$.

We use directed angles between lines, written $\angle(m,n)$ and taken mod $180^\circ$.

The rotation. The segments $BC$ and $DA$ have the same length and are not parallel. So there is a rotation $\rho$, with some center $X$ and angle $\theta\ne0$, taking $B\mapsto D$ and $C\mapsto A$. It takes the point of $BC$ at distance $t$ from $B$ to the point of $DA$ at distance $t$ from $D$. So $\rho(E)=F$ for every allowed $E$, and $X$ is the same point every time.

Similar triangles. The triangles $XBD$, $XEF$, $XCA$ are isosceles ($XB=XD$, etc.), with apex angle $\theta$ at $X$ and the same orientation. So they are similar, and their base angles match: $$\angle(BX,BD)=\angle(EX,EF)=\angle(CX,CA).$$

$X$ is on two circles. Recall $P=AC\cap BD$, $Q=BD\cap EF$, $R=EF\cap AC$.

• Circle $BCP$: $\angle(BX,BP)=\angle(BX,BD)=\angle(CX,CA)=\angle(CX,CP)$, so $X,B,C,P$ are concyclic.
• Circle $BEQ$: $\angle(BX,BQ)=\angle(BX,BD)=\angle(EX,EF)=\angle(EX,EQ)$, so $X,B,E,Q$ are concyclic.

$X$ is on circle $PQR$. Using these two circles, and that $B,E,C$ lie on one line, $$\angle(PX,PR)=\angle(PX,PC)=\angle(BX,BC)=\angle(BX,BE)=\angle(QX,QE)=\angle(QX,QR).$$ So $X,P,Q,R$ are concyclic.

$X\ne P$. If $X=P$, then $PB=PD$ and $PC=PA$, so the diagonals of $ABCD$ bisect each other and $ABCD$ is a parallelogram. Then $BC\parallel DA$, which is excluded.

So every circle $PQR$ passes through the fixed point $X\ne P$.

Key idea: double counting leaves almost no slack. If only one contestant solved five problems, the numbers fit only in a very rigid way, and a count mod $3$ breaks it.

Let $N$ be the number of contestants and $s_i$ the number of problems contestant $i$ solved, so $s_i\le5$. For a pair of problems let $c$ be the number of contestants who solved both; we know $5c\ge2N+1$. Counting pairs (contestant, two problems they solved): $$\sum_i\binom{s_i}2=\sum_{\text{pairs}}c\ \ge\ 15\cdot\frac{2N+1}5=6N+3 .$$

At least one solved five. If $s_i\le4$ for all $i$, the left side is at most $6N$. So someone solved five.

Suppose exactly one did. Call this contestant $X$, and let $p$ be the problem $X$ missed. Then $\sum\binom{s_i}2\le10+6(N-1)=6N+4$. Let $m$ be the least integer with $5m\ge2N+1$, so $15m\le6N+4$. Write $N=5k+r$ with $0\le r\le4$:

So $N=5k+2$, every pair count is at least $2k+1$, and $30k+15\le\sum c\le30k+16$.

Rigid structure. If some contestant other than $X$ solved at most three problems, then $\sum\binom{s_i}2\le10+6(N-2)+3=30k+13$, too small. So everyone except $X$ solved exactly four, and $\sum c=10+6(N-1)=30k+16$. Since each of the $15$ pair counts is at least $2k+1$, exactly one pair has count $2k+2$ and the rest have $2k+1$.

Count around one problem. For a problem $q$, let $\Sigma_q$ be the sum of the five pair counts involving $q$. Then $\Sigma_q$ is $10k+5$, or $10k+6$ if $q$ is in the special pair. Also $\Sigma_q$ counts, over the solvers of $q$, the number of other problems they solved.

• For $q\ne p$: $X$ contributes $4$ and each other solver contributes $3$, so $\Sigma_q\equiv1\pmod3$. At least three of the five problems $q\ne p$ are outside the special pair, so $10k+5\equiv1$, which gives $k\equiv2\pmod3$.
• For $q=p$: $X$ didn’t solve $p$, and each solver contributes $3$, so $\Sigma_p\equiv0\pmod3$. But with $k\equiv2$, we get $10k+5\equiv1$ and $10k+6\equiv2\pmod3$.

That is a contradiction. So at least two contestants solved exactly five problems.