IMO 2012

Key idea: $F$ is the foot of the perpendicular from $A$ to the external bisector $BJ$. Reflecting in $BJ$ then sends $A$ to $S$, so $BS=BA$, and $MS$ works out to the semiperimeter. The same holds for $MT$.

Let $a,b,c$ be the sides and $s$ the semiperimeter. Tangent lengths from a point to a circle are equal, so $AK=AL=s$, $BK=BM=s-c$ and $CL=CM=s-b$.

Step 1: $F$ is on the circle with diameter $AJ$. The angles $AKJ$ and $ALJ$ are right angles, so $K$ and $L$ lie on the circle $\omega$ with diameter $AJ$. Now look at the excircle. The inscribed angle $\angle KLM$ is half the central angle $\angle KJM$. Since $BK$ and $BM$ are the two tangents from $B$, the line $JB$ bisects $\angle KJM$. So $$\angle KLF=\angle KLM=\tfrac12\angle KJM=\angle KJB=\angle KJF .$$ The segment $KF$ is seen from $L$ and from $J$ at the same angle, so $K,F,J,L$ are concyclic. That circle is $\omega$ (it passes through $K,J,L$). Hence $\angle AFJ=90^\circ$: $AF\perp BJ$.

Step 2: $S$ is the reflection of $A$. $BJ$ is the external bisector at $B$: it bisects the angle between ray $BM$ (toward $C$) and ray $BK$ (the extension of $AB$ beyond $B$). So the reflection in $BJ$ swaps the lines $BA$ and $BC$, and sends $A$ to the point $A'$ of line $BC$ with $BA'=BA=c$, on the far side of $B$ from $M$. Because $AF\perp BJ$ with $F$ on $BJ$, the point $A'$ lies on line $AF$. So $A'$ is where line $AF$ meets $BC$, that is, $A'=S$. Then $$MS=MB+BS=(s-c)+c=s .$$

Step 3: same for $T$. The same argument with $C$, $G$, $L$, $K$ in place of $B$, $F$, $K$, $L$ gives $MT=(s-b)+b=s$, with $T$ on the other side of $M$.

So $MS=MT$, and $M$ is the midpoint of $ST$.

Key idea: a weighted AM–GM on each factor produces constants that telescope to exactly $n^n$, and the product of the $a_k$ disappears because it is $1$.

For each $k\ge2$, write $1+a_k$ as the sum of $k$ numbers: $k-1$ copies of $\frac1{k-1}$ and one $a_k$. By AM–GM, $$1+a_k\ \ge\ k\,\sqrt[k]{\frac{a_k}{(k-1)^{k-1}}},\qquad\text{so}\qquad(1+a_k)^k\ \ge\ \frac{k^k}{(k-1)^{k-1}}\,a_k .$$ Multiply over $k=2,\dots,n$. The constants telescope: $$\prod_{k=2}^n\frac{k^k}{(k-1)^{k-1}}=\frac{n^n}{1^1}=n^n,$$ and $\prod a_k=1$. So the product is at least $n^n$.

Strict. Equality would need $a_k=\frac1{k-1}$ for every $k$ (all numbers in each AM–GM equal). Then $\prod a_k=\frac1{(n-1)!}<1$ for $n\ge3$, which is not allowed. So the inequality is strict.

Key idea: in part 1, a “yes” followed by $k$ binary questions makes one candidate impossible, because it would need $k+1$ lies in a row. In part 2, A answers greedily to keep a weighted count of lie runs below a threshold, so that no candidate is ever ruled out.

Part 1. It is enough to show: whenever B knows that $x$ is in a set $T$ with more than $2^k$ elements, he can find an element of $T$ that is surely not $x$. Repeating this (each round uses finitely many questions) shrinks the set of candidates to at most $2^k\le n$ numbers, and B names them.

Take $2^k+1$ elements of $T$: one special element $e$ and $2^k$ others, labeled by the $2^k$ binary strings of length $k$. B asks “is $x=e$?” over and over.

• If A says “no” $k+1$ times in a row, one of these answers is true, so $x\ne e$.
• Otherwise A says “yes” at some point. Right after it, B asks $k$ questions: the $j$-th asks whether $x$ is among the elements whose label has digit $1$ in place $j$. Let $u$ be the element whose label disagrees with all $k$ answers. If $x$ were $u$, then the “yes” (as $u\ne e$) and the $k$ answers after it would be $k+1$ lies in a row. So $x\ne u$.

Either way one candidate is ruled out.

Part 2. Let $N=n+1$ and fix $\lambda$ with $1<\lambda<2$. At each moment of the game and for each $i\in\{1,\dots,N\}$, let $m_i$ be the number of most recent answers in a row that would be false if $x$ were $i$. If A can keep every $m_i\le k$, B cannot win: whatever $n$ numbers he names, some $i\le N$ is missing, and A could have chosen $x=i$ at the start and given exactly the same answers legally.

A keeps $\Phi=\sum_i\lambda^{m_i}$ small. For a question $S$, let $p=\sum_{i\in S}\lambda^{m_i}$ and $q=\sum_{i\notin S}\lambda^{m_i}$, so $p+q=\Phi$. A “yes” resets the runs of $i\in S$ to $0$ and lengthens the others by one, giving $\Phi_{\text{yes}}=|S|+\lambda q$. A “no” gives $\Phi_{\text{no}}=(N-|S|)+\lambda p$. A picks the smaller, so the new value is at most $$\tfrac12\big(\Phi_{\text{yes}}+\Phi_{\text{no}}\big)=\tfrac12\big(N+\lambda\Phi\big).$$ Now suppose $N\le(2-\lambda)\lambda^{k+1}$. At the start $\Phi=N<\lambda^{k+1}$. And if $\Phi<\lambda^{k+1}$, the next value is less than $\tfrac12\big((2-\lambda)\lambda^{k+1}+\lambda^{k+2}\big)=\lambda^{k+1}$. So $\Phi<\lambda^{k+1}$ for the whole game, which forces every $m_i\le k$.

Finally take $\lambda=1.995$ and $n=\lceil1.99^k\rceil$. Then $N\le1.99^k+2$, while $$(2-\lambda)\lambda^{k+1}=0.005\cdot1.995\cdot1.995^k,$$ and $(1.995/1.99)^k\to\infty$. So for all large $k$ the condition holds, and with this $n\ge1.99^k$ B cannot be sure to win.

Key idea: the rule says $f(a+b)$ is a root of a quadratic with roots $f(a)+f(b)\pm2\sqrt{f(a)f(b)}$. Starting from $k=f(1)$, the first few values split into three branches, and each branch is then forced.

Basics. $(0,0,0)$: $3f(0)^2=6f(0)^2$, so $f(0)=0$. $(a,-a,0)$: $(f(a)-f(-a))^2=0$, so $f$ is even. Using $(a,b,-a-b)$ and evenness, the rule is a quadratic in $f(a+b)$: $$f(a+b)^2-2\big(f(a)+f(b)\big)f(a+b)+\big(f(a)-f(b)\big)^2=0,$$ whose roots are $f(a)+f(b)\pm2\sqrt{f(a)f(b)}$ (the discriminant $4f(a)f(b)$ is $\ge0$ since a root exists). $\quad(\dagger)$

Let $k=f(1)$. If $k=0$, then $(\dagger)$ with $b=1$ gives $f(n+1)=f(n)$, so $f\equiv0$ (which is $kx^2$ with $k=0$). From now on $k\ne0$.

$f(2)$. $(\dagger)$ with $a=b$: $f(2a)\in\{0,4f(a)\}$. So $f(2)\in\{0,4k\}$.

Branch $f(2)=0$. $(\dagger)$ with $b=2$: $f(n+2)=f(n)$. So $f$ is $k$ on odd numbers and $0$ on even numbers.

Branch $f(2)=4k$. $(\dagger)$ with $(a,b)=(2,1)$: $f(3)=5k\pm4k\in\{k,9k\}$. Also $f(4)\in\{0,4f(2)\}=\{0,16k\}$, and $(\dagger)$ with $(3,1)$ gives $f(4)=f(3)+k\pm2\sqrt{kf(3)}$.

• If $f(3)=k$: $f(4)\in\{0,4k\}$, so $f(4)=0$. Then $(\dagger)$ with $b=4$ gives $f(n+4)=f(n)$: the values are $0,k,4k,k$ by residue mod $4$.
• If $f(3)=9k$: $f(4)\in\{4k,16k\}$, so $f(4)=16k$. Now suppose $f(j)=kj^2$ for $j\le n$, with $n\ge4$. $(\dagger)$ with $(n,1)$ gives $f(n+1)\in\{k(n+1)^2,k(n-1)^2\}$, and with $(n-1,2)$ gives $f(n+1)\in\{k(n+1)^2,k(n-3)^2\}$. Since $(n-1)^2\ne(n-3)^2$ for $n\ne2$, $f(n+1)=k(n+1)^2$. So $f(x)=kx^2$.

Check. Each of the three families satisfies the rule for every zero-sum triple: for $kx^2$ this is the identity $\sum a^4=2\sum a^2b^2$ when $a+b+c=0$, and for the two periodic families it is a finite check of residues.

Key idea: $K$ and $L$ lie on one circle $\Gamma$ to which $AL$ and $BK$ are both tangent. Then $MK$ and $ML$ are the two tangent segments from $M$ to $\Gamma$.

Let $\omega_A$ be the circle with center $A$ through $C$, and $\omega_B$ the circle with center $B$ through $C$. Then $L\in\omega_A$ and $K\in\omega_B$.

Tangents at $C$. $\angle ACB=90^\circ$, so $AC$ is tangent to $\omega_B$ at $C$, and $BC$ is tangent to $\omega_A$ at $C$. Hence the power of $A$ with respect to $\omega_B$ is $AC^2$, and the power of $B$ with respect to $\omega_A$ is $BC^2$.

The common chord. The two circles meet at $C$ and at its reflection $C'$ in line $AB$. So their radical axis is line $CC'$, which is line $CD$. The point $X$ is on it, so it has the same power with respect to both circles.

A circle through four points. Let line $AX$ meet $\omega_B$ at $K$ and $K'$, and line $BX$ meet $\omega_A$ at $L$ and $L'$. Then $$XK\cdot XK'=\operatorname{pow}_{\omega_B}(X)=\operatorname{pow}_{\omega_A}(X)=XL\cdot XL' .$$ So $K,K',L,L'$ lie on one circle $\Gamma$ (converse of the power of a point).

Two tangents. $A$ lies on line $KK'$, so its power with respect to $\Gamma$ is $AK\cdot AK'$, which is its power with respect to $\omega_B$, namely $AC^2=AL^2$. Since $L\in\Gamma$, the line $AL$ meets $\Gamma$ at $L$ and at a point $L^*$ with $AL\cdot AL^*=AL^2$, so $L^*=L$. That means $AL$ is tangent to $\Gamma$ at $L$. In the same way, $B$ has power $BL\cdot BL'=BC^2=BK^2$, so $BK$ is tangent to $\Gamma$ at $K$.

Finish. $M$ is where the tangents at $K$ and $L$ meet. Two tangent segments from one point to a circle are equal, so $MK=ML$.

Key idea: the parity of the second equation gives the condition. For the construction, any term can be split in two without changing either sum, and six simple splitting moves add eight new labels at once.

Necessity. Let $A$ be the largest $a_k$. Multiplying the second equation by $3^A$ gives $\sum_k k\cdot3^{A-a_k}=3^A$. Powers of $3$ are odd, so mod $2$ this says $1+2+\dots+n\equiv1$, that is, $\frac{n(n+1)}2$ is odd. That happens exactly when $n\equiv1$ or $2\pmod4$.

The splitting move. Think of label $k$ with exponent $a_k$ as a token of value $k$ at depth $a_k$. Replace a token of value $v$ at depth $a$ by two tokens of values $p,q$ at depth $a+1$, where $p+q=3v$. Since $$\frac1{2^a}=\frac1{2^{a+1}}+\frac1{2^{a+1}},\qquad\frac v{3^a}=\frac{p+q}{3^{a+1}},$$ both sums stay the same. If after some moves the token values are exactly $1,2,\dots,n'$, each once, their depths solve the problem for $n'$. We use two kinds of moves:

• Double $D(x)$: replace $x$ by $x$ and $2x$. This adds the value $2x$.
• Pair $P(y)$: replace $y$ by $2y-1$ and $y+1$, then replace one of the two tokens $y+1$ by $y$ and $2y+3$. (Check: $(2y-1)+(y+1)=3y$ and $y+(2y+3)=3(y+1)$.) Now $y$ and $y+1$ are each there once again, and $2y-1$ and $2y+3$ are new.

From $n$ to $n+8$. Take a solution for some $n\ge9$. Among $n+1,\dots,n+8$ there are four even numbers $2x$ and four odd numbers $2y-1,\,2y+1,\,2y+3,\,2y+5$. Apply $P(y)$, then $P(y+1)$, then the four doubles $D(x)$. $P(y)$ adds $2y-1$ and $2y+3$, $P(y+1)$ adds $2y+1$ and $2y+5$, and the doubles add the even ones. Every token we start from has value at most $\frac{n+8}2\le n$, so it exists, and at the end the values are exactly $1,\dots,n+8$. This solves the problem for $n+8$.

Starting cases. Here are exponent lists $(a_1,\dots,a_n)$:

• $n=1$: $(0)$; $n=2$: $(1,1)$;
• $n=5$: $(2,2,2,3,3)$; $n=6$: $(2,2,3,3,3,3)$;
• $n=9$: $(2,3,2,4,4,4,4,4,4)$; $n=10$: $(2,3,3,3,4,4,4,4,4,4)$;
• $n=13$: $(2,4,2,3,5,4,4,5,6,5,5,6,5)$;
• $n=14$: $(2,4,2,3,5,5,4,4,6,5,5,6,6,6)$.

For example, for $n=5$: $\frac34+\frac28=1$ and $\frac{1+2+3}9+\frac{4+5}{27}=1$. Every $n\equiv1,2\pmod4$ with $n\ge17$ is $8$ more than a smaller such number that is at least $9$, so the step reaches it.

So solutions exist exactly when $n\equiv1$ or $2\pmod4$.