IMO 2011

Key idea: two pair sums are too big to divide the total, so the best possible is $4$. Requiring the other four to divide pins the ratios to a few small integers.

Order the set as $a_1<a_2<a_3<a_4$ with total $s$. A divisor of $s$ that is less than $s$ is at most $\tfrac s2$. Now $a_3+a_4>a_1+a_2$ and $a_2+a_4>a_1+a_3$, so both $a_3+a_4$ and $a_2+a_4$ exceed $\tfrac s2$, and neither divides $s$. So $n_A\le4$.

When $n_A=4$. All of $a_1+a_4$, $a_2+a_3$, $a_1+a_3$, $a_1+a_2$ divide $s$.

• $a_1+a_4$ and $a_2+a_3$ add up to $s$ and both divide $s$, so each is at most $\tfrac s2$: both equal $\tfrac s2$. So $s=2(a_2+a_3)$ and $a_4=a_2+a_3-a_1$.
• $\dfrac{s}{a_1+a_3}=\dfrac{2(a_2+a_3)}{a_1+a_3}$ is strictly between $2$ and $4$, so it is $3$: $a_3=2a_2-3a_1$.
• $\dfrac{s}{a_1+a_2}=\dfrac{2(3a_2-3a_1)}{a_1+a_2}=:k$, an integer less than $6$. Then $a_2(6-k)=a_1(6+k)$. Also $a_3>a_2$ means $a_2>3a_1$, so $\frac{6+k}{6-k}>3$, which gives $k>3$.

For $k=4$: $a_2=5a_1$, $a_3=7a_1$, $a_4=11a_1$. For $k=5$: $a_2=11a_1$, $a_3=19a_1$, $a_4=29a_1$.

Check. $\{1,5,7,11\}$: total $24$, pair sums $6,8,12,12$ all divide $24$. $\{1,11,19,29\}$: total $60$, pair sums $12,20,30,30$ all divide $60$. Scaling by $d$ keeps this.

Key idea: with an orientation, the windmill keeps the same number of points on its right forever. Choose that number to be about half. Then for each direction there is only one possible line, and every point gets its turn as the “middle” point for some direction.

Let $n=|S|$ and $k=\big\lfloor\frac{n-1}2\big\rfloor$. Call a direction generic if no line through two points of $S$ is parallel to it; all but finitely many directions are generic.

The right side is preserved. Give the line an orientation and carry it along as the line turns. Between pivot changes, no point crosses the line. At a pivot change from $P$ to $Q$, put the line along the $x$-axis with $P$ at the origin and $Q=(q,0)$. Just before, the line through $P$ has a small positive angle $\varepsilon$; just after, the line through $Q$ has angle $-\varepsilon$. A short computation shows that $Q$ is on the right of the first line exactly when $q>0$, and $P$ is on the right of the second line exactly when $q>0$. So $Q$ leaves the right side and $P$ takes its place: the number of points on the right never changes.

One line per direction. For a generic oriented direction $\theta$, sort the points by how far they are to the right. Exactly one point $X_\theta$ has exactly $k$ points to its right. So the line in direction $\theta$ through a point of $S$, with exactly $k$ points on its right, is unique: it passes through $X_\theta$.

The windmill. Start on such a line. Then the windmill always has $k$ points on its right. It turns clockwise without stopping. Each turn between pivot changes is positive and at least the smallest gap between the finitely many special directions, so the total turn grows without bound. Whenever its direction is a generic $\theta$, the windmill is the unique line above, so its pivot is $X_\theta$.

Every point is a middle point. Fix $X\in S$ and let $r(\theta)$ be the number of points to the right of the line through $X$ in direction $\theta$. Turning by $180^\circ$ swaps the sides, so $r(\theta+180^\circ)=n-1-r(\theta)$. As $\theta$ turns, $r$ changes by $\pm1$ at a time. One of $r(\theta)$ and $n-1-r(\theta)$ is at most $k$ and the other at least $k$ (check $n$ odd and $n$ even), so $r=k$ on some interval of generic directions. For such $\theta$, $X_\theta=X$.

The windmill passes through direction $\theta$ again and again, and each time its pivot is $X$. So every point of $S$ is a pivot infinitely often.

Key idea: two clever instances of the inequality, added together, show $af(a)\le0$. Then $f$ can’t be positive anywhere, because a line with positive slope would push $f$ negative far to the left.

Put $t=x+y$: the condition is $$f(t)\le(t-x)f(x)+f(f(x))\qquad\text{for all }x,t .\tag{$*$}$$

Step 1: $af(a)\le0$. Apply $(*)$ with $x=a$, $t=f(b)$, and with $x=b$, $t=f(a)$: $$f(f(b))\le(f(b)-a)f(a)+f(f(a)),\qquad f(f(a))\le(f(a)-b)f(b)+f(f(b)).$$ Adding, $0\le2f(a)f(b)-af(a)-bf(b)$. Now take $b=2f(a)$: $0\le-af(a)$. So $f(a)\ge0$ for $a<0$ and $f(a)\le0$ for $a>0$.

Step 2: $f\le0$ everywhere. Suppose $f(x_0)>0$. By $(*)$, $f(t)\le(t-x_0)f(x_0)+f(f(x_0))$, and the right side tends to $-\infty$ as $t\to-\infty$. So $f(t)<0$ for some $t<0$, contradicting Step 1.

Step 3: zero on the negatives. For $x<0$, Step 1 gives $f(x)\ge0$ and Step 2 gives $f(x)\le0$, so $f(x)=0$.

Step 4: $f(0)=0$. Apply $(*)$ with $x=-1$: since $f(-1)=0$, $f(t)\le f(f(-1))=f(0)$ for all $t$. Take $t=-1$: $0\le f(0)$. With Step 2, $f(0)=0$.

Key idea: the lightest weight barely matters. After the first heavier weight is placed, the left pan leads by at least $2$, so the weight $1$ can go anywhere, on either pan. This gives the recursion $f(n)=(2n-1)f(n-1)$.

Let $f(n)$ be the number of ways. Clearly $f(1)=1$. Placing weights $2,4,\dots,2^{n-1}$ is the same problem as placing $1,2,\dots,2^{n-2}$, scaled by $2$, so it has $f(n-1)$ ways.

Signed sums. A sum $\pm2^{e_1}\pm2^{e_2}\pm\dots$ of distinct powers of two is never $0$: the smallest power can’t be cancelled by the larger ones, which are all multiples of twice it. So in a valid placing of the even weights, after the first placement the difference “left minus right” is a positive even number, at least $2$.

Removing the weight 1. In a valid placing of all $n$ weights, look at the even weights alone. At every moment their difference $D$ is the full difference minus $\pm1$, so $D\ge-1$. $D$ is even, so $D\ge0$. So removing the weight $1$ leaves a valid placing of the even weights.

Inserting the weight 1. Conversely, take a valid placing of the even weights, and insert the weight $1$ at step $j$ ($1\le j\le n$).

• If $j=1$, it is the first weight and must go on the left: $1$ way.
• If $j\ge2$, at least one even weight is already placed, so $D\ge2$ at every later moment, and $D\pm1\ge1$. Both pans are fine: $2$ ways.

So each placing of the even weights extends in $1+2(n-1)=2n-1$ ways, and $f(n)=(2n-1)f(n-1)$. Hence $$f(n)=1\cdot3\cdot5\cdots(2n-1).$$

Key idea: all values divide $f(0)$, and $f$ is even. Then three instances of the condition relate $a=f(m)$, $b=f(n)$ and $c=f(n-m)$ tightly enough to force $a\mid b$.

Write $x\mid y$ for divisibility; all values of $f$ are positive.

All values divide $f(0)$. Take $n=0$: $f(m)\mid f(m)-f(0)$, so $f(m)\mid f(0)$.

$f$ is even. Take $m=0$: $f(-n)\mid f(0)-f(n)$. Since also $f(-n)\mid f(0)$, we get $f(-n)\mid f(n)$. Swapping $n$ and $-n$, $f(n)\mid f(-n)$. So $f(-n)=f(n)$.

Three relations. Let $a=f(m)\le b=f(n)$ and $c=f(n-m)=f(m-n)$.

1. The pair $(n,m)$: $c\mid b-a$.
2. The pair $(n,n-m)$: $f(m)\mid f(n)-f(n-m)$, so $a\mid b-c$.
3. The pair $(n-m,-m)$: $f(n)\mid f(n-m)-f(-m)$, so $b\mid c-a$.

Case $c\le b$. Then $|c-a|<b$ (both $a$ and $c$ are between $1$ and $b$), so relation 3 forces $c=a$. Relation 2 becomes $a\mid b-a$, so $a\mid b$.

Case $c>b$. Relation 1: $c$ divides $b-a$, where $0\le b-a<b<c$. So $b-a=0$, and $a=b$ divides $b$.

Either way $f(m)\mid f(n)$.

Key idea: in complex coordinates the corners of the new triangle and its circumcenter are short formulas in $a,b,c$. The distance between the two centers and the two radii then turn out to be three numbers $|u|$, $|y|$, $|u+y|$ built from two real numbers $u,y$, and that forces tangency.

Let $\Gamma$ be the unit circle and $a,b,c$ the vertices, so $\bar a=1/a$, and so on. Turn the picture so that $\ell$ touches $\Gamma$ at $1$; then $\ell$ is the line $z+\bar z=2$. Put $$\sigma_1=a+b+c,\quad\sigma_2=ab+bc+ca,\quad\sigma_3=abc,\quad P=(a+b)(b+c)(c+a)=\sigma_1\sigma_2-\sigma_3 .$$ Then $|\sigma_3|=1$, $\bar\sigma_1=\sigma_2/\sigma_3$ and $\bar\sigma_2=\sigma_1/\sigma_3$. The triangle is acute, so no side is a diameter: $a+b$, $b+c$, $c+a$ and $P$ are nonzero.

The reflected lines. Reflection in line $BC$ is $z\mapsto w=b+c-bc\,\bar z$ (it fixes $b$ and $c$ and reverses orientation). Then $z=b+c-bc\,\bar w$. Putting this into $z+\bar z=2$ and multiplying by $bc$: $$\ell_a:\quad w+b^2c^2\,\bar w=(b+c)(1+bc)-2bc,$$ and $\ell_b$, $\ell_c$ come from cycling $a\to b\to c\to a$.

The corners. Let $A'$ be the meeting point of $\ell_b$ and $\ell_c$. Subtracting their equations, $$a^2(c^2-b^2)\,\bar w=(c-b)\,\big(1+a(b+c)+a^2-2a\big).$$ Divide by $a^2(c-b)(c+b)$, take conjugates and multiply out: $$A'=\frac{\sigma_2-2\sigma_3+a\sigma_3}{b+c},$$ and cyclically for $B'$, $C'$.

The circumcenter. Let $Q=\dfrac{(\sigma_3-\sigma_2)^2}{P}$. Since $(a+b)(a+c)=a^2+\sigma_2$, $$P\,(Q-A')=(\sigma_3-\sigma_2)^2-(\sigma_2-2\sigma_3+a\sigma_3)(a^2+\sigma_2).$$ Expanding, and using $a^2-a\sigma_1+\sigma_2=bc$ (so that $\sigma_3-a^3-a\sigma_2=-a^2\sigma_1$), this equals $-a^2Z$ with $$Z=\sigma_1\sigma_3-2\sigma_3+\sigma_2 .$$ Both $Z$ and $P$ are symmetric in $a,b,c$, so $|Q-A'|=|Q-B'|=|Q-C'|=|Z|/|P|$. So $Q$ is the circumcenter of the new triangle and its radius is $\rho=|Z|/|P|$. (If $Z=0$ the three lines go through one point and there is no triangle.)

Two real numbers. Let $X=\sigma_3-\sigma_2$. Then $\bar X=(1-\sigma_1)/\sigma_3$, that is, $\sigma_1=1-\sigma_3\bar X$. So $$Z=\sigma_3(\sigma_1-1)-X=-\big(X+\sigma_3^2\bar X\big)=\sigma_3\,y,\qquad y=-\Big(\frac X{\sigma_3}+\overline{\Big(\frac X{\sigma_3}\Big)}\Big),$$ and $y$ is real. Also, with $u=|X|^2$, $$P=\sigma_1(\sigma_3-X)-\sigma_3=\sigma_3(\sigma_1-1)-\sigma_1X=Z+\sigma_3|X|^2=\sigma_3\,(u+y).$$ Let $d=|Q|$ be the distance between the centers. Since $|\sigma_3|=1$, $$d\,|P|=u,\qquad \rho\,|P|=|y|,\qquad |P|=|u+y| .$$

Tangency. The real numbers $u\ge0$ and $y$ satisfy $u=(u+y)-y$. So:

• if $y\le0\le u+y$, then $u=|u+y|+|y|$ and $d=1+\rho$: the circles touch from outside;
• if $y>0$, then $u=|u+y|-|y|$ and $d=1-\rho$: the new circle touches $\Gamma$ from inside;
• if $u+y<0$, then $u=|y|-|u+y|$ and $d=\rho-1$: $\Gamma$ touches the new circle from inside.

In every case the circumcircle of the triangle formed by $\ell_a,\ell_b,\ell_c$ is tangent to $\Gamma$.