IMO 2009

Key idea: if the chain closed into a cycle, every term would be congruent to the product of all the terms. Then two different terms would be congruent mod $n$, which is impossible in $\{1,\dots,n\}$.

Suppose $n\mid a_k(a_1-1)$ as well. Then, with indices read cyclically ($a_{k+1}=a_1$), $$a_ja_{j+1}\equiv a_j\pmod n\qquad\text{for every }j .$$ Start from any $a_i$ and use this repeatedly: $$a_i\equiv a_ia_{i+1}\equiv a_ia_{i+1}a_{i+2}\equiv\dots\equiv a_ia_{i+1}\cdots a_{i+k-1}=a_1a_2\cdots a_k\pmod n .$$ Each step multiplies the relation $a_j\equiv a_ja_{j+1}$ by the product of the earlier terms. So every $a_i$ is congruent to the same product. In particular $a_1\equiv a_2\pmod n$, and since both lie in $\{1,\dots,n\}$, $a_1=a_2$. That contradicts that the numbers are distinct.

Key idea: tangency gives a similarity between the midpoint triangle and $APQ$. The resulting ratio says $P$ and $Q$ have the same power with respect to the circumcircle.

Midlines. In triangle $BPQ$, $K$ and $M$ are midpoints of $BP$ and $PQ$, so $MK\parallel BQ$ (which is line $AB$) and $MK=\tfrac12BQ$. In triangle $CQP$, $ML\parallel CP$ (line $AC$) and $ML=\tfrac12CP$.

Similar triangles. $PQ$ is tangent to $\Gamma$ at $M$. By the tangent–chord angle, $\angle(PQ,MK)=\angle MLK$. Since $MK\parallel AQ$, $\angle(PQ,MK)=\angle AQP$. So $\angle MLK=\angle AQP$. In the same way $\angle MKL=\angle APQ$. Hence triangles $MKL$ and $APQ$ are similar, with $M\leftrightarrow A$, $K\leftrightarrow P$, $L\leftrightarrow Q$. By the law of sines, $$\frac{MK}{ML}=\frac{\sin\angle MLK}{\sin\angle MKL}=\frac{\sin\angle AQP}{\sin\angle APQ}=\frac{AP}{AQ}.$$

Powers. Substituting $MK=\tfrac12BQ$ and $ML=\tfrac12CP$ gives $BQ\cdot AQ=CP\cdot AP$. The power of $P$ with respect to the circumcircle is $-PA\cdot PC=OP^2-R^2$, and the power of $Q$ is $-QA\cdot QB=OQ^2-R^2$. These are equal, so $OP=OQ$.

Key idea: the jump between $s_{s_n}$ and $s_{s_{n+1}}$ is a sum of $d_n$ consecutive gaps. Comparing the smallest and the largest gap pins that sum down, and the first gap of each block is a constant. That forces the smallest and largest gaps to be equal.

Let $d_n=s_{n+1}-s_n\ge1$. Let $s_{s_n}=A+nD$ and $s_{s_n+1}=B+nD'$.

Same difference. Since $s$ is increasing, $s_{s_n}<s_{s_n+1}\le s_{s_{n+1}}$, so $A+nD<B+nD'\le A+(n+1)D$ for every $n$. This forces $D=D'$. So $c:=s_{s_n+1}-s_{s_n}=d_{s_n}$ is the same for every $n$.

Gaps are bounded. For integers, $s_j-s_i\ge j-i$ when $j>i$. So $d_n=s_{n+1}-s_n\le s_{s_{n+1}}-s_{s_n}=D$. Let $m=\min d_n$ and $M=\max d_n$; both are attained.

Squeeze. For each $n$, $$D=s_{s_{n+1}}-s_{s_n}=d_{s_n}+d_{s_n+1}+\dots+d_{s_{n+1}-1},$$ a sum of $d_n$ gaps. So $m\,d_n\le D\le M\,d_n$.

• Take $n$ with $d_n=M$: then $D\ge mM$.
• Take $n$ with $d_n=m$: then $D\le Mm$.

So $D=mM$. For an $n$ with $d_n=M$, the sum of $M$ gaps equals $mM$, so all of them equal $m$; in particular $d_{s_n}=m$. For an $n$ with $d_n=m$, all gaps in the block equal $M$, so $d_{s_n}=M$. But $d_{s_n}=c$ for every $n$, so $m=c=M$.

All gaps are equal, so $(s_n)$ is an arithmetic progression.

Key idea: the point $D$ already sees the segment $IK$ at $45^\circ$. Reflecting it onto line $CA$ gives a second point there with that property. So either $E$ is that point, or $E$ is on the same circle, and the power of $C$ turns this into one trigonometric equation.

Let $\beta=\angle B=\angle C$, so $\angle A=180^\circ-2\beta$ and $0<\beta<90^\circ$. Let $a=BC$, $b=CA=AB$, and let $I$ be the incenter of $ABC$, where $AD$ and $BE$ meet. Since the triangle is isosceles, $AD\perp BC$ and $CD=\tfrac a2$.

Where $K$ is. $K$ is the incenter of $ADC$. Its bisector from $C$ is the bisector of the whole angle $C$, so $K$ lies on segment $CI$. Its bisector from $D$ halves the right angle $ADC$, so $\angle IDK=\angle KDC=45^\circ$.

Two points on line $CA$. Reflect $D$ in line $CI$ to get $D'$ on ray $CA$, with $CD'=\tfrac a2$. The reflection fixes $I$ and $K$, so $\angle ID'K=45^\circ$. Also $I$ lies on segment $BE$, so $\angle BEK=\angle IEK$.

The points $X$ on the side of line $CI$ containing $A$ with $\angle IXK=45^\circ$ form an arc of a circle through $I$ and $K$. Line $CA$ meets this arc in at most two points, and $D'$ is one of them. So $\angle BEK=45^\circ$ holds exactly when $E=D'$ or when $E\ne D'$ and $I,K,E,D'$ are concyclic. Since $C,K,I$ lie on a line in this order and $E,D'$ lie on one ray from $C$, “concyclic” is the same as $CK\cdot CI=CE\cdot CD'$ (power of $C$).

Lengths. From the right triangle $CDI$: $CI=\dfrac{a}{2\cos(\beta/2)}$. In triangle $CDK$ the angles are $45^\circ$ at $D$, $\tfrac\beta2$ at $C$, and $135^\circ-\tfrac\beta2$ at $K$, so $CK=\dfrac{(a/2)\sin45^\circ}{\sin(135^\circ-\beta/2)}$. By the bisector theorem, $CE=\dfrac{ab}{a+b}$, and $b=\dfrac{a}{2\cos\beta}$, so $CE=\dfrac{a}{1+2\cos\beta}$.

Case $E=D'$. $\dfrac a{1+2\cos\beta}=\dfrac a2$ gives $\cos\beta=\tfrac12$, $\beta=60^\circ$, $\angle A=60^\circ$.

Case concyclic. $CK\cdot CI=CE\cdot CD'$ becomes $$\frac{\sin45^\circ}{2\sin(135^\circ-\beta/2)\cos(\beta/2)}=\frac1{1+2\cos\beta}.$$ Since $2\sin(135^\circ-\tfrac\beta2)\cos\tfrac\beta2=\sin135^\circ+\sin(135^\circ-\beta)$, this is $$\tfrac{\sqrt2}2+\sqrt2\cos\beta=\tfrac{\sqrt2}2+\tfrac{\sqrt2}2(\cos\beta+\sin\beta)\iff\tan\beta=1 .$$ So $\beta=45^\circ$ and $\angle A=90^\circ$. Here $E\ne D'$, since $\cos45^\circ\ne\tfrac12$.

Each case was an equivalence, so $\angle BEK=45^\circ$ exactly when $\angle CAB$ is $60^\circ$ or $90^\circ$.

Key idea: thin triangles force $f(1)=1$ and $f(f(a))=a$. Then a subadditive bound and injectivity make $f$ linear, and being its own inverse makes it the identity.

Write $T(a,b)$ for the condition that $a$, $f(b)$, $f(b+f(a)-1)$ are the sides of a nondegenerate triangle.

$f(1)=1$. $T(1,b)$ needs $|f(b)-f(b+f(1)-1)|<1$, so $f(b+f(1)-1)=f(b)$. If $f(1)>1$, then $f$ is periodic, so it takes only finitely many values, all at most some $B$. Then $T(2B,b)$ fails, since $2B\ge f(b)+f(\dots)$. So $f(1)=1$.

Involution. $T(a,1)$: the sides are $a$, $1$, $f(f(a))$, so $|a-f(f(a))|<1$ and $f(f(a))=a$. In particular $f$ is a bijection.

Subadditivity. $T(f(a),b)$ has sides $f(a)$, $f(b)$, $f(b+a-1)$, so $$f(a+b-1)<f(a)+f(b),\quad\text{that is,}\quad f(a+b-1)\le f(a)+f(b)-1 .$$

Linear. Let $z=f(2)$. Then $z\ne1$ (since $f(1)=1$ and $f$ is injective), so $z\ge2$, and $f(z)=f(f(2))=2$. Claim: $f\big(j(z-1)+1\big)=j+1$ for all $j\ge0$. It holds for $j=0,1$. If it holds up to $j$, apply subadditivity with $a=j(z-1)+1$ and $b=z$: $$f\big((j+1)(z-1)+1\big)\le(j+1)+2-1=j+2 .$$ The values $1,\dots,j+1$ are already taken at the smaller points $i(z-1)+1$, $i\le j$, and $f$ is injective, so the value is exactly $j+2$.

Applying $f$ to the claim: $f(j+1)=j(z-1)+1$, that is, $f(n)=(n-1)(z-1)+1$ for all $n$. Then $f(f(n))=(n-1)(z-1)^2+1=n$ forces $(z-1)^2=1$, so $z=2$ and $f(n)=n$.

Check. For $f(n)=n$ the sides are $a$, $b$, $a+b-1$, and every triangle inequality holds strictly.

Key idea: strong induction, always looking at the longest jump $A$. The grasshopper is out of trouble as soon as it has passed at least as many forbidden points as it has used jumps, because what is left is a smaller copy of the problem.

Write $s$ for the total. “The claim for $k$” means: for $k$ distinct jump lengths and at most $k-1$ forbidden points, none equal to the total, a safe order exists. Fewer forbidden points only make it easier, and for $k=1$ there are none.

The reduction. Suppose the grasshopper has made $j$ jumps safely and stands at $p\notin M$. The other $n-j$ jumps take it from $p$ to $s$, and only the points of $M$ strictly between $p$ and $s$ matter. If there are at most $n-j-1$ of them, the claim for $n-j$ (with everything shifted by $p$) finishes the walk. This happens whenever at least $j$ points of $M$ lie below $p$.

Let $A$ be the largest jump and $m$ the smallest point of $M$ (if $M$ is empty there is nothing to do). All other jumps are shorter than $A$.

Case 1: $m<A$ and $A\notin M$. Jump $A$ first. The point $m$ is behind, so the reduction works with $j=1$.

Case 2: $m<A$ and $A\in M$. For each of the $n-1$ shorter jumps $a$, look at the start “jump $a$, then jump $A$”. It lands on $a$ and on $a+A$. Call it spoiled if one of these is in $M$. A point $x\in M$ other than $A$ spoils at most one start: if $x<A$ it can equal only one $a$, and if $x>A$ it can equal only one $a+A$. So at most $n-2$ starts are spoiled, and one start is safe. After it the grasshopper stands at $a+A$, with the two points $m$ and $A$ of $M$ behind it, after two jumps. The reduction works with $j=2$.

Case 3: $m\ge A$. Now every point of $M$ is at least $A$. Apply the claim to the $n-1$ shorter jumps (total $s-A$) with the forbidden set $$F=\{x-A:\ x\in M,\ x\ne m\}.$$ These are $n-2$ positive integers, and $s-A\notin F$ because $s\notin M$. We get an order of the short jumps whose landing points $0=q_0<q_1<\dots<q_{n-1}=s-A$ satisfy $q_k\notin F$ for $k\ge1$.

• If $m-A$ is not one of the $q_k$: jump $A$ first, then follow this order. The landing points are $q_k+A$. For $k\ge1$ they miss $M\setminus\{m\}$ because $q_k\notin F$; for $k=0$ the point $A$ could only be in $M$ if $A=m$. None equals $m$, by assumption.
• If $m-A=q_i$: then $i\le n-2$, because $q_{n-1}+A=s\ne m$. Follow the order up to $q_{i+1}$, then jump $A$, then finish the order. The early landing points are at most $q_{i+1}=q_i+(\text{a jump shorter than }A)<m$, so they miss $M$. The later ones are $q_k+A$ with $k\ge i+1$: they miss $M\setminus\{m\}$ as before, and miss $m$ because $q_k\ne q_i$.

The three cases cover everything, so the induction is complete.