IMO 2015

Key idea: regular polygons with an odd number of sides do everything. For even $n$, a counting argument shows that some point would have to be equally far from three others.

(a), odd $n$. Take a regular $n$-gon. For two vertices $A,B$, the perpendicular bisector of $AB$ is a mirror line of the polygon, and for an odd polygon every mirror line passes through exactly one vertex $C$. Then $CA=CB$.

(a), even $n\ge4$. Let $O$ be the center of a unit circle, and use angles on that circle. Take the points at $0^\circ$, $60^\circ$, $120^\circ$, and, for $m=\frac{n-4}2$ different angles $\theta_1,\dots,\theta_m$ in $(120^\circ,180^\circ)$, the points at $\theta_j$ and $\theta_j+60^\circ$. Together with $O$, that is $1+3+2m=n$ points, all different.

• Two points on the circle: $O$ is equally far from both.
• $O$ and a circle point $A$: every circle point has another circle point $B$ exactly $60^\circ$ away (the triple $0^\circ,60^\circ,120^\circ$ and the pairs $\theta_j,\theta_j+60^\circ$ are chosen for this). Then $OAB$ is equilateral, so $BO=BA$.

(b), odd $n$ works. In the regular $n$-gon, a point equally far from three vertices is the center of the circle through them, which is the polygon’s center, not a vertex. So the set is centre-free.

(b), even $n$ fails. Suppose $S$ is balanced and centre-free with $|S|=n$. For each $C\in S$, group the other $n-1$ points by their distance from $C$. Centre-free means each group has at most $2$ points, so $C$ is equally far from the two points of at most $\big\lfloor\frac{n-1}2\big\rfloor$ pairs. Balanced means every one of the $\binom n2$ pairs is served by some $C$. So $$\frac{n(n-1)}2\le n\Big\lfloor\frac{n-1}2\Big\rfloor .$$ For even $n$ the right side is $\frac{n(n-2)}2$, which is smaller. Contradiction.

Key idea: sort the numbers. The middle power of two divides the sum and the difference of the two larger ones, and those factor nicely. Since $c-1$ and $c+1$ share at most one factor $2$, almost all of that power of two has to sit in $a+b$ or in $b-a$, which forces $a$ to be tiny.

Permuting $a,b,c$ only permutes the three expressions, so let $a\le b\le c$. Put $$ab-c=2^p,\qquad ac-b=2^q,\qquad bc-a=2^r .$$ Since $(ac-b)-(ab-c)=(c-b)(a+1)\ge0$ and $(bc-a)-(ac-b)=(b-a)(c+1)\ge0$, we have $p\le q\le r$.

$a\ge2$. If $a=1$, then $b-c\ge1$, against $b\le c$.

The case $a=b$. Then $ac-b=bc-a=a(c-1)$, so $a=2^s$ with $s\ge1$ and $c=2^t+1$. The first expression is $4^s-2^t-1$.

• If it is even, $2^t$ is odd, so $t=0$, $c=2$, and $4^s-2=2(2^{2s-1}-1)$ is a power of two only for $s=1$. This gives $(2,2,2)$.
• Otherwise it is an odd power of two, so it equals $1$. Then $2^t(2^{2s-t}-1)=2$, so $t=1$ and $s=1$. This gives $(2,2,3)$.

From now on $a<b$. Because $q\le r$, the power $2^q$ divides $$2^r+2^q=(a+b)(c-1)\qquad\text{and}\qquad 2^r-2^q=(b-a)(c+1).$$

• $c$ even. Then $c\pm1$ are odd, so $2^q$ divides $b-a>0$, and $2^q\le b-a<b$. But $2^q=ac-b\ge2c-b\ge b$. So $c$ is odd.
• $c\equiv1\pmod 4$. Then $c+1$ has just one factor $2$, so $2^{q-1}$ divides $b-a$, and $2(b-a)\ge ac-b\ge ab-b$. This gives $3b>ab$, so $a=2$.
• $c\equiv3\pmod 4$. Then $c-1$ has just one factor $2$, so $2(a+b)\ge 2^q=ac-b$, that is, $ac\le 2a+3b$. With $c\ge b$ this gives $(a-3)(b-2)\le6$, which leaves $a=2$, $a=3$, or $a=4$ with $b\le8$.

Also, $c=b$ is now impossible: $c$ is odd, and $ab-c=b(a-1)$ would be a power of two with an odd factor $b\ge3$.

$a=2$. Then $2b-c$ is odd, so $2b-c=1$ and $c=2b-1$. Next, $2c-b=3b-2$ is a power of two at least $4$, so $b$ is even; write $b=2m$ with $m\ge2$. Then $3m-1=2^s$ and $bc-2=2(4m^2-m-1)$, so $4m^2-m-1$ is a power of two. It is odd for even $m$ (and then would have to be $1$, which fails), so $m$ is odd. Substituting $m=\frac{2^s+1}3$, $$9(4m^2-m-1)=4^{s+1}+5\cdot2^s-8 .$$ For $s\ge4$ the right side is $8$ times an odd number and much bigger than $72$, so it is not $9$ times a power of two. Checking $s\le3$: only $s=3$ gives an integer $m\ge2$, namely $m=3$. So $b=6$, $c=11$, and indeed $12-11=1$, $22-6=16$, $66-2=64$.

$a=3$. Now $c\equiv3\pmod4$, since the other case forced $a=2$. From $3c\le6+3b$ and $b<c$: $c=b+1$ or $c=b+2$. If $c=b+1$, then $3b-c=2b-1$ is odd and larger than $1$. If $c=b+2$, the three numbers are $2(b-1)$, $2(b+3)$ and $(b-1)(b+3)$. Two powers of two that differ by $4$ are $4$ and $8$, so $b=5$, $c=7$, and $15-7=8$, $21-5=16$, $35-3=32$.

$a=4$. Again $c\equiv3\pmod4$, so $5\le b\le8$ and $b<c\le\frac{8+3b}4$, which is never possible.

So the sorted solutions are $(2,2,2)$, $(2,2,3)$, $(2,6,11)$, $(3,5,7)$, and the answer is all their rearrangements.

Key idea: an inversion centred at $H$ turns the circle on $HQ$ into a straight line through $M$, and the other circle into a circle through $A$ and $Q$. The new tangency follows from one right angle in the nine-point circle.

The line through $Q$. Let $A'$ be the point of $\Gamma$ opposite $A$. Since $\angle AQH=90^\circ=\angle AQA'$, the points $Q,H,A'$ are collinear. It is well known that $BHCA'$ is a parallelogram (both $BH$ and $A'C$ are perpendicular to $AC$, and both $CH$ and $A'B$ to $AB$), so $M$ is the midpoint of $HA'$. So $Q,H,M,A'$ lie on one line, with $H$ between $Q$ and $M$, because $H$ is inside $\Gamma$.

The map. For a point $X\ne H$, let $X^*$ be the point on line $XH$, on the other side of $H$, with $HX\cdot HX^*=HA\cdot HF$. (This is an inversion followed by a reflection through $H$; it keeps circles and lines as circles and lines, and keeps tangency.)

• $A^*=F$, because $H$ lies between $A$ and $F$.
• If $B_1,C_1$ are the feet of the altitudes from $B$ and $C$, then $HB\cdot HB_1=HA\cdot HF$ (the four points $A,B,F,B_1$ lie on the circle with diameter $AB$), so $B^*=B_1$, and likewise $C^*=C_1$. Hence $\Gamma^*$ is the circle $FB_1C_1$, the nine-point circle $\omega$.
• The power of $H$ with respect to $\Gamma$ gives $HQ\cdot HA'=HA\cdot 2HF$, since the reflection of $H$ in $BC$ lies on $\Gamma$. With $HA'=2HM$ this says $HQ\cdot HM=HA\cdot HF$, so $Q^*=M$.

The images of the two circles. The circle $KQH$ has diameter $HQ$, because $\angle HKQ=90^\circ$. It passes through $H$, so its image is a line: the line $\ell$ through $Q^*=M$ perpendicular to $HQ$. The point $K$ is on $\Gamma$ and on this circle, so $K^*$ is the second point where $\ell$ meets $\omega$. The circle $FKM$ goes to the circle through $A$, $K^*$ and $Q$. So we must show:

the line $\ell=MK^*$ is tangent to the circle $AQK^*$ at $K^*$.

(The points $A,Q,K^*$ are not collinear: line $AQ$ is perpendicular to $QM$ at $Q$, and $\ell$ is a different line perpendicular to $QM$, so they don’t meet.)

The tangency. Let $U$ be the midpoint of $AH$. In the nine-point circle, $UM$ is a diameter (the angle $UFM$ is right). Since $K^*$ is on $\omega$, the line through $K^*$ perpendicular to $\ell$ passes through $U$. (If $K^*=U$ this is clear too.) Since $\ell\perp QM$, that line is the line through $U$ parallel to $QM$.

On the other hand, triangle $AQH$ has a right angle at $Q$, so $U$ is its circumcentre and $UA=UQ$. So the perpendicular bisector of $AQ$ is the line through $U$ perpendicular to $AQ$, which is again the line through $U$ parallel to $QM$.

So the centre of the circle $AQK^*$ lies on the line through $K^*$ perpendicular to $\ell$. A line through a point of a circle that is perpendicular to the radius there is the tangent. So $\ell$ touches the circle $AQK^*$ at $K^*$. Mapping back, the circles $KQH$ and $FKM$ are tangent at $K$.

Key idea: the whole figure is nearly symmetric about $AO$. Lines $FK$ and $GL$ make equal and opposite angles with $FG$, so they are reflections of each other in $AO$, and their meeting point lies on the mirror.

Write $\angle(m,n)$ for the directed angle from line $m$ to line $n$, taken modulo $180^\circ$. Recall that four points $P,Q,R,S$ lie on a circle exactly when $\angle(RP,RQ)=\angle(SP,SQ)$. Call the circle about $A$ simply $\Gamma$.

The mirror. $AF=AG$ (radii of $\Gamma$) and $OF=OG$ (radii of $\Omega$), so $AO$ is the perpendicular bisector of $FG$. Reflection $\sigma$ in $AO$ swaps $F$ and $G$, maps line $FG$ to itself, and reverses directed angles.

Angle at $F$. Using the circle $BDFK$ (with $K$ on $AB$) and then $\Gamma$ (through $D,E,F,G$, with $E$ on $BC$): $$\angle(FK,FG)=\angle(FK,FD)+\angle(FD,FG)=\angle(BA,BC)+\angle(BC,EG)=\angle(AB,EG).$$ Angle at $G$. In the same way, with the circle $CGEL$: $$\angle(GF,GL)=\angle(GF,GE)+\angle(GE,GL)=\angle(DF,BC)+\angle(BC,CA)=\angle(DF,AC).$$

These are equal. Let $h$ be the line through $A$ perpendicular to $BC$. It is the perpendicular bisector of the chord $DE$ of $\Gamma$, and $AO$ is the perpendicular bisector of the chord $FG$. A standard fact is that $h$ and $AO$ are mirror images in the bisector of angle $A$, so $\angle(AB,h)=\angle(AO,AC)$. Then $$\angle(AB,EG)-\angle(DF,AC)=\angle(AB,h)+\angle(h,EG)+\angle(AC,AO)+\angle(AO,DF)=\angle(h,EG)+\angle(AO,DF).$$ Since $h\perp DE$ and $AO\perp FG$, $$\angle(h,EG)+\angle(AO,DF)=\big(90^\circ+\angle(ED,EG)\big)+\big(90^\circ+\angle(FG,FD)\big)=\angle(ED,EG)-\angle(FD,FG)=0,$$ the last step because $D,E,F,G$ lie on $\Gamma$. So $\angle(FK,FG)=\angle(GF,GL)$.

Conclusion. $\sigma(FK)$ is a line through $G$ with $\angle(\sigma(FK),GF)=-\angle(FK,FG)=-\angle(GF,GL)=\angle(GL,GF)$. A line through $G$ is fixed by its angle with $GF$, so $\sigma(FK)=GL$, and likewise $\sigma(GL)=FK$. So $\sigma$ maps the single common point $X$ of the two different lines to itself, and a point fixed by a reflection lies on its mirror. Hence $X$ lies on $AO$.

Directed angles make the argument independent of the shape of the picture.

Key idea: setting $y=1$ produces many fixed points of $f$. When $f(0)\ne0$ every fixed point must be $1$, which pins $f$ down at once. When $f(0)=0$, the fixed points let us prove $f$ is odd, and then two substitutions finish.

Both answers work: for $f(x)=x$ both sides equal $2x+y+xy$, and for $f(x)=2-x$ both sides equal $2+y-xy$.

Write $P(x,y)$ for the equation and $c=f(0)$.

Fixed points. $P(x,1)$ gives $f\big(x+f(x+1)\big)=x+f(x+1)$, so $$x+f(x+1)\ \text{is a fixed point of } f \text{ for every } x. \tag{1}$$

The value $c$. $P(0,0)$ gives $f(c)=0$. $P(0,y)$ gives $f(f(y))=f(y)+(y-1)c$. With $y=c$ this is $c=c^2-c$, so $c=0$ or $c=2$. Also, if $f(t)=t$, then $P(0,t)$ gives $t=t+(t-1)c$, so $(t-1)c=0$.

Case $c=2$. Every fixed point equals $1$, so by (1) $x+f(x+1)=1$ for all $x$, that is, $f(u)=2-u$.

Case $c=0$. Then:

• $P(x,0)$ gives $f\big(x+f(x)\big)=x+f(x)$, so $x+f(x)$ is a fixed point for every $x$.
• $P(-1,1)$ gives $f(-1)=-1$, and then $P(1,-1)$ gives $f(1)-1=1-f(1)$, so $f(1)=1$.
• $P(1,y)$ now reads $$f\big(1+f(y+1)\big)+f(y)=1+f(y+1)+y. \tag{2}$$ If $t$ and $t+1$ are both fixed points, (2) with $y=t$ gives $f(t+2)=t+2$.

For any $x$, the numbers $t=x+f(x+1)$ (by (1)) and $t+1=(x+1)+f(x+1)$ (by the first bullet) are fixed points. So $x+f(x+1)+2$ is a fixed point for every $x$; replacing $x$ by $x-2$, so is $x+f(x-1)$.

$f$ is odd. $P(x,-1)$ gives $f\big(x+f(x-1)\big)+f(-x)=x+f(x-1)-f(x)$. The first term equals $x+f(x-1)$, so $f(-x)=-f(x)$.

Finish. $P(-1,-y)$ gives $f\big(-1+f(-1-y)\big)+f(y)=-1+f(-1-y)+y$. By oddness this is $$-f\big(1+f(1+y)\big)+f(y)=-1-f(1+y)+y .$$ Adding (2) gives $2f(y)=2y$. So $f(x)=x$.

Key idea: read the sequence as a juggling pattern. Eventually there are exactly $b$ balls, and the partial sums of $a_j-b$ are, up to a constant, the total “time left in the air” of the balls. That total can only move inside a window of width at most $1007^2$.

Pending landing times. For $t\ge0$ let $S_t$ be the set of numbers $j+a_j$ with $j\le t$ and $j+a_j>t$: the landing times, after time $t$, of balls thrown so far. So $S_0=\varnothing$ and $$S_t=\big(S_{t-1}\setminus\{t\}\big)\cup\{t+a_t\}.$$ By condition (ii), $t+a_t$ is not already in $S_{t-1}$. So $|S_t|=|S_{t-1}|$ if $t\in S_{t-1}$ (a ball lands and is thrown again), and $|S_t|=|S_{t-1}|+1$ otherwise (a new ball). Also $S_t\subseteq\{t+1,\dots,t+2015\}$ by condition (i), so $|S_t|\le2015$.

A non-decreasing bounded sequence of integers is eventually constant: there are $N\ge1$ and $b$ with $|S_t|=b$ for all $t\ge N$, and $b\ge1$ because $S_t$ contains $t+a_t$. Then $t\in S_{t-1}$ for every $t>N$.

The partial sums. For $t>N$, the update removes $t$ and adds $t+a_t$, so $\Sigma S_t=\Sigma S_{t-1}+a_t$, where $\Sigma S$ is the sum of the elements. Put $$g(t)=\sum_{s\in S_t}(s-t)=\Sigma S_t-bt .$$ Then $g(t)-g(t-1)=a_t-b$ for $t>N$, and so for $n>m\ge N$ $$\sum_{j=m+1}^{n}(a_j-b)=g(n)-g(m).$$

The window. Fix $t\ge N$. The set $\{s-t:s\in S_t\}$ has $b$ different elements of $\{1,\dots,2015\}$, and it contains $1$ because $t+1\in S_t$. So $g(t)$ is $1$ plus the sum of $b-1$ different numbers from $\{2,\dots,2015\}$, and $$1+(2+3+\dots+b)\ \le\ g(t)\ \le\ 1+\big(2015+2014+\dots+(2017-b)\big).$$ The difference between the bounds is $$\sum_{i=0}^{b-2}\big((2015-i)-(2+i)\big)=(b-1)(2015-b)\le\Big(\frac{2014}2\Big)^2=1007^2,$$ by AM–GM, since $(b-1)+(2015-b)=2014$.

So $|g(n)-g(m)|\le1007^2$, which is the claim with this $b$ and $N$.