IMO 2010

Key idea: the value $f(0)$ splits the problem in two. If it is nonzero, $f$ is constant. If it is zero, $f$ vanishes on $[0,1)$, and every real number is an integer times a number in $[0,1)$.

Write the equation as $f(\lfloor x\rfloor y)=f(x)\lfloor f(y)\rfloor$.

Case $f(0)\ne0$. With $x=0$: $f(0)=f(0)\lfloor f(y)\rfloor$, so $\lfloor f(y)\rfloor=1$ for all $y$. With $y=0$: $f(0)=f(x)\lfloor f(0)\rfloor=f(x)$. So $f\equiv c$ with $\lfloor c\rfloor=1$, that is, $1\le c<2$. These work: both sides equal $c$.

Case $f(0)=0$. For $x\in[0,1)$ we get $0=f(x)\lfloor f(y)\rfloor$ for all $y$.

• If $\lfloor f(y)\rfloor=0$ for every $y$, then the right side is always $0$, and $x=1$ gives $f(y)=0$ for all $y$.
• Otherwise $f(x)=0$ for all $x\in[0,1)$. Then for $y\in[0,1)$ the right side is $f(x)\lfloor0\rfloor=0$, so $f(ny)=0$ for every integer $n$ (take $x=n$). Every real $t$ has this form: for $t\ge0$ use $n=\lfloor t\rfloor+1$, for $t<0$ use $n=-\lfloor -t\rfloor-1$, and $y=t/n\in[0,1)$. So $f\equiv0$.

$f\equiv0$ clearly works. So the solutions are $f\equiv0$ and the constants $c\in[1,2)$.

Key idea: add the excenter $J$ opposite $A$. The midline $DG$ is parallel to $JF$, and a pair of similar triangles shows that the line from $D$ to the second point of $EI$ on $\Gamma$ is parallel to $JF$ as well.

Let $\alpha,\beta,\gamma$ be the angles of the triangle and $J$ the excenter opposite $A$; it lies on ray $AI$ beyond $D$. We use directed angles between lines, mod $180^\circ$, written $\angle(m,n)$. The angle $\angle CAE$ is positive and less than $\tfrac\alpha2$, so $E\ne C$ and $E\ne D$.

Step 1: $DG\parallel JF$. We have $\angle DBI=\angle DBC+\angle CBI=\tfrac\alpha2+\tfrac\beta2$ (as $\angle DBC=\angle DAC$), and $\angle DIB=\tfrac\alpha2+\tfrac\beta2$ as an exterior angle of triangle $ABI$. So $DB=DI$. The two bisectors at $B$ are perpendicular, so $\angle IBJ=90^\circ$, and the point $D$ of the hypotenuse $IJ$ with $DB=DI$ is its midpoint. Since $G$ is the midpoint of $IF$, the midline $DG$ of triangle $IFJ$ is parallel to $JF$.

Step 2: two similar triangles. Triangles $ABF$ and $AEC$ are similar: $\angle BAF=\angle EAC$, and $\angle ABF=\angle ABC=\angle AEC$ (inscribed angles on arc $AC$). So $AF\cdot AE=AB\cdot AC$. Triangles $ABJ$ and $AIC$ are similar too: $\angle BAJ=\angle IAC=\tfrac\alpha2$, and $\angle ABJ=\beta+\tfrac{180^\circ-\beta}2=90^\circ+\tfrac\beta2=\angle AIC$. So $AI\cdot AJ=AB\cdot AC$. Hence $$\frac{AI}{AF}=\frac{AE}{AJ}.$$ The rays $AF$ and $AE$ are mirror images in the bisector $AI$, so $\angle IAE=\angle FAJ$. Both angles turn the same way (from $AI$ toward $AC$, and from $AF$ toward $AC$). So triangles $AIE$ and $AFJ$ are similar with the same orientation, and $$\angle(EA,EI)=\angle(JA,JF).\qquad(\ast)$$

Step 3: the meeting point. Let line $EI$ meet $\Gamma$ again at $X$. Since $E\ne D$, the point $X$ is not $A$ or $D$. Inscribed angles on the chord $ED$ give $$\angle(XI,XD)=\angle(XE,XD)=\angle(AE,AD)=\angle(AE,AJ).$$ On the other hand, using $(\ast)$, $$\angle(XI,JF)=\angle(EI,EA)+\angle(EA,AJ)+\angle(AJ,JF)=-\angle(JA,JF)+\angle(AE,AJ)+\angle(JA,JF)=\angle(AE,AJ).$$ So the lines $XD$ and $JF$ make the same angle with line $XI$, which means they are parallel. By Step 1, $XD$ is then parallel to $DG$, and both pass through $D$: they are the same line. So $X$ is on $DG$, and $DG$ and $EI$ meet at the point $X$ of $\Gamma$.

Key idea: if $p$ divides $g(k)-g(l)$, we can pick $n$ so that $p$ appears to an odd power in both $g(k)+n$ and $g(l)+n$. The square condition then pushes $p$ into $k+g(n)$ and $l+g(n)$, so $p\mid k-l$. Neighboring values then differ by exactly $1$.

Lemma. If a prime $p$ divides $g(k)-g(l)$, then $p\mid k-l$.

Proof. We choose $n=pu-g(k)$ with $u$ a large positive integer (so $n>0$), so that both $g(k)+n$ and $g(l)+n$ contain an odd power of $p$:

• If $p^2\mid g(l)-g(k)$ (this includes the difference $0$): take $p\nmid u$. Then $g(k)+n=pu$ and $g(l)+n=pu+(g(l)-g(k))$ both have exactly one factor $p$.
• If $g(l)-g(k)=pw$ with $p\nmid w$, and $p$ is odd: take $u\not\equiv0$ and $u\not\equiv-w\pmod p$. Then $g(k)+n=pu$ and $g(l)+n=p(u+w)$ both have exactly one factor $p$.
• If $g(l)-g(k)=2w$ with $w$ odd: take $u\equiv4-w\pmod 8$, which is odd. Then $g(k)+n=2u$ has one factor $2$, and $g(l)+n=2(u+w)$ with $u+w\equiv4\pmod8$ has exactly three.

Now $(g(k)+n)(k+g(n))$ is a square and $p$ divides $g(k)+n$ to an odd power, so $p\mid k+g(n)$. In the same way $p\mid l+g(n)$. Subtracting, $p\mid k-l$.

Steps of size one. No prime divides $(k+1)-k=1$, so by the Lemma no prime divides $g(k+1)-g(k)$. That difference is not $0$ (every prime divides $0$), so $g(k+1)-g(k)=\pm1$. Also $g$ is injective: if $g(k)=g(l)$, every prime divides $k-l$, so $k=l$.

Same direction. If one step were $+1$ and the next $-1$ (or the reverse), then $g(k+2)=g(k)$, contradicting injectivity. So all steps are $+1$, or all are $-1$. All $-1$ would make $g$ negative eventually. So $g(n)=n+c$ with $c=g(1)-1\ge0$.

Check. $(g(m)+n)(m+g(n))=(m+n+c)^2$.

Key idea: $MK=ML$ is the same as $PA:PB=CA:CB$. The circle centered at $S$ through $C$ is exactly the set of points with that ratio, and $P$ is on it.

Reduce to a ratio. The chords $AK$ and $CM$ cross at $P$, so $PA\cdot PK=PC\cdot PM$ and triangles $PAC$ and $PMK$ are similar. Hence $\dfrac{MK}{AC}=\dfrac{PM}{PA}$. In the same way, from the chords $BL$ and $CM$, $\dfrac{ML}{BC}=\dfrac{PM}{PB}$. Dividing, $$\frac{MK}{ML}=\frac{AC}{BC}\cdot\frac{PB}{PA}.$$ So $MK=ML$ exactly when $\dfrac{PA}{PB}=\dfrac{CA}{CB}$.

The circle about $S$. $SC$ is tangent to $\Gamma$, so $SC^2=SA\cdot SB$, and triangles $SCA$ and $SBC$ are similar (common angle at $S$). So $\dfrac{CA}{BC}=\dfrac{SC}{SB}$.

Now $SP=SC$, so $SP^2=SA\cdot SB$, and in the same way triangles $SPA$ and $SBP$ are similar. So $\dfrac{PA}{BP}=\dfrac{SP}{SB}=\dfrac{SC}{SB}$.

Finish. Both ratios equal $\dfrac{SC}{SB}$, so $\dfrac{PA}{PB}=\dfrac{CA}{CB}$ and $MK=ML$.

Key idea: the swap move lets us reuse a doubling routine many times, so a few coins grow into a tower of powers of $2$. A pile can also be trimmed one coin at a time, by swapping two empty boxes. Build far more than needed, trim to a quarter of the target, then double twice.

Write the six box contents as a list, and let $T=2010^{2010^{2010}}$.

Doubling routine. In three neighboring boxes (the first at position $\le4$), $(k,s,0)\to(k,0,2s)$ by $s$ moves of type 1 on the middle box, and then one type 2 move on the first box gives $(k-1,2s,0)$. Starting from $(a,0,0)$, a type 1 move gives $(a-1,2,0)$, and repeating the routine gives $$(a,0,0)\to(0,2^a,0).$$

Tower routine. In four neighboring boxes (starting at position $\le3$), from $(k,t,0,0)$ the doubling routine on the last three boxes gives $(k,0,2^t,0)$, and a type 2 move on the first box gives $(k-1,2^t,0,0)$. Starting from $(a,0,0,0)$, a type 1 move gives $(a-1,2,0,0)$, and repeating gives $$(a,0,0,0)\to(0,P_a,0,0),\qquad P_1=2,\ P_{j+1}=2^{P_j},$$ a tower of $a$ twos.

The plan.

• Type 1 on box 5, then type 2 on boxes 4, 3, 2, 1 in that order: $$(1,1,1,1,1,1)\to(1,1,1,1,0,3)\to(1,1,1,0,3,0)\to(1,1,0,3,0,0)\to(1,0,3,0,0,0)\to(0,3,0,0,0,0).$$
• Doubling on boxes 2–4: $(0,0,8,0,0,0)$.
• Tower on boxes 3–6: $(0,0,0,P_8,0,0)$.
• $P_8$ is far larger than $T/4$: indeed $\log_2T=2010^{2010}\log_22010<2^{11\cdot2010+4}<2^{65536}=P_5$, so $T<P_6<P_8$. Apply type 2 to box 4 repeatedly: it removes one coin and swaps the empty boxes 5 and 6, so it just lowers box 4 by one. Stop at $(0,0,0,T/4,0,0)$; note $4\mid T$.
• Type 1 on box 4, $T/4$ times: $(0,0,0,0,T/2,0)$. Type 1 on box 5, $T/2$ times: $(0,0,0,0,0,T)$.

So the answer is yes.

Key idea: subtract the best growth rate among the first $s$ terms. What is left never goes above $0$, never drops when the index grows by $\ell$, and has only finitely many possible values. So it must settle down.

Step 1: a short first part is enough. We show by strong induction that for every $n>s$, $$a_n=\max_{1\le k\le s}\,(a_k+a_{n-k}).\qquad(1)$$ The right side is at most $a_n$ by the rule. For the other direction, pick $k$ with $a_n=a_k+a_{n-k}$. If $k\le s$ or $n-k\le s$ we are done (the rule is symmetric in $k$ and $n-k$). Otherwise $k>s$, and by induction $a_k=a_j+a_{k-j}$ for some $j\le s$. Now $n-j=(k-j)+(n-k)$ with both parts positive and $n-j>n-k>s$, so the rule gives $a_{n-j}\ge a_{k-j}+a_{n-k}$. Hence $a_n=a_j+a_{k-j}+a_{n-k}\le a_j+a_{n-j}$.

Step 2: subtract a linear term. Choose $\ell\in\{1,\dots,s\}$ with $a_\ell/\ell$ as large as possible, put $\theta=a_\ell/\ell$ and $b_n=a_n-n\theta$. Since $b_k+b_{n-k}=a_k+a_{n-k}-n\theta$, the sequence $b$ follows the same rule for $n>s$, and (1) holds for it too. Also $b_i\le0$ for $i\le s$, and $b_\ell=0$. Then:

• $b_n\le0$ for all $n$ (for $n>s$, $b_n$ is a sum of two earlier terms);
• $b_n\ge b_\ell+b_{n-\ell}=b_{n-\ell}$ for all $n>s$.

Step 3: few possible values. Using (1) again and again (on $n$, then on the second index while it exceeds $s$) writes each $b_n$ as a sum of terms from the list $b_1,\dots,b_s$, all $\le0$. If none of them is negative, $b_n=0$ for all $n$. Otherwise let $\delta>0$ be the smallest size of a negative one. A sum that is at least $-C$ contains at most $C/\delta$ negative terms, so such sums take only finitely many values.

Step 4: it settles. Fix a residue class mod $\ell$ and its first index $n_0>s$. Along $n_0,n_0+\ell,n_0+2\ell,\dots$ the values $b_n$ never decrease (Step 2), so they stay $\ge b_{n_0}$, and by Step 3 they take finitely many values. So they are constant from some point on. Taking the latest of these points over the $\ell$ classes gives an $N$ with $b_n=b_{n-\ell}$ for all $n\ge N$. Adding back $n\theta=\ell\theta+(n-\ell)\theta$: $$a_n=a_\ell+a_{n-\ell}\qquad\text{for all }n\ge N,$$ with $\ell\le s$. (The positivity of the $a_n$ is not even needed.)