IMO 2022

Key idea: the number of runs never goes up, and it stays the same only when the last run is moved. For $k$ in the right range, moving the last run forever would force every run to be long, and four long runs don’t fit.

Call a maximal block of equal coins a run, and let $r$ be the number of runs. Since both types are present, $r\ge2$. The leftmost $n$ coins are all one type exactly when $r=2$ (then the row is $n$ of one type followed by $n$ of the other).

$k<n$ fails. Start from $n-1$ aluminium coins, then $n$ bronze, then one aluminium. The $k$-th coin is in the first run, and moving the first run to the front changes nothing. The row never changes and $r$ stays $3$.

$k>\lceil 3n/2\rceil$ fails. Then $n\ge2$. Let $h=\lfloor n/2\rfloor\ge1$ and start from runs of lengths $h,h,n-h,n-h$ (types A, B, A, B). Every run has length at least $h$, so the last run starts at position $2n-(\text{its length})+1\le 2n-h+1=\lceil 3n/2\rceil+1\le k$. So the $k$-th coin is in the last run. Moving it to the front just rotates the sequence of runs (a run of B lands in front of a run of A, so nothing merges). The new row again has four runs, each of length at least $h$, and the same thing repeats forever. So $r$ is always $4$.

$n\le k\le\lceil 3n/2\rceil$ works. Look at one operation when $r\ge3$.

• If the $k$-th coin is in the first run, that run has length at least $k\ge n$, so it is exactly $n$ coins of one type and we are done.
• If it is in a middle run, removing that run makes its two neighbors (both of the other type) merge, so $r$ drops by at least $1$.
• If it is in the last run and $r$ is odd, the first and last runs have the same type, so the moved run merges with the first one: $r$ drops by $1$.
• If it is in the last run and $r$ is even, $r$ stays the same and the runs rotate.

So $r$ never increases. Suppose $r$ never reaches $2$. Then from some point on $r$ stays fixed at an even value $r\ge4$, and every operation moves the last run. After $r$ more operations, every run has been the last run while holding the $k$-th coin. A last run holding position $k$ has length at least $2n-k+1\ge 2n-\lceil 3n/2\rceil+1=\lfloor n/2\rfloor+1$. So every run has length at least $\lfloor n/2\rfloor+1$. But with $r\ge4$ there are at least two runs of aluminium, which would need at least $2\lfloor n/2\rfloor+2>n$ aluminium coins. This contradiction shows $r$ reaches $2$, and at that moment the leftmost $n$ coins are all one type.

Key idea: AM–GM shows that a number can’t have a partner other than itself. So $xf(x)\le1$ for all $x$, and a little continuity at $y\to x$ squeezes out $f(x)=1/x$.

Say $y$ is a partner of $x$ when $xf(y)+yf(x)\le2$. This condition is symmetric in $x$ and $y$, and every $x$ has exactly one partner.

Every $x$ is its own partner. Suppose the partner of $x$ is some $y\ne x$. Then $x$ is not its own partner, so $2xf(x)>2$, that is, $xf(x)>1$. Also $x$ is a partner of $y$, so it is $y$’s only partner, and $y$ is not its own: $yf(y)>1$. By AM–GM, $$xf(y)+yf(x)\ \ge\ 2\sqrt{xf(y)\cdot yf(x)}=2\sqrt{xf(x)\cdot yf(y)}\ >\ 2,$$ so $y$ is not a partner of $x$ after all. This contradiction shows that the partner of each $x$ is $x$ itself. In other words, $xf(x)\le1$, so $f(x)\le 1/x$, and $xf(y)+yf(x)>2$ whenever $y\ne x$.

Then $f(x)=1/x$. Suppose $f(x)<1/x$ for some $x$, so $xf(x)<1$. For every $y\ne x$, using $f(y)\le 1/y$, $$2<xf(y)+yf(x)\le \frac{x}{y}+yf(x).$$ As $y\to x$ the right side tends to $1+xf(x)<2$, so it is below $2$ for $y$ close enough to $x$. That is a contradiction, so $f(x)=1/x$ for every $x$.

Check. For $f(x)=1/x$ the condition reads $\frac xy+\frac yx\le2$. By AM–GM the left side is at least $2$, with equality only when $y=x$. So each $x$ has exactly one partner, namely $x$.

Key idea: the largest prime’s neighbors are forced. Removing it and joining its two neighbors leaves a smaller valid circle, thanks to a product identity for $f(x)=x^2+x+k$, so induction finishes. One special case, where the identity gives $x=0$, only happens with four primes.

Write $f(x)=x^2+x+k$. Call an arrangement good if every pair of neighbors has product $f(x)$ for some whole number $x\ge1$.

Step 1: an identity. For any numbers $a,b$, put $s=a+b+1$ and $A=ab-k$. Expanding both sides shows $$f(a)\,f(b)=A^2+As+ks^2 .$$

Step 2: the largest prime’s neighbors are forced. Take a good arrangement of a set $S$ with $n\ge3$ primes, and let $p$ be the largest. Each neighbor $q$ of $p$ is smaller than $p$, and $pq=f(x)$ with $x\ge1$. Since $x^2<f(x)=pq<p^2$, we get $1\le x\le p-1$, and $x^2+x+k\equiv0\pmod p$. A quadratic congruence modulo a prime has at most two solutions. The two neighbors are different, so they come from two different values of $x$, and these must be exactly the two solutions $\rho_1,\rho_2$ in $\{1,\dots,p-1\}$. Their sum is $\equiv-1\pmod p$ and lies between $3$ and $2p-3$, so $\rho_1+\rho_2=p-1$. Hence the neighbors of $p$ are $$q_1=\frac{f(\rho_1)}{p},\qquad q_2=\frac{f(\rho_2)}{p},$$ and these depend only on $p$ and $k$, not on the arrangement.

Step 3: joining the two neighbors. Apply Step 1 with $a=\rho_1$, $b=\rho_2$, so $s=p$: $$p^2q_1q_2=A^2+Ap+kp^2,\qquad A=\rho_1\rho_2-k .$$ Since $\rho_2\equiv-1-\rho_1$, we get $\rho_1\rho_2\equiv-\rho_1-\rho_1^2\equiv k\pmod p$, so $y=A/p$ is an integer and $q_1q_2=y^2+y+k=f(y)$. Note $f(y)=f(-1-y)$. So if $y\ge1$ or $y\le-2$, the product $q_1q_2$ equals $f(z)$ for a whole number $z\ge1$. Then deleting $p$ and letting $q_1,q_2$ touch gives a good arrangement of $S\setminus\{p\}$.

Step 4: the special case $y\in\{0,-1\}$. Then $q_1q_2=k$.

• If $y=0$, then $\rho_1\rho_2=k$, so $pq_1=\rho_1^2+\rho_1+\rho_1\rho_2=\rho_1(\rho_1+\rho_2+1)=\rho_1p$. So $q_1=\rho_1$, $q_2=\rho_2$, and $p=q_1+q_2+1$.
• If $y=-1$, the same computation gives $q_1=\rho_1+1$, $q_2=\rho_2+1$, and $p=q_1+q_2-1$.

Either way $p\le q_1+q_2+1$. Suppose $n\ge4$, and let $r$ be the other neighbor of $q_1$. Then $r\ne q_2$ (otherwise $q_1q_2=f(x)=x^2+x+q_1q_2$ with $x\ge1$, impossible) and $r<p$. Writing $q_1r=x^2+x+q_1q_2$, $$x^2+x=q_1(r-q_2)\le q_1\cdot q_1,$$ because $r\le p-1\le q_1+q_2$. So $1\le x\le q_1-1$. But $q_1$ divides $x(x+1)$, and the only way is $x+1=q_1$. Then $r-q_2=q_1-1$, that is $r=q_1+q_2-1$. The same argument shows the other neighbor of $q_2$ is also $q_1+q_2-1$. So $q_1$ and $q_2$ share a neighbor besides $p$, and the circle is just $p,q_1,r,q_2$: $n=4$. In short, for $n\ge5$ the special case never happens.

Step 5: induction on $n$. We show that a set $S$ of $n$ primes has at most one good arrangement, up to rotation and reflection.

• For $n\le3$ there is only one arrangement of any kind.
• For $n=4$, Step 2 fixes the two neighbors of $p$, so the fourth prime sits opposite $p$, and the arrangement is fixed.
• For $n\ge5$, take two good arrangements of $S$. By Step 2 both have $p$ between $q_1$ and $q_2$. By Steps 3 and 4, deleting $p$ from each gives good arrangements of $S\setminus\{p\}$. By induction these two are the same circle. Each original arrangement is that circle with $p$ put back between $q_1$ and $q_2$. Those two touch along only one edge of the circle (it has at least $4$ primes), so the two originals are the same.

Key idea: two similar triangles at $T$ show that $Q,S,C,D$ are concyclic. A short angle chase then moves this to $P,Q,R,S$.

Step 1: congruent triangles. From $TB=TD$, $TC=TE$ and $BC=DE$, the triangles $TBC$ and $TDE$ are congruent (side–side–side), so $\angle BTC=\angle DTE$.

Step 2: where $Q$ and $S$ are. The segment $CT$ lies inside the convex pentagon, which meets line $AB$ only along the side $AB$. Since $Q$ is on line $AB$ outside that side, $Q$ is not on segment $CT$. It is also not on the ray from $C$ pointing away from $T$: that ray lies in the angle opposite the pentagon’s angle at $C$, on the far side of line $BC$ from $A$, and the only part of line $AB$ there is beyond $B$, while $Q$ is beyond $A$. So $T$ lies between $C$ and $Q$. In the same way, $T$ lies between $D$ and $S$.

Step 3: similar triangles. Because $Q$ is on ray $BA$ and $S$ is on ray $EA$, the given equal angles say $\angle TBQ=\angle TES$. By Step 2 and Step 1, $$\angle BTQ=180^\circ-\angle BTC=180^\circ-\angle DTE=\angle ETS .$$ So triangles $TBQ$ and $TES$ are similar, with $B\leftrightarrow E$ and $Q\leftrightarrow S$. Hence $TQ/TB=TS/TE$, and using $TB=TD$, $TE=TC$: $$TQ\cdot TC=TS\cdot TD .$$ Since $T$ is between $Q$ and $C$ and between $S$ and $D$, the converse of the intersecting chords theorem says $Q,S,C,D$ lie on one circle.

Step 4: angle chase. Write $\measuredangle(\ell,m)$ for the directed angle from line $\ell$ to line $m$, taken modulo $180^\circ$. Going around $T$, the rays $TB,TC,TD,TE$ appear in this order, ray $TQ$ is opposite $TC$ and ray $TS$ is opposite $TD$. So the similar triangles $TBQ$ and $TES$ have opposite orientations, and every directed angle of one is the negative of the matching angle of the other. In particular $$\measuredangle(QB,QT)=\measuredangle(ST,SE),\quad\text{that is,}\quad \measuredangle(AB,CT)=\measuredangle(DT,AE).$$ From the circle through $Q,S,C,D$: $\measuredangle(QC,QS)=\measuredangle(DC,DS)$. Now $$\measuredangle(QP,QS)=\measuredangle(AB,CT)+\measuredangle(CT,QS)=\measuredangle(DT,AE)+\measuredangle(DC,DT)=\measuredangle(DC,AE).$$ And $\measuredangle(RP,RS)=\measuredangle(DC,AE)$ too, since $R$ and $P$ lie on line $CD$ and $R,S$ on line $AE$. So $\measuredangle(QP,QS)=\measuredangle(RP,RS)$, which means $P,S,Q,R$ lie on a circle.

Key idea: either $b<p$, and then $a^p$ is far too big, or $b\ge p$, and then counting factors of $p$ forces $a=p$. The last equation $b!=p^p-p$ falls to a count of factors of $2$.

Case 1: $b<p$. Then $p\nmid b!$, so $p\nmid b!+p=a^p$ and $p\nmid a$. If $a\le b$, then $a\mid b!$ and $a\mid a^p$, so $a\mid p$; but $a=1$ is impossible ($b!+p>1$) and $a=p$ was just ruled out. So $a\ge b+1$, and then $$a^p\ge (b+1)^p\ge b^p+pb+1>b^p+p\ge b!+p,$$ using $b!\le b^b\le b^p$. No solutions here.

Case 2: $b\ge p$. Now $p\mid b!+p=a^p$, so $p\mid a$ and $p^p\mid a^p$.

• If $b\ge 2p$, then $p^2\mid b!$, so $b!+p$ is divisible by $p$ but not by $p^2$. That contradicts $p^2\mid a^p$. So $p\le b\le 2p-1$.
• If a prime $q\ne p$ divides $a$, then $q>b$ (otherwise $q\mid b!$ and $q\mid a^p$ would give $q\mid p$). Then $a\ge pq>p\cdot p$. Also if $a$ is a power of $p$ other than $p$ itself, $a\ge p^2$. In both cases $a^p\ge p^{2p}$. But pairing $i$ with $2p-i$, each pair has $i(2p-i)\le p^2$, so $$b!+p\le (2p-1)!+p\le p\cdot (p^2)^{p-1}+p=p^{2p-1}+p<p^{2p}.$$ So $a=p$.

We are left with $b!=p^p-p$, where $b\ge p$. For $p=2$ this is $b!=2$, so $b=2$. For $p=3$ it is $b!=24$, so $b=4$. For $p=5,7,11,13$, the numbers $p^p-p$ are $3120$, $823536$, $285311670600$ and $302875106592240$. Each lies strictly between two consecutive factorials ($6!$ and $7!$, $9!$ and $10!$, $14!$ and $15!$, $16!$ and $17!$), so none is a factorial.

Large $p$. For $p\ge17$ compare factors of $2$ in $b!/p=p^{p-1}-1$. On the left, $b!/p$ is a multiple of $(p-1)!$, and by Legendre’s formula $(p-1)!$ has $(p-1)-s$ factors of $2$, where $s\le \log_2(p-1)+1$ is the number of $1$’s in the binary form of $p-1$. So the left side has at least $p-2-\log_2(p-1)$ factors of $2$. On the right, the lifting-the-exponent formula for odd $x$ and even $m$, $v_2(x^m-1)=v_2(x-1)+v_2(x+1)+v_2(m)-1$, gives $$v_2\big(p^{p-1}-1\big)=2u+w-1,\qquad u=v_2(p-1),\ w=v_2(p+1).$$ One of $u,w$ equals $1$ (the numbers $p-1$ and $p+1$ are consecutive even numbers). If $w=1$ this is $2u\le 2\log_2(p-1)$; if $u=1$ it is $w+1\le \log_2(p+1)+1$. Either way it is at most $2\log_2(p+1)$. But $p-2-\log_2(p-1)>2\log_2(p+1)$ for $p\ge17$, so the two sides can’t be equal.

So the solutions are $(2,2,2)$ and $(3,4,3)$: indeed $2^2=2!+2$ and $3^3=4!+3$.

Key idea: each of the $2n(n-1)$ pairs of neighboring cells ends its own uphill path, and the lone valley path adds one more. To reach this count, the cells that are not local maxima must form a tree. We build such a tree from diagonal “ribbons” hung on a frame along two edges of the board.

Call a cell a valley if all its neighbors are larger, and write “path” for an uphill path.

Lower bound. Take two neighboring cells $u<v$. Starting at $u$, keep stepping to a smaller neighbor while there is one. The numbers decrease, so this stops, at a cell with no smaller neighbor: a valley $w$. Read backwards, the walk is a path from $w$ to $u$, and adding $v$ gives a path that ends with the step $u\to v$. Different neighboring pairs give different paths (a path’s last two cells name the pair). The board has $2n(n-1)$ neighboring pairs. The cell holding $1$ is a valley, and the one-cell path at it is not among those, since they all have at least two cells. So there are at least $2n(n-1)+1$ paths.

What equality needs. Let $N(c)$ be the number of paths ending at $c$. Then $N(c)=[c\text{ is a valley}]+\sum N(u)$ over the smaller neighbors $u$ of $c$. Suppose we split the cells into peaks, no two of them neighbors, and tree cells, which form a tree when we join neighbors. Number the tree cells $1,2,3,\dots$ by spreading out from one root cell, so that each tree cell other than the root comes after exactly one of its tree neighbors (its parent, the one toward the root) and before the others. Then give the peaks the largest numbers.

• The root is the only valley: every other tree cell has its parent as a smaller neighbor, and every peak has only tree cells, all smaller, as neighbors (for $n\ge2$).
• A tree cell other than the root has exactly one smaller neighbor, its parent. So by induction from the root, $N=1$ at every tree cell.
• A peak gets $N=$ its number of neighbors.

So the total is (number of tree cells) $+$ (number of peak–tree neighbor pairs). There are no peak–peak pairs, and a tree with $T$ cells has $T-1$ tree–tree pairs, so the total is exactly $2n(n-1)+1$. It remains to split every board this way. (For $n=1$ there is one path, which matches the formula.)

The split. Number the rows and columns $0,\dots,n-1$, and write $(i,j)$ for row $i$, column $j$. The peaks are:

• the bulk peaks: cells with $i,j\ge2$ and $i\equiv j\pmod 3$;
• in row $0$, the columns $j\equiv5\pmod 6$; in row $1$, the columns $j\equiv1$ or $3\pmod 6$;
• the same with rows and columns swapped (column $0$ at rows $\equiv5$, column $1$ at rows $\equiv1,3\pmod 6$). The cell $(1,1)$ is a peak by either rule.
• One change when $n\equiv4\pmod6$: the last column $n-1$ is $\equiv3\pmod 6$, and there we use $(0,n-1)$ as the peak instead of $(1,n-1)$. Likewise $(n-1,0)$ instead of $(n-1,1)$.

No two peaks touch. Bulk peaks lie on every third diagonal, so they never touch. In rows $0$ and $1$ the peak columns have residues $5$ and $1,3$ mod $6$, which are never equal or next to each other. Row $2$ has its peaks at columns $\equiv2\pmod3$, that is $\equiv2,5\pmod6$, never below a peak of row $1$. In the case $n\equiv4$, the new peak $(0,n-1)$ has neighbors $(0,n-2)$ and $(1,n-1)$, which are both tree cells. The columns $0,1$ work the same way by symmetry, and $(1,1)$ has only tree cells around it.

The tree cells form a tree. Take three pieces.

The frame along the top. In rows $0$ and $1$, row $0$ is cut by its peaks into runs of five cells, columns $6s$ to $6s+4$. Below run $s$ hang the tree cells $(1,6s)$, $(1,6s+2)$ and $(1,6s+4)$. The cell $(1,6s+5)$ is joined only to $(1,6s+4)$ and $(1,6s+6)$, so it links run $s$ to run $s+1$ by the single path $(0,6s+4),(1,6s+4),(1,6s+5),(1,6s+6),(0,6s+6)$. No other pairs of tree cells in rows $0,1$ are neighbors. So the runs, linked in a chain, form a tree, and cutting it off at column $n-1$ keeps it a tree. (When $n\equiv4$, the last cell $(1,n-1)$ hangs from $(1,n-2)$.) The frame along the left, in columns $0$ and $1$, is the mirror image. The two frames overlap in the three cells $(0,0),(0,1),(1,0)$, which form a path in both, and no other cell of one frame touches the other. So the whole frame is a tree.

The ribbons. In the bulk ($i,j\ge2$), the tree cells are those with $j-i\equiv1$ or $2\pmod3$. For each integer $m$, the cells with $j-i\in\{3m+1,3m+2\}$ form a ribbon. A ribbon cell with $j-i=3m+1$ touches only $(i,j+1)$ and $(i-1,j)$ inside the ribbon, and its other neighbors are peaks. So each ribbon is a staircase $$(i,j)\to(i,j+1)\to(i+1,j+1)\to(i+1,j+2)\to\cdots$$ that only moves right and down, and the part inside the bulk is one unbroken piece of it. Different ribbons never touch.

Each ribbon hangs from the frame by exactly one pair. A bulk cell touches the frame only if it is in row $2$ or column $2$. Take a ribbon with $m\ge0$. None of its cells are in column $2$, and its cells in row $2$ are its first two, $(2,3m+3)$ and $(2,3m+4)$. Above them, in row $1$, the residues mod $6$ are $3,4$ (if $m$ is even) or $0,1$ (if $m$ is odd), so exactly one of the two cells above is a tree cell. If only $(2,3m+3)$ fits on the board, then $3m+3=n-1$ and the ribbon is that single cell. When $m$ is odd, the cell above it is a tree cell. When $m$ is even, $n\equiv4\pmod6$, and the change in the last column made $(1,n-1)$ a tree cell. Ribbons with $m<0$ are the mirror images and hang from the left frame.

So the tree cells are a tree (the frame) with paths (the ribbons) each attached by a single pair. That is a tree. Numbering it outward from $(0,0)$, with the peaks last, gives exactly $2n(n-1)+1$ paths.

Answer: the smallest possible number of uphill paths is $2n^2-2n+1$.