Putnam 2023

Key idea: take logarithms; each factor $\cos kx$ contributes $-k^2$ to the second derivative at $0$.

Near $0$, $f_n>0$ and $\ln f_n=\sum_{k=1}^n\ln\cos kx$. Since $(\ln f)''=\frac{f''}{f}-\big(\frac{f'}{f}\big)^2$, $f_n(0)=1$ and $f_n'(0)=0$ (each $\ln\cos kx$ has derivative $-k\tan kx$, which is $0$ at $0$), we get $$f_n''(0)=(\ln f_n)''(0)=\sum_{k=1}^n\big(-k^2\sec^2 kx\big)\Big|_{x=0}=-\frac{n(n+1)(2n+1)}{6}.$$ For $n=17$ this is $-1785$, and for $n=18$ it is $-2109$. So the smallest $n$ with $|f_n''(0)|>2023$ is $18$.

Key idea: $q(y)=y^2p(y)-1$ is monic of degree $2n+2$ and vanishes at all $\pm\frac1k$, so it is that product times a monic quadratic. Two coefficients of $q$ that we know fix the quadratic.

$p(1/x)=x^2$ means $q(1/x)=0$. We know $q(\pm\frac1k)=0$ for $k=1,\dots,n$, and $q$ is monic of degree $2n+2$, so $$q(y)=(y^2+ay+b)\prod_{k=1}^n\Big(y^2-\frac1{k^2}\Big).$$ The product is even with constant term $\prod(-\frac1{k^2})=\frac{(-1)^n}{(n!)^2}=\frac1{(n!)^2}$, since $n$ is even. In $q=y^2p(y)-1$, the coefficient of $y$ is $0$ and the constant term is $-1$. Comparing: $a/(n!)^2=0$, so $a=0$; and $b/(n!)^2=-1$, so $b=-(n!)^2$.

The other roots of $q$ are $y=\pm n!$, which differ from all $\pm\frac1k$. So the other solutions are $x=1/y=\pm\frac1{n!}$.

Key idea: before $f$ first hits $0$, the point $(f,v)$, where $v=\int_0^x f$, turns with angular speed at most $1$. It has to turn by $\frac\pi2$, so this takes time at least $\frac\pi2$.

$\frac\pi2$ is reached. $f=\cos$, $g=\sin$: $|f'|=|g|$, $|g'|=|f|$, $f(0)=1$, $g(0)=0$, $f(\frac\pi2)=0$.

Nothing smaller. Let $r$ be the first zero of $f$ (it exists by assumption and $r>0$), so $f>0$ on $[0,r)$. Put $v(x)=\int_0^xf$ on $[0,r]$. Then $v'=f\ge0$, and $$|g(x)|=\Big|\int_0^xg'\Big|\le\int_0^x|f|=v(x),\qquad\text{so}\qquad f'\ge-|g|\ge-v .$$ The point $(f,v)$ is never the origin on $[0,r]$: $f>0$ before $r$, and $v(r)>0$. Write $f=R\cos\theta$, $v=R\sin\theta$ with $\theta$ continuous, $\theta(0)=0$. Then $$\theta'=\frac{f\,v'-v\,f'}{f^2+v^2}=\frac{f^2-v f'}{f^2+v^2}\le\frac{f^2+v^2}{f^2+v^2}=1,$$ using $-vf'\le v^2$ (as $v\ge0$ and $f'\ge-v$). At $x=r$ we have $f=0$, $v>0$, so $\theta(r)=\frac\pi2$ (the angle stays in $[0,\frac\pi2]$ while $f,v\ge0$). By the mean value theorem, $\frac\pi2=\theta(r)-\theta(0)\le r$.

Key idea: the integer combinations contain two vectors on each axis whose length ratio is the irrational golden ratio, so on each axis they come arbitrarily close to every point.

Up to a rotation and a common scale factor (which do not affect density), the twelve vertices are the cyclic shifts of $(0,\pm1,\pm\phi)$, where $\phi=\frac{1+\sqrt5}2$. Let $\Lambda$ be the set of integer combinations of them. Then $\Lambda$ contains $$(0,1,\phi)-(0,1,-\phi)=(0,0,2\phi),\qquad(\phi,0,1)+(-\phi,0,1)=(0,0,2).$$ Since $\phi$ is irrational, the numbers $2a+2b\phi$ ($a,b\in\mathbb Z$) are dense in $\mathbb R$ (a subgroup of $\mathbb R$ that is not cyclic is dense). So $\Lambda$ meets every interval of the $z$-axis, and by the cyclic symmetry, of the $x$- and $y$-axes too.

Given $v=(v_1,v_2,v_3)$ and $\varepsilon>0$, pick points of $\Lambda$ on the three axes within $\varepsilon/3$ of $(v_1,0,0)$, $(0,v_2,0)$, $(0,0,v_3)$. Their sum is in $\Lambda$ and within $\varepsilon$ of $v$.

Key idea: with $t=e^s$, the weights give a product that vanishes to order $2020$ at $s=0$. The sum then only depends on three more terms, and it is a cubic in $z$ with explicit roots.

Let $m=1010$ and $w(k)=(-2)^{f(k)}$. Each base-3 digit contributes a factor $1-2t^{3^j}+t^{2\cdot3^j}$, so $$\sum_{k<3^m}w(k)\,t^k=\prod_{j=0}^{m-1}\big(1-t^{3^j}\big)^2 .$$ Hence, with $a_j=3^j$, $$F(s):=\sum_k w(k)e^{(z+k)s}=e^{zs}\prod_{j}\big(1-e^{a_js}\big)^2,$$ and our sum is $F^{(2023)}(0)=2023!\,[s^{2023}]F$. Use $e^u-1=u\,e^{u/2}\,\frac{\sinh(u/2)}{u/2}$: $$F(s)=\Big(\prod_ja_j^2\Big)s^{2m}\,e^{ws}\,H(s),\qquad w=z+\sum_ja_j=z+\frac{3^m-1}{2},$$ where $H(s)=\prod_j\Big(\frac{\sinh(a_js/2)}{a_js/2}\Big)^2=1+\frac{\sum a_j^2}{12}s^2+O(s^4)$ is even. Since $2023=2m+3$, we need $[s^3]$ of $e^{ws}H$: $$\frac{w^3}{6}+\frac{\sum_ja_j^2}{12}\,w .$$ So the sum vanishes exactly when $w=0$ or $w^2=-\frac12\sum_ja_j^2=-\frac{9^m-1}{16}$. That gives the three values in the answer.

Key idea: describe a position mid-game by three numbers: the turns left, the dead numbers (too small to ever be fixed), and the run of upcoming turns whose own numbers are still free. A short table then says, for every position, whether the next player can choose the parity of the remaining fixed points or one parity is locked in. The start is locked to the parity of $n$, so Bob names that parity.

Call turn $k$ a fixed point if the number $k$ is chosen on turn $k$. We show Bob wins for every $n$ by choosing “odd” when $n$ is odd and “even” when $n$ is even.

Positions. Before turn $t$, let $m=n-t+1$ be the number of turns left. An unchosen number below $t$ is dead: its turn has passed. An unchosen number $\ge t$ is live. Renumber the remaining turns and the live numbers by subtracting $t-1$, so the current turn is turn $1$ and live number $i$ belongs to turn $i$. A position is then a set $L\subseteq\{1,\dots,m\}$ of live numbers together with $d=m-|L|$ dead numbers. Let $r$ be the largest $k$ with $1,2,\dots,k$ all in $L$ (so $r=0$ if $1\notin L$). Only the parity of the fixed points still to come matters.

A move is one of three kinds:

• take $1$ (if $1\in L$): a fixed point;
• take a dead number (if $d\ge1$): no fixed point;
• take a live $x\ge2$: no fixed point.

In the last two kinds, if $1$ was live it becomes dead. In all three, the next position has $m-1$ turns, and the numbers shift down by one.

Call a position locked to $e$ if whichever player wants the remaining fixed points to have parity $e$ can force it, no matter who moves next. Call it open if the player about to move can force either parity, whichever they choose.

Claim.

1. If $d=0$: locked to $m \bmod 2$.
2. If $d=1$: open when $m$ is even, locked to $0$ when $m$ is odd.
3. If $d\ge2$: open when $r$ is odd, locked to $0$ when $r$ is even.

At the start $d=0$ and $m=n$, so the game is locked to the parity of $n$, and Bob wins by naming it.

How to check a position. Suppose every position one move away is open or locked. Say a move secures $e$ if it leads to a position locked to $e'$ and the move’s own fixed point (0 or 1) plus $e'$ has parity $e$. A move into an open position secures nothing, since the opponent then picks the parity. So the mover can force parity $e$ exactly when some move secures $e$. Hence a position is open if moves secure both parities, and locked to $e$ if moves secure $e$ and nothing secures $1-e$. We prove the claim by induction on $m$. The base case $m=0$ is locked to $0$, and it has $d=0$.

Case $d=0$ ($L$ is everything, $r=m$). Taking $1$ leads to $d=0$ with $m-1$ turns, locked to $m-1$; it secures $1+(m-1)\equiv m$. Taking $x\ge2$ kills $1$ and leads to $d=1$ with $m-1$ turns. If $m$ is odd, that position is open and secures nothing. If $m$ is even, it is locked to $0$ and secures $0\equiv m$. Either way only $m \bmod 2$ is secured.

Case $d=1$, $1\notin L$ ($L=\{2,\dots,m\}$). Taking the dead number leads to $d=0$ with $m-1$ turns, securing $m-1$. Taking a live $x$ leads to $d=1$ with $m-1$ turns: open if $m$ is odd, locked to $0$ if $m$ is even. For $m$ even, the moves secure $1$ and $0$, so the position is open. For $m$ odd, only $0$ is secured.

Case $d=1$, $1\in L$ (one missing live number $h\ge2$). Taking $1$, or taking the dead number, leads to $d=1$ with $m-1$ turns. If $m$ is even, those positions are locked to $0$, so taking $1$ secures $1$ and the dead number secures $0$: open. If $m$ is odd (so $m\ge3$), those positions are open and secure nothing. A live $x\notin\{1,h\}$ leads to $d=2$ with run $\min(h,x)-2$. It secures $0$ when that run is even and nothing otherwise. Choosing $x=2$ (or any $x$ if $h=2$) makes the run $0$. So only $0$ is secured: locked to $0$.

Case $d\ge2$, $r=0$. No move makes a fixed point, and every next position has at least one dead number, so nothing is locked to $1$ (that needs $d=0$). Nothing secures $1$. To secure $0$: if $2\in L$, take $x=2$. If $2\notin L$ but $L\neq\varnothing$, take any live $x$. Either way the next position has $d\ge2$ and run $0$, so it is locked to $0$. If $L=\varnothing$, take a dead number. The result has no live numbers and $d-1$ dead ones, which is locked to $0$ by case 3 (run $0$) or by case 2 ($d-1=m-1=1$ is odd).

Case $d\ge2$, $r$ odd. Taking $1$ and taking a dead number lead to the same position: $d$ is unchanged and the run is $r-1$, which is even, so it is locked to $0$. The first move secures $1$, the second secures $0$: open.

Case $d\ge2$, $r\ge2$ even. Taking $1$ or a dead number leads to run $r-1$, odd, which is open. A live $x$ leads to $d+1$ dead numbers with run $r-1$ if $x>r$ (open), or run $x-2$ if $x\le r$. Taking $x=2$ gives run $0$, locked to $0$. Every next position has $d\ge2$, so nothing secures $1$: locked to $0$.

This covers every position and proves the claim. $\blacksquare$

In the actual game, Bob’s winning moves come straight from the case list. For instance, when $n$ is odd and Alice fixes $1$, on each turn $2k$ Bob takes $2k+1$ if it is still free, and otherwise any number except $2k$. Then Alice gets no more fixed points, Bob makes none, and the total is $1$.

Key idea: every coin moves at most once, and the set of moved coins is a “staircase” in the starting block. Every staircase can be reached, and staircases in an $(m-1)\times(n-1)$ block are counted by lattice paths.

Call the starting cells (with $i\le m-1$, $j\le n-1$) the block. For a set $M$ of block cells, let $C(M)$ be the position where the coins from cells in $M$ have moved one step diagonally and the rest have not moved. Call $M$ closed if $(i,j)\in M$ implies $(i+1,j)$ and $(i,j+1)$ are in $M$ whenever those are block cells.

Claim. From $C(M)$ with $M$ closed, the legal moves are exactly: move the coin of a cell $(i,j)\notin M$ whose block neighbors $(i+1,j)$, $(i,j+1)$, $(i+1,j+1)$ all lie in $M$. The result is $C(M\cup\{(i,j)\})$, again closed.

Unmoved coins. The cell $(i+1,j+1)$ is empty only if its own coin has moved (or it is outside the block). The cell $(i+1,j)$ is empty only if its coin has moved and the coin from $(i,j-1)$ has not landed there; the second condition holds automatically, since $(i,j-1)\in M$ would force $(i,j)\in M$. The cell $(i,j+1)$ is similar. This gives the rule in the claim.

Moved coins never move again. A moved coin from $(i,j)$ sits at $(i+1,j+1)$. If that is still a block cell, it is in $M$, so $(i+1,j)\in M$ too, and the coin from $(i+1,j)$ sits at $(i+2,j+1)$, which blocks the move.

Counting. Starting from $M=\varnothing$, every closed set can be built one cell at a time (add cells from the bottom-right corner outward), so every $C(M)$ with $M$ closed is reachable, and nothing else is. Different closed sets give different positions: on each diagonal, $M$ is a final segment, and the position of the single gap on that diagonal shows its length. Closed sets in an $(m-1)\times(n-1)$ block correspond to monotone lattice paths along their boundary, and there are $\binom{(m-1)+(n-1)}{m-1}$ of them.

Key idea: powers of $2$ modulo $7$ are only $1,2,4$, which rules out one or two binary ones. A search finds a multiple with three.

One 1. $2023n=2^a$ is impossible, since $2023$ is odd and larger than $1$.

Two 1s. $2023n=2^a+2^b=2^b(2^{a-b}+1)$ with $a>b$ would need $7\mid2^c+1$ for $c=a-b\ge1$. But $2^c\bmod 7$ cycles through $2,4,1$, never $6$. Impossible.

Three 1s. $2^{77}+2^{16}+1$ is divisible by $2023$ (one can check $2^{77}\equiv-2^{16}-1$ modulo $7$ and modulo $289$ by repeated squaring). So $n=(2^{77}+2^{16}+1)/2023$ gives $k(n)=3$.

Key idea: the longest zigzag subsequence uses the two endpoints and every interior peak and valley, and no zigzag can be longer. Each interior point is a peak or valley with probability $\frac23$.

With probability $1$ all $X_i$ are distinct. Call an index $i$ with $2\le i\le n-1$ a turn if $X_i$ is larger than both neighbors (a peak) or smaller than both (a valley). Let $t$ be the number of turns. We show $a=t+2$ (for $n\ge2$).

At least $t+2$. Peaks and valleys alternate along the sequence (between two peaks the minimum is a valley). Take $X_1$, the turns in order, and $X_n$. Between consecutive chosen indices the sequence is monotone, and the direction switches at each turn. So this subsequence is zigzag.

At most $t+2$. Let $X_{i_1},\dots,X_{i_k}$ be zigzag. For $2\le j\le k-1$, the term $X_{i_j}$ is above both neighbors in the subsequence (or below both). In the first case, the maximum of $X$ on $[i_{j-1},i_{j+1}]$ is at an index strictly inside, and it is a peak of the full sequence; similarly for the second case with a valley. Two indices $j$ of the same type give peaks in the disjoint open intervals $(i_{j-1},i_{j+1})$, and indices of opposite type give a peak and a valley. So these $k-2$ turns are distinct, and $k-2\le t$.

Expectation. For an interior $i$, among three distinct values the middle position is the largest or smallest with probability $\frac23$. So $$E[a]=2+\frac23(n-2)=\frac{2n+2}{3}.$$

Key idea: the total gain is a convex function of the piece lengths, so for a fixed total time it is largest when all but one piece have their minimum length $1$. That reduces the problem to one variable.

Let $L_k=t_{k+1}-t_k\ge1$ for $0\le k\le n-1$, and let $L\ge0$ be the time spent after $t_n$. On a piece with second derivative $c$ that starts with slope $0$, $f$ rises by $\frac c2(\text{length})^2$. So the value reached at time $t_0+T$, with $T=\sum L_k+L$, is $$\frac12+\frac12V,\qquad V=\sum_{k=0}^{n-1}(k+1)L_k^2+(n+1)L^2 .$$ Since $f$ is increasing, we need the least $T$ for which some choice gives $V=4045$. (If the target is hit before $t_n$, drop the later jumps; that is a choice with smaller $n$.)

Reduction. For fixed $n$ and $T\ge n$, $V$ is convex on the simplex $\{L_k\ge1,\ L\ge0,\ \sum L_k+L=T\}$, so its maximum is at a vertex: all variables at their lower bounds except one. If the free one is $L$, then $V=g(n,T):=\frac{n(n+1)}{2}+(n+1)(T-n)^2$. If it is some $L_j$, then $L=0$ and a direct comparison shows $V\le g(j,T)$: with $a=T-n+1\ge1$ and $r=n-1-j$, $$g(j,T)-V=(j+1)\big[(a+r)^2-a^2\big]-\sum_{i=1}^{r}(j+1+i)\ge(j+1)r(r+2)-r(j+1)-\tfrac{r(r+1)}2\ge0 .$$ So the most that can be reached by time $T$ is $\max_n g(n,T)$, and this increases with $T$.

The numbers. At $T=29$: $g(9,29)=45+10\cdot20^2=4045$ exactly, and checking $n=0,\dots,28$ shows $g(n,29)\le4045$ for all of them. So no $T<29$ works, and $T=29$ does: take $n=9$, $t_k=t_0+k$, and $20$ more units after $t_9$. Then $f(t_0+29)=\frac12+\frac{45}{2}+\frac{10\cdot400}{2}=2023$.

Key idea: for $n=2n'$ with $n'$ odd, the Chinese remainder theorem splits multiplication by $m$ into two identical copies, which can be interleaved into a square root. For other $n$, a good choice of $m$ produces an odd number of cycles of some even length, which a square cannot have.

Think of $\{1,\dots,n\}$ as $\mathbb Z/n$ and let $\sigma_m(k)=mk$.

Squares have paired even cycles. If $\pi$ is a permutation, a cycle of $\pi$ of odd length $L$ becomes one cycle of length $L$ in $\pi^2$, and a cycle of even length $2\ell$ splits into two cycles of length $\ell$. So in $\pi^2$, cycles of any even length come in pairs.

Cycle structure of $\sigma_m$. The elements with $\gcd(k,n)=n/e$ are $k=(n/e)u$ with $u$ a unit modulo $e$, and $\sigma_m$ acts on them as $u\mapsto mu$ modulo $e$. So they form $\varphi(e)/\operatorname{ord}_e(m)$ cycles of length $\operatorname{ord}_e(m)$, for each divisor $e$ of $n$.

$n$ odd, $n>1$, fails. Let $p^a\,\|\,n$, $n=p^an'$. Choose $m$ with $m$ a primitive root modulo $p^a$ and $m\equiv1\pmod{n'}$. For $e=p^be'$ with $e'\mid n'$, the order of $m$ modulo $e$ is $\varphi(p^b)$. These lengths are distinct for different $b$ and even for $b\ge1$. The cycles of length $\varphi(p^a)$ come from $b=a$, and their number is $\sum_{e'\mid n'}\varphi(e')=n'$, which is odd.

$4\mid n$ fails. Write $n=2^an'$ with $a\ge2$, $n'$ odd, and choose $m\equiv-1\pmod{2^a}$, $m\equiv1\pmod{n'}$. For $e=2^be'$ the order is $2$ when $b\ge2$ and $1$ otherwise. The number of $2$-cycles is $$\sum_{b=2}^{a}\sum_{e'\mid n'}\frac{\varphi(2^be')}{2}=n'\sum_{b=2}^a2^{b-2}=n'(2^{a-1}-1),$$ which is odd.

$n=2n'$, $n'$ odd, works. By the Chinese remainder theorem, $k\leftrightarrow(k\bmod2,\ k\bmod n')$. Since $m$ is odd, $\sigma_m$ is $(\varepsilon,x)\mapsto(\varepsilon,mx)$. Define $\pi(0,x)=(1,x)$ and $\pi(1,x)=(0,mx)$. Then $\pi^2(0,x)=(0,mx)$ and $\pi^2(1,x)=\pi(0,mx)=(1,mx)$, so $\pi^2=\sigma_m$. And $n=1$ is trivial.

Key idea: counting the solutions by the value of $ai$ factors $S$ through divisibility matrices. Cauchy–Binet then turns the determinant into a short sum, and each term is read off from one easy linear system.

Step 1: factor $S$. A pair $(a,b)$ is fixed by $x=ai$, a multiple of $i$ in $[0,n]$ for which $j\mid n-x$; then $b=(n-x)/j\ge0$. So $$s(i,j)=\sum_{x=0}^{n}[\,i\mid x\,]\,[\,j\mid n-x\,],$$ where $[\cdot]$ is $1$ for true and $0$ for false (and every $i$ divides $0$). Let $A$ be the $n\times(n+1)$ matrix with $A_{i,x}=[i\mid x]$, columns $x=0,\dots,n$, and $B$ the $(n+1)\times n$ matrix with $B_{x,j}=[j\mid n-x]=A_{j,\,n-x}$. Then $S=AB$.

Step 2: Cauchy–Binet. Let $a_t$ be the determinant of $A$ with column $t$ removed. Removing row $t$ from $B$ leaves the transpose of $A$-without-column-$(n-t)$, with its $n$ rows in reverse order. Reversing $n$ rows multiplies a determinant by $\varepsilon=(-1)^{n(n-1)/2}$. So $$\det S=\varepsilon\sum_{t=0}^{n}a_t\,a_{n-t}.$$

Step 3: the minors. Column $0$ of $A$ is all ones. The other columns form $Z$, with $Z_{i,x}=[i\mid x]$ for $1\le i,x\le n$. It is upper triangular with ones on the diagonal (a divisor is never bigger than the number), so $\det Z=1$ and $a_0=1$. For $t\ge1$, slide the ones column past columns $1,\dots,t-1$ ($t-1$ swaps) into the empty slot. The result is $Z$ with column $t$ replaced by $\mathbf 1=(1,\dots,1)^T$. By Cramer’s rule, $$a_t=(-1)^{t-1}u_t,\qquad\text{where } Zu=\mathbf 1 .$$

Step 4: what we know about $u$. Row $i$ of $Zu=\mathbf 1$ says that the sum of $u_x$ over the multiples $x\le n$ of $i$ is $1$.

• If $t>n/2$, the only multiple of $t$ up to $n$ is $t$, so $u_t=1$.
• If $n$ is even, row $n/2$ gives $u_{n/2}+u_n=1$, so $u_{n/2}=0$.
• Row $1$ gives $u_1+\dots+u_n=1$.

There are $n-\lfloor n/2\rfloor=h$ indices above $n/2$, where $h=\lceil n/2\rceil$. So the last two facts give $\sum_{1\le s<n/2}u_s=1-h$.

Step 5: add up. The terms $t=0$ and $t=n$ each equal $a_n=(-1)^{n-1}u_n=(-1)^{n-1}$. For $1\le t\le n-1$, $a_ta_{n-t}=(-1)^{n}u_tu_{n-t}$. If $t\ne n/2$, exactly one of $t,n-t$ is above $n/2$, and that factor is $1$. So each $s<n/2$ shows up twice (as $t=s$ and $t=n-s$), and the middle term $t=n/2$, if there is one, is $u_{n/2}^2=0$. Hence $$\sum_{t=0}^{n}a_ta_{n-t}=2(-1)^{n-1}+2(-1)^{n}(1-h)=(-1)^{n-1}\,2h .$$

Step 6: the sign. $\det S=(-1)^{n(n-1)/2+n-1}\,2h$. For $n=2h-1$ the exponent is $(2h-1)(h-1)+2h-2$, which has the parity of $h-1$. For $n=2h$ it is $h(2h-1)+2h-1$, which has the parity of $h+1$. Either way $\det S=(-1)^{h-1}\,2h$. For $n=5$ this gives $6$, and the sequence for $n=1,2,3,\dots$ is $2,2,-4,-4,6,6,-8,-8,\dots$