Putnam 2024

Key idea: for $n=1$ there is a small solution. For $n=2$ every variable must be divisible by $3$, and for $n\ge3$ every variable must be even; either way a smaller solution appears, which is impossible.

$n=1$. $2\cdot1+3\cdot2=8=4\cdot2$.

$n=2$. Suppose $2a^2+3b^2=4c^2$ with positive integers, and choose a solution with $a$ smallest. Modulo $3$: $2a^2\equiv c^2$. Squares are $0$ or $1$ modulo $3$, and $2a^2$ is $0$ or $2$, so both sides are $0$: $3\mid a$ and $3\mid c$. Then $9$ divides $4c^2-2a^2=3b^2$, so $3\mid b$. Dividing by $3$ gives a solution with smaller $a$.

$n\ge3$. Suppose $2a^n+3b^n=4c^n$ with $a$ smallest. Then $3b^n$ is even, so $b=2b'$. Dividing by $2$: $a^n+3\cdot2^{n-1}b'^n=2c^n$, so $a$ is even, $a=2a'$. Dividing by $2$ again: $2^{n-1}a'^n+3\cdot2^{n-2}b'^n=c^n$. The left side is even (as $n\ge3$), so $c=2c'$, and dividing by $2^{n-2}$: $$2a'^n+3b'^n=4c'^n,$$ a solution with $a'<a$. Contradiction.

Key idea: $p(p(x))-x$ always has the factor $p(x)-x$, and the other factor is congruent to $p'(x)+1$ modulo $p(x)-x$. So the condition becomes “$p(x)-x$ divides $p'(x)+1$”, and degrees settle it.

Let $D(x,y)=\frac{p(y)-p(x)}{y-x}$, a polynomial with $D(x,x)=p'(x)$. With $y=p(x)$, $$p(p(x))-x=\big(p(p(x))-p(x)\big)+\big(p(x)-x\big)=\big(p(x)-x\big)\big(D(x,p(x))+1\big).$$ If $p(x)=x$, the condition holds. Otherwise the condition is that $p(x)-x$ divides $D(x,p(x))+1$. Since $D(x,y)-D(x,x)$ is divisible by $y-x$, we have $D(x,p(x))\equiv D(x,x)=p'(x)$ modulo $p(x)-x$. So the condition is $$p(x)-x\ \text{ divides }\ p'(x)+1 .$$

• If $\deg p\ge2$, then $p(x)-x$ has degree $\deg p$, larger than $\deg(p'+1)$, and $p'+1\ne0$. Impossible.
• If $p=c$ is constant, $c-x$ (degree $1$) cannot divide $1$.
• If $p=ax+b$ with $a\ne0$: for $a=1$, $p-x=b$ is a nonzero constant (or $p=x$) and divides anything. For $a\ne1$, $p-x$ has degree $1$ and must divide the constant $a+1$, so $a=-1$.

So the answer is $p(x)=x+c$ and $p(x)=-x+c$. (Check: for $p=-x+c$, $p(p(x))=x$ and the left side is $0$.)

Key idea: compare the two cells next to the last corner. Which one holds the second largest entry has probability $\frac{2N-2}{3N-1}$ by the hook length formula, and for $N=2024$ that is between $\frac13$ and $\frac23$.

The maps $T$ in $S$ are exactly the standard Young tableaux of the $3\times N$ rectangle, $N=2024$ (rows increase to the right, columns increase downward). The entry $3N$ must be in the cell $(3,N)$. Removing it leaves a tableau of shape $\lambda=(N,N,N-1)$, whose largest entry $3N-1$ is in one of the two corners $(2,N)$ or $(3,N-1)$.

Take $(a,b)=(2,N)$ and $(c,d)=(3,N-1)$. Then $T(2,N)<T(3,N-1)$ exactly when $3N-1$ sits at $(3,N-1)$, and those tableaux correspond to tableaux of shape $\mu=(N,N,N-2)$. So the fraction is $f^\mu/f^\lambda$, where $f$ counts standard tableaux.

By the hook length formula $f^\nu=|\nu|!/\prod(\text{hooks})$, $$\frac{f^\mu}{f^\lambda}=\frac{1}{3N-1}\cdot\frac{\prod\text{hooks}(\lambda)}{\prod\text{hooks}(\mu)} .$$ Only the hooks in row $3$ and column $N-1$ change. In $\lambda$, row $3$ has hooks $N-1,N-2,\dots,1$ and column $N-1$ has hooks $4,3$ above it; in $\mu$, row $3$ has hooks $N-2,\dots,1$ and column $N-1$ has $3,2$. The ratio of products is $(N-1)\cdot\frac{4\cdot3}{3\cdot2}=2(N-1)$. So $$\frac{f^\mu}{f^\lambda}=\frac{2N-2}{3N-1}=\frac{4046}{6071}\approx0.6664,$$ which is at least $\frac13$ and at most $\frac23$ (because $3\cdot4046=12138<12142=2\cdot6071$).

Key idea: for $p>7$, the set $\{1,a,\dots,a^{p-5}\}$ misses exactly four residues, $0,x,x^2,x^3$ with $x=a^{-1}$, and these four must form an arithmetic progression. A short case check shows that only happens for $p\le7$.

$p=7$ works: $a=3$, $r=1$, since $\{1,3,9\}\equiv\{1,2,3\}$, which is $1,2,3$ in order.

$p>7$ fails. Since $1\le r\le p-1$, the $p-4$ terms of the progression are distinct. So $1,a,\dots,a^{p-5}$ are distinct and the order of $a$ is at least $p-4>\frac{p-1}{2}$; as it divides $p-1$, it equals $p-1$. The set is then all nonzero residues except $a^{p-4},a^{p-3},a^{p-2}$, that is $x^3,x^2,x$ with $x=a^{-1}$.

The complement of an arithmetic progression $b,b+r,\dots,b+(p-5)r$ in $\mathbb Z/p$ is the progression $b+(p-4)r,\dots,b+(p-1)r$. So $\{0,x,x^2,x^3\}$ is a $4$-term progression, and dividing by $x$, so is $\{0,1,x,x^2\}$ (four distinct elements).

A $4$-term progression $c,c+d,c+2d,c+3d$ splits into an outer pair and an inner pair with the same sum, whose differences are $\pm3d$ and $\pm d$. Try the three ways to pair $\{0,1,x,x^2\}$:

• $\{0,1\},\{x,x^2\}$: $x^2+x=1$ and $x^2-x=1-2x\in\{\pm3,\pm\frac13\}$, so $x\in\{-1,2,\frac13,\frac23\}$. Putting these into $x^2+x=1$ gives $0=1$, $6=1$, $4=9$, $10=9$, which need $p\mid1$ or $p\mid5$.
• $\{0,x\},\{1,x^2\}$: $x^2-x+1=0$ and $x^2-1=x-2$; then $x-2=\pm3x$ or $x=\pm3(x-2)$, so $x\in\{-1,\frac12,3,\frac32\}$. These make $x^2-x+1$ equal to $3,\frac34,7,\frac74$, which need $p\in\{3,7\}$.
• $\{0,x^2\},\{1,x\}$: $x^2=x+1$ and $x+1=\pm3(x-1)$ or $x-1=\pm3(x+1)$, so $x\in\{2,\frac12,-2,-\frac12\}$. These make $x^2-x-1$ equal to $1,-\frac54,5,-\frac14$, which need $p\mid5$ or $p\mid1$.

None of these is possible for a prime $p>7$.

Key idea: the probability is the average over $P\in\Omega$ of $\frac2\pi\arcsin\frac1{|P-c|}$. That function of $P-c$ has positive Laplacian, so its average over a circle grows as the center moves away from the middle.

The probability. Let $c=(r,0)$ and fix $P$ on $\Omega$, at distance $\delta=|P-c|\ge1$ from $c$. The two tangent lines from $P$ to $\Delta$ make the angle $2\arcsin(1/\delta)$, and the chord $PQ$ meets $\Delta$ exactly when $Q$ lies on the arc between their second intersections with $\Omega$. By the inscribed angle theorem, that arc has central angle $4\arcsin(1/\delta)$. So $$\operatorname{Prob}(r)=\frac2\pi\cdot\frac1{2\pi}\int_0^{2\pi}H(P_\theta-c)\,d\theta,\qquad H(x)=\arcsin\frac1{|x|} .$$

Subharmonicity. For a radial function $h(\delta)$ in the plane, $\Delta H=h''+h'/\delta$. With $h=\arcsin(1/\delta)$, $$h'=-\frac{1}{\delta\sqrt{\delta^2-1}},\qquad h''=\frac{2\delta^2-1}{\delta^2(\delta^2-1)^{3/2}},\qquad \Delta H=\frac{1}{(\delta^2-1)^{3/2}}>0 .$$

Monotonicity. Let $\Phi(c)=\frac1{2\pi}\int H(P_\theta-c)\,d\theta$ for $|c|<8$ (then every $|P-c|>1$). By symmetry $\Phi$ depends only on $\rho=|c|$, and $\Delta\Phi$ is the average of $\Delta H>0$, so $\Delta\Phi>0$. For a radial function, $\Delta\Phi=\frac1\rho(\rho\Phi'(\rho))'$. So $\rho\Phi'(\rho)$ is strictly increasing on $[0,8)$ and equals $0$ at $\rho=0$; hence $\Phi'>0$ for $0<\rho<8$. By continuity $\Phi$ is strictly increasing on $[0,8]$.

So the probability is smallest exactly at $r=0$ (where it is $\frac2\pi\arcsin\frac19\approx0.0709$).

Key idea: the shifted series has a Jacobi continued fraction with every $\lambda_k=10$. A standard theorem then gives the Hankel determinants as $\prod\lambda_k^{\,n-k}=10^{n(n-1)/2}$.

Let $f=\sum c_kx^k$. From $4f-1+3x=-\sqrt{1-14x+9x^2}$, squaring gives $16f^2-8(1-3x)f+8x=0$, i.e. $f=x+3xf+2f^2$. Here $c_0=0$, $c_1=1$. With $f=xg$, $g=\sum_{k\ge0}c_{k+1}x^k$: $$g=1+3xg+2xg^2 .$$ The matrix in the problem is the Hankel matrix $(g_{i+j})_{0\le i,j\le n-1}$ of $g$.

The continued fraction. Put $K=\frac{g-1}{5x}$, a power series with constant term $1$ (since $g=1+5x+\dots$). Let $u=g-1=5xK$. The relation for $g$ reads $u=5x+7xu+2xu^2$, which is the same as $u(1-7x)-2xu^2=5x$. Dividing by $5x$: $$K(1-7x)-10x^2K^2=1,\qquad\text{i.e.}\qquad K=\cfrac{1}{1-7x-10x^2K}.$$ Also $1/g=1-3x-2xg=1-5x-2x(g-1)=1-5x-10x^2K$. So $$g=\cfrac{1}{1-5x-\cfrac{10x^2}{1-7x-\cfrac{10x^2}{1-7x-\cdots}}}.$$

Hankel determinants. For a series $G=\cfrac{1}{1-\beta_0x-\cfrac{\lambda_1x^2}{1-\beta_1x-\cfrac{\lambda_2x^2}{\ddots}}}$, the $n\times n$ Hankel determinant is $\prod_{k=1}^{n-1}\lambda_k^{\,n-k}$ (Heilermann’s formula; equivalently $H_n(G)=\lambda_1^{\,n-1}H_{n-1}(\text{tail})$). With every $\lambda_k=10$, $$\det A=10^{(n-1)+(n-2)+\dots+1}=10^{n(n-1)/2}.$$

Key idea: adding the chosen entries forces $k=\frac{n+1}2$; for odd $n$ a “shift by half” permutation works.

Necessity. A choice of $n$ cells with no two in a row or column is a permutation $\sigma$, with entries $i+\sigma(i)-k$. Their sum is $n(n+1)-nk$. If they are $1,\dots,n$, the sum is $\frac{n(n+1)}2$, so $k=\frac{n+1}2$, and $n$ must be odd.

Sufficiency. Let $n=2m+1$, $k=m+1$, and $$\sigma(i)=\begin{cases}i+m+1,& 1\le i\le m,\\ i-m,& m+1\le i\le2m+1.\end{cases}$$ This is a permutation (values $m+2,\dots,2m+1$ and $1,\dots,m+1$). The sums $i+\sigma(i)$ are $m+3,m+5,\dots,3m+1$ from the first part and $m+2,m+4,\dots,3m+2$ from the second, together all of $m+2,\dots,3m+2$. Subtracting $k=m+1$ gives exactly $1,\dots,n$.

Key idea: a partner move only rearranges the side lengths and keeps the area. With given sides in a given order, a convex quadrilateral of a given area has at most two shapes, so a partner sequence can visit only finitely many congruence classes.

What a move keeps. Reflection in the perpendicular bisector of $AC$ swaps $A$ and $C$, so $AE=CD$, $CE=AD$, and triangle $ACE$ is congruent to triangle $CAD$. It also keeps $E$ on the same side of line $AC$ as $D$. So $ABCE$ has the same four side lengths as $ABCD$ (two of them swapped) and the same area $\operatorname{area}(ABC)+\operatorname{area}(ACD)$.

In a sequence of partners, every quadrilateral therefore has the same multiset of side lengths $\{s_1,s_2,s_3,s_4\}$ and the same area $K>0$.

Finitely many shapes. Fix an order of the sides, $AB=a$, $BC=b$, $CD=c$, $DA=d$. The quadrilateral is determined up to congruence by the diagonal $e=AC$ (two triangles with known sides, on opposite sides of $AC$). By Heron’s formula, $P_1(u)=16\,\operatorname{area}(ABC)^2$ and $P_2(u)=16\,\operatorname{area}(ACD)^2$ with $u=e^2$ and $$P_1=-u^2+2(a^2+b^2)u-(a^2-b^2)^2,\qquad P_2=-u^2+2(c^2+d^2)u-(c^2-d^2)^2 .$$ The area condition $\sqrt{P_1}+\sqrt{P_2}=4K$ implies, after squaring twice, $$256K^4-32K^2(P_1+P_2)+(P_1-P_2)^2=0 .$$ Here $P_1-P_2$ is linear in $u$ and $P_1+P_2=-2u^2+\dots$, so the left side is a quadratic in $u$ with leading coefficient $64K^2+4\big((a^2+b^2)-(c^2+d^2)\big)^2>0$. It has at most two roots. So each of the $24$ orders gives at most two congruence classes, at most $48$ in all.

An infinite sequence with no two members congruent would need infinitely many classes. So no such sequence exists.

Key idea: subtracting $n\pi$ from each root leaves $\arctan r_n$, so the gap minus $\pi$ is a difference of two arctangents of large numbers.

Where the roots are. On $(0,\frac\pi2)$, $\tan x>x$, so there is no root there. On each interval $(n\pi-\frac\pi2,n\pi+\frac\pi2)$ with $n\ge1$, the function $\tan x-x$ has derivative $\tan^2x\ge0$ (zero only at $x=n\pi$), so it is strictly increasing from $-\infty$ to $+\infty$; it has exactly one root, and since its value at $n\pi$ is $-n\pi<0$, the root lies in $(n\pi,n\pi+\frac\pi2)$. So $r_n=n\pi+\theta_n$ with $\theta_n\in(0,\frac\pi2)$ and $\tan\theta_n=\tan r_n=r_n$, i.e. $\theta_n=\arctan r_n$.

The estimate. Let $\delta=r_{n+1}-r_n-\pi=\theta_{n+1}-\theta_n=\arctan r_{n+1}-\arctan r_n$. Since $r_{n+1}>r_n$, $\delta>0$. For $0<a<b$, $$\arctan b-\arctan a=\arctan\frac{b-a}{1+ab}<\frac{b-a}{1+ab}.$$ With $b-a=\pi+\delta$: $\delta(1+r_nr_{n+1})<\pi+\delta$, so $\delta\,r_nr_{n+1}<\pi$. Since $r_n>n\pi$ and $r_{n+1}>(n+1)\pi$, $$\delta<\frac{\pi}{n(n+1)\pi^2}=\frac{1}{(n^2+n)\pi}.$$

Key idea: the expected next step is a linear function of the current value, so the expectation follows a simple linear recursion.

Given $a_{n,k}=a$, the walk goes up with probability $\frac{n-a}{n}$ and down with probability $\frac{a-1}{n}$. So $$E[a_{n,k+1}\mid a_{n,k}=a]=a+\frac{n-a}{n}-\frac{a-1}{n}=\Big(1-\frac2n\Big)a+\frac{n+1}{n}.$$ Let $e_k=E[a_{n,k}]$. Then $e_{k+1}=(1-\frac2n)e_k+\frac{n+1}n$, whose fixed point is $\frac{n+1}2$. Since $e_0=1$, $$e_k-\frac{n+1}{2}=\Big(1-\frac2n\Big)^k\Big(1-\frac{n+1}{2}\Big),\qquad E(n)=\frac{n+1}2-\frac{n-1}2\Big(1-\frac2n\Big)^n .$$ Dividing by $n$ and using $(1-\frac2n)^n\to e^{-2}$, the limit is $\frac12-\frac12e^{-2}$.

Key idea: a polynomial like $M_r(n)=\frac{n(n+1)\cdots(n+r-1)}{r!}$ has nonnegative coefficients, and so do sums and products of such polynomials with positive weights. We find a recursion in $k$ that builds the count from these pieces using only positive weights.

Setup. Write $M_r(z)=\binom{z+r-1}{r}$ with $M_0=1$. This is the number of weakly increasing sequences of length $r$ with entries in $\{1,\dots,z\}$. As a polynomial, $M_r(z)=z(z+1)\cdots(z+r-1)/r!$, a product of factors $z+c$ with $c\ge0$, so its coefficients are nonnegative. Once $z$ is chosen, the two sequences are independent, so with $m$ fixed, $$f(n)=F_k(n):=\sum_{z=1}^{n}M_k(z)\,M_m(z).$$

Three facts about $M$ (for integers $n\ge1$):

1. Pascal: $M_r(n)-M_r(n-1)=M_{r-1}(n)$ for $r\ge1$. (A sequence from $\{1,\dots,n\}$ either avoids $n$, or ends in $n$ and the rest is a sequence of length $r-1$.)
2. $M_{m+1}(n)=\dfrac{n+m}{m+1}M_m(n)$, and so by fact 1, $M_{m+1}(n-1)=\dfrac{n-1}{m+1}M_m(n)$.
3. $(n+k-1)\,M_{k-1}(n)=k\,M_k(n)$.

The recursion. For $k\ge1$ and every integer $n\ge0$, $$(k+m+1)\,F_k(n)=k\,F_{k-1}(n)+(m+1)\,M_{m+1}(n)\,M_k(n).$$ Both sides are $0$ at $n=0$, so it is enough to check that both sides grow by the same amount from $n-1$ to $n$. The left side minus $kF_{k-1}$ grows by $M_m(n)\big[(k+m+1)M_k(n)-kM_{k-1}(n)\big]$. For the last term, facts 1 and 2 give $$(m+1)\big[M_{m+1}(n)M_k(n)-M_{m+1}(n-1)M_k(n-1)\big]=M_m(n)\big[(n+m)M_k(n)-(n-1)\big(M_k(n)-M_{k-1}(n)\big)\big],$$ which is $M_m(n)\big[(m+1)M_k(n)+(n-1)M_{k-1}(n)\big]$. By fact 3, $(n-1)M_{k-1}(n)=kM_k(n)-kM_{k-1}(n)$, and the two increments agree.

Induction on $k$. For $k=0$ the sum is the hockey-stick sum $\sum_{z\le n}\binom{z+m-1}{m}=\binom{n+m}{m+1}=M_{m+1}(n)$, a polynomial with nonnegative coefficients. If $F_{k-1}(n)$ agrees for all $n\ge1$ with such a polynomial, the recursion writes $F_k(n)$ as $$F_k(n)=\frac{k}{k+m+1}F_{k-1}(n)+\frac{m+1}{k+m+1}M_{m+1}(n)M_k(n),$$ a positive combination of polynomials with nonnegative coefficients. So $f(n)$ is such a polynomial for every $k\ge0$.

Closed form. Unrolling the recursion gives $$\binom{k+m+1}{k}f(n)=M_{m+1}(n)\sum_{a=0}^{k}\binom{m+a}{a}M_a(n).$$ For example, with $k=m=1$ this is $3f(n)=\frac{n(n+1)}2(1+2n)$, the familiar $1^2+2^2+\dots+n^2$.

Key idea: the terms form a Gaussian bump around $n\approx1/t$ of width about $t^{-1/2}$. So $F_a(x)\approx t^{-a-1/2}e^{1/t}$, and the factor $e^{-1/(1-x)}$ cancels $e^{1/t}$ up to a bounded factor.

Let $s=1-x$ and $t=-\ln x=s+\frac{s^2}2+\dots$. Then $\frac1t=\frac1s-\frac12+O(s)$, so $E:=e^{1/t-1/s}\to e^{-1/2}$. Also $$F_a(x)\,e^{-1/s}=E\sum_{n\ge1}n^a\,e^{-t(n-1/t)^2}.$$

$a>-\frac12$: the limit is $\infty$. Keep only the integers $n\in[\frac1t,\frac1t+t^{-1/2}]$; for small $t$ there are at least $\frac12t^{-1/2}$ of them. For each, $t(n-\frac1t)^2\le1$, and $n^a\ge\kappa\,t^{-a}$ with $\kappa=\min(1,2^a)$ (since $\frac1t\le n\le\frac2t$). So the sum is at least $\frac{\kappa}{2e}\,t^{-a-1/2}\to\infty$, while $E\to e^{-1/2}$.

$a<-\frac12$: the limit is $0$. Here $a<0$. Split the sum.

• $n>\frac1{2t}$: $n^a<(2t)^{-a}$, and $\sum_ne^{-t(n-1/t)^2}\le1+\int e^{-tu^2}du=1+\sqrt{\pi/t}$. This part is $O(t^{-a}\cdot t^{-1/2})=O(t^{-a-1/2})\to0$.
• $n\le\frac1{2t}$: there $2n-n^2t\le\frac{3}{4t}$ (the quadratic increases up to $n=\frac1t$), and $n^a\le1$. This part of $F_a(x)e^{-1/s}$ is at most $\frac{1}{2t}e^{3/(4t)-1/s}$, and since $\frac1t-\frac1s$ is bounded, the exponent behaves like $-\frac1{4s}$. So it tends to $0$.

Hence $c=-\frac12$. (At $a=-\frac12$ the expression tends to $\sqrt{\pi}\,e^{-1/2}\approx1.075$.)