Putnam 2022

Key idea: count zeros of $f(x)=\ln(1+x^2)-ax-b$ from the shape of its graph. Everything depends on how $a$ compares with the range $[-1,1]$ of $\frac{2x}{1+x^2}$.

We have $f'(x)=\frac{2x}{1+x^2}-a$, and $\left|\frac{2x}{1+x^2}\right|\le1$ with equality only at $x=\pm1$. Also $\ln(1+x^2)$ grows more slowly than any line, so for $a\ne0$, $f(x)\to\pm\infty$ with opposite signs at the two ends.

$|a|\ge1$. $f'$ has one sign everywhere, vanishing at most at one point, so $f$ is strictly monotone. Its end values have opposite signs, so there is exactly one zero, for every $b$.

$a=0$. $\ln(1+x^2)=b$ has one solution for $b=0$, two for $b>0$, none for $b<0$. Only $(0,0)$ works.

$0<a<1$. $f'(x)=0$ means $ax^2-2x+a=0$, with roots $0<r_-<r_+$ as in the answer. So $f$ decreases on $(-\infty,r_-]$ from $+\infty$, increases on $[r_-,r_+]$, and decreases on $[r_+,\infty)$ to $-\infty$. There is exactly one zero when the local minimum is positive (the only zero is after $r_+$) or the local maximum is negative (the only zero is before $r_-$). If $f(r_-)\le0\le f(r_+)$, there are at least two zeros. So the condition is $f(r_-)>0$ or $f(r_+)<0$, which is $b<\ln(1+r_-^2)-ar_-$ or $b>\ln(1+r_+^2)-ar_+$.

$-1<a<0$. Replacing $x$ by $-x$ turns the line $y=ax+b$ into $y=-ax+b$ and leaves the curve unchanged. So $(a,b)$ works exactly when $(|a|,b)$ does.

Key idea: if all $2n-1$ middle coefficients were negative, then $p$ would be the square root of $1-U$ to high order, with $U$ having positive coefficients. Such a square root has negative coefficients in every degree up to $2n-1$, which a degree-$n$ polynomial cannot have.

Write $q=p^2=\sum_{k=0}^{2n}c_kx^k$ with $p=\sum a_ix^i$. Then $c_{2n}=a_n^2>0$ and $c_0=a_0^2\ge0$, so at most $2n-1$ coefficients are negative.

$2n-1$ is impossible. Suppose $c_1,\dots,c_{2n-1}<0$. Then $c_1=2a_0a_1\ne0$, so $a_0\ne0$. Dividing $p$ by $a_0$ multiplies every $c_k$ by $a_0^{-2}>0$, so we may assume $a_0=1$. Then $$q=1-U+c_{2n}x^{2n},\qquad U=\sum_{k=1}^{2n-1}|c_k|x^k ,$$ where $U$ has positive coefficients. As formal power series, $p$ is the square root of $q$ with constant term $1$, and it is determined by $q$ one degree at a time; so modulo $x^{2n}$, $p$ agrees with $$\sqrt{1-U}=1-\tfrac12U-\tfrac18U^2-\tfrac1{16}U^3-\cdots=1-\sum_{j\ge1}\beta_jU^j,\qquad\beta_j>0 .$$ Each $U^j$ has nonnegative coefficients, and $U$ itself has positive coefficient in every degree $1,\dots,2n-1$. So $\sqrt{1-U}$ has a strictly negative coefficient in every degree $1,\dots,2n-1$. But $p$ has degree $n$, so its coefficient of $x^{n+1}$ is $0$, and $n+1\le2n-1$ for $n\ge2$. Contradiction.

$2n-2$ is possible. Take $$p(x)=1-\varepsilon(x+x^2+\dots+x^{n-1})+x^n,\qquad \varepsilon=\tfrac1n .$$ For $1\le k\le n-1$, the coefficient of $x^k$ in $p^2$ is $-2\varepsilon+(k-1)\varepsilon^2<0$. For $n+1\le k\le2n-1$, it is $-2\varepsilon$ plus at most $(n-2)\varepsilon^2$, also negative. That is $2(n-1)=2n-2$ negative coefficients (the coefficient of $x^n$ is positive).

Key idea: the recurrence is periodic with period $5$. So shifting the sequence acts on valid sequences with orbits of size $1$ or $5$, and the fixed points are the solutions of $x^2=x+1$.

Each term is $a_{n+2}=(1+a_{n+1})/a_n$, so a sequence is fixed by $(a_1,a_2)=(x,y)$, as long as no term is $0$. Computing, $$a_3=\frac{1+y}{x},\quad a_4=\frac{1+x+y}{xy},\quad a_5=\frac{1+x}{y},\quad a_6=x,\quad a_7=y,$$ so the sequence repeats with period $5$. It is valid exactly when $x$, $y$, $1+x$, $1+y$, $1+x+y$ are all nonzero modulo $p$; then all terms are nonzero and every step is defined. So $f(p)$ is the number of valid pairs.

The shift $T(a_1,a_2,\dots)=(a_2,a_3,\dots)$ maps valid sequences to valid sequences, and $T^5$ is the identity. Each orbit has size dividing $5$, so size $1$ or $5$. Hence $$f(p)\equiv\#\{\text{fixed points of }T\}\pmod5 .$$ A fixed point is a constant sequence $a_n=x$, which needs $x^2=1+x$. These are valid: $x=0$ and $x=-1$ do not satisfy $x^2=x+1$, and $1+2x=0$ would give $x=-\frac12$ and then $\frac14=\frac12$, impossible for $p>5$.

The quadratic $x^2-x-1$ has discriminant $5$, which is nonzero modulo $p$. So it has either $0$ or $2$ roots. Therefore $f(p)\equiv0$ or $2\pmod5$.

Key idea: by linearity we only need $E[X_i;\,X_1>\dots>X_i]$, which is a beta integral equal to $\frac1{(i+1)!}$.

The term $X_i/2^i$ appears in $S$ exactly when $k\ge i$, that is, when there is no rise among $X_1,\dots,X_i$, i.e. $X_1>X_2>\dots>X_i$ (ties have probability $0$). So $$E[S]=\sum_{i\ge1}2^{-i}\,E\big[X_i\,;\,X_1>\dots>X_i\big].$$ Condition on $X_i=x$. The other $i-1$ values must all exceed $x$ (probability $(1-x)^{i-1}$) and be in decreasing order (probability $\frac1{(i-1)!}$). Hence $$E\big[X_i;\,X_1>\dots>X_i\big]=\int_0^1x\,\frac{(1-x)^{i-1}}{(i-1)!}\,dx=\frac{1}{(i-1)!}\cdot\frac{1!\,(i-1)!}{(i+1)!}=\frac1{(i+1)!}.$$ Therefore $$E[S]=\sum_{i\ge1}\frac{2^{-i}}{(i+1)!}=2\sum_{j\ge2}\frac{(1/2)^j}{j!}=2\Big(e^{1/2}-1-\frac12\Big)=2\sqrt e-3\approx0.2974 .$$

Key idea: give each uncovered block a score that depends only on its length mod $7$. Most blocks are worth a fixed number of leftover squares. Blocks of length $\equiv4$ or $6\pmod 7$ are switches: one more square for Alice if she gets to play there first, one less if Bob does. This gives the exact value of every position, and the whole strip, $2022\equiv6\pmod7$, is a single switch.

Positions. At any moment the uncovered squares form maximal runs of consecutive squares; call them blocks. Placing a tile inside a block of length $L\ge2$ leaves two blocks of lengths $a,b\ge0$ with $a+b=L-2$. Blocks of length $0$ or $1$ are never touched again. The game ends when every block has length at most $1$, and the final count is the number of blocks of length $1$. Blocks never interact, so a position is just a list of lengths.

The score. Write $L=7q+r$ with $0\le r\le6$ and set $$m(L)=q+\mu_r,\qquad(\mu_0,\mu_1,\mu_2,\mu_3,\mu_4,\mu_5,\mu_6)=(0,1,0,1,1,1,1).$$ Call $L$ a switch if $r=4$ or $r=6$. For a position with block lengths $L_1,\dots,L_k$, let $M=\sum_i m(L_i)$ and let $s$ be the number of switches among the $L_i$. Write $[P]$ for $1$ if $P$ is true and $0$ otherwise.

Theorem. With best play from a given position, the final number of uncovered squares is $$M+[s\text{ odd}]\ \text{ if Alice moves next},\qquad M-[s\text{ odd}]\ \text{ if Bob moves next}.$$ At the start there is one block, $2022=7\cdot288+6$. It is a switch with $m=289$, and Alice moves first, so the answer is $289+1=290$.

Lemma (one move). Say a move replaces a block $L$ by blocks $a,b$, and let $\Delta=m(a)+m(b)-m(L)$. Then either $\Delta=0$ and an even number of the three lengths $a,b,L$ are switches, or $\Delta=\pm1$ and an odd number of them are.

Proof. Adding $7$ to $a$ adds $7$ to $L$. That raises both $m(a)$ and $m(L)$ by $1$ and changes neither one’s switch status. The same holds for $b$, so it is enough to check $0\le a,b\le6$, where $L=a+b+2\le14$. Here is $\Delta$ for each pair (row $a$, column $b$): $$\begin{array}{c|ccccccc} & 0&1&2&3&4&5&6\\ \hline 0&0&0&-1&0&0&0&-1\\ 1&0&+1&0&+1&+1&0&+1\\ 2&-1&0&-1&0&-1&0&-1\\ 3&0&+1&0&0&+1&0&0\\ 4&0&+1&-1&+1&0&0&0\\ 5&0&0&0&0&0&0&0\\ 6&-1&+1&-1&0&0&0&0\end{array}$$ For example, $a=1,b=3$ gives $L=6$ and $\Delta=1+1-1=1$, and only $L$ is a switch. In every cell, $\Delta\ne0$ exactly when an odd number of $a,b,L$ have residue $4$ or $6$. (Each of the $28$ cells with $a\le b$ takes one line to check; we also checked all $a,b<200$ by computer.) $\square$

So every move either keeps $M$ and the parity of $s$, or changes $M$ by $1$ and flips the parity of $s$.

Proof of the theorem, by induction on the number of moves left. When no move is possible, every block has length $0$ or $1$. Then $m(0)=0$, $m(1)=1$, $s=0$, and $M$ is the count of uncovered squares, as claimed.

Now let Alice move. After a move with change $\Delta$ and new switch count $s'$, the induction hypothesis (Bob to move) says the result is $M+\Delta-[s'\text{ odd}]$.

• She can’t do better than $M+[s\text{ odd}]$. If $\Delta=0$, then $s'\equiv s$ and the result is $M-[s\text{ odd}]$. If $\Delta=\pm1$, the parity flips, so $[s\text{ odd}]+[s'\text{ odd}]=1$ and the result is at most $M+1-[s'\text{ odd}]=M+[s\text{ odd}]$.
• She can reach it. If some block is a switch, she plays in it leaving a single square at one end ($a=1$). For $r=4$ the other piece has residue $1$; for $r=6$ it has residue $3$. The table gives $\Delta=+1$ in both cases, and the result is $M+1-[s'\text{ odd}]=M+[s\text{ odd}]$. If there is no switch ($s=0$), she makes a move with $\Delta=0$ (see below), and the result is $M=M+[s\text{ odd}]$.

Bob’s case is the mirror image. The result after his move is $M+\Delta+[s'\text{ odd}]$, which is at least $M-[s\text{ odd}]$ by the same two cases. He reaches it as follows. In a switch with $r=4$, he places his tile against one end ($a=0$, other piece residue $2$); with $r=6$, he leaves two squares at one end ($a=2$, other piece residue $2$). Both give $\Delta=-1$. With no switch, he makes a $\Delta=0$ move.

A $\Delta=0$ move exists in any block of length $L\ge2$ that is not a switch. For $r\in\{0,2,3,5\}$, put the tile against an end (row $0$ of the table). For $r=1$, where $L\ge8$, leave one square at an end (cell $a=1$, $b\equiv5$). This finishes the induction. $\blacksquare$

In plain terms: Alice’s good moves leave a single square at the end of a block, and Bob’s mostly put his tile right against an end.

Key idea: the conditions say a certain step function in $s=t^2$ is orthogonal to all polynomials of degree below $m$. Such a function must change sign at least $m$ times, but $2n$ endpoints allow at most $n$ sign changes. Equally spaced cosines reach $m=n$.

Let $U=\bigcup_i[x_{2i-1},x_{2i}]\subset(-1,1)$. Then $\sum_i\big(x_{2i}^{2k-1}-x_{2i-1}^{2k-1}\big)=(2k-1)\int_Ut^{2k-2}\,dt$.

Upper bound $m\le n$. Substitute $s=t^2$ on the positive and negative parts of $U$: $$\int_Ut^{2k-2}dt=\int_0^1s^{k-1}\frac{c(s)}{2\sqrt s}\,ds,\qquad c(s)=[\sqrt s\in U]+[-\sqrt s\in U]\in\{0,1,2\}.$$ Since $(2k-1)\int_0^1s^{k-1}\frac{ds}{2\sqrt s}=1$, the condition for $k$ becomes $$\int_0^1s^{k-1}\,\nu(s)\,ds=0,\qquad \nu(s)=\frac{c(s)-1}{2\sqrt s}.$$ If this holds for $k=1,\dots,m$, then $\int\nu q=0$ for every polynomial $q$ of degree below $m$. Now $\nu$ is not zero almost everywhere: near $s=1$ both $\pm\sqrt s$ lie outside $U$, so $c=0$ there. If $\nu$ changed sign at only $j<m$ points $s_1,\dots,s_j$, then $q=\prod(s-s_i)$ would make $\nu q$ of one sign and not zero, so $\int\nu q\ne0$. Hence $\nu$ changes sign at least $m$ times.

The function $c$ jumps only at the squares of the $2n$ endpoints, and each endpoint changes $c$ by $1$. A sign change of $c-1$ means going from $c=0$ to $c=2$ or back, which uses up at least two endpoints. So there are at most $n$ sign changes, and $m\le n$.

Construction with $m=n$. Let $\theta=\frac{\pi}{2n+1}$ and $z_j=\cos j\theta$ for $j=1,\dots,2n$. These decrease from near $1$ to near $-1$. Take $x_1=z_{2n}<x_2=z_{2n-1}<\dots<x_{2n}=z_1$. Then the sum for exponent $p=2k-1$ is $\sum_{j=1}^{2n}(-1)^{j+1}z_j^p$.

For odd $q$ with $1\le q\le2n-1$, $e^{iq\theta}\ne-1$, and a geometric sum gives $$\sum_{j=0}^{2n}(-1)^j\cos(jq\theta)=\operatorname{Re}\frac{1-(-e^{iq\theta})^{2n+1}}{1+e^{iq\theta}}=0,$$ because $(-1)^{2n+1}e^{iq\pi}=1$. So $\sum_{j=1}^{2n}(-1)^{j+1}\cos(jq\theta)=1$. For odd $p\le2n-1$, the power $\cos^px$ is $2^{1-p}\sum_{q}\binom{p}{(p-q)/2}\cos qx$ over odd $q\le p$, and these binomial coefficients add up to $2^{p-1}$. Hence $$\sum_{j=1}^{2n}(-1)^{j+1}z_j^{\,p}=2^{1-p}\sum_q\binom{p}{(p-q)/2}=1$$ for $p=1,3,\dots,2n-1$, that is, for $k=1,\dots,n$. So $m=n$.

Key idea: the numbers $c_k=k!\,b_k$ are integers, and modulo $2$ they satisfy $c_{k+1}\equiv a_1c_k$. So they are all odd.

Comparing coefficients of $x^k$ in $(e^{P})'=P'\,e^{P}$ gives $$(k+1)b_{k+1}=\sum_{j=1}^{n}j\,a_j\,b_{k+1-j}\qquad(b_i=0\text{ for }i<0).$$ Multiply by $k!$ and put $c_k=k!\,b_k$: $$c_{k+1}=\sum_{j=1}^{n}j\,a_j\cdot k(k-1)\cdots(k-j+2)\cdot c_{k+1-j}.$$ Here $k(k-1)\cdots(k-j+2)=k!/(k+1-j)!$ is a product of $j-1$ consecutive integers. Since $c_0=b_0=1$, induction shows every $c_k$ is an integer.

Look modulo $2$. The $j=1$ term is $a_1c_k$. For $j\ge2$, the factor $j\cdot k(k-1)\cdots(k-j+2)$ is even: if $j$ is even, $j$ is; if $j\ge3$ is odd, the product has at least two consecutive integers. So $$c_{k+1}\equiv a_1c_k\equiv c_k\pmod2 ,$$ since $a_1$ is odd. With $c_0=1$, every $c_k$ is odd, hence nonzero, and $b_k=c_k/k!\ne0$.

Key idea: crossing repeatedly with a fixed $v\in S$ scales lengths by $|v|$, so finiteness forces $|v|=1$. Then all cross products of unit vectors in $S$ have length $0$ or $1$, which pins $S$ down to a coordinate frame.

Examples. $S=\{0\}$ works ($n=1$). So does $S=\{0,\pm e_1,\pm e_2,\pm e_3\}$ ($n=7$): products of these are $0$ or $\pm e_i$, and each element arises, e.g. $0=e_1\times e_1$ and $\pm e_3=\pm e_1\times e_2$.

Nothing else. Let $S$ be finite with $S=\{v\times w\}$, and $S\ne\{0\}$. Then $0=v\times v\in S$. If all nonzero vectors of $S$ were parallel, all cross products would be $0$. So $S$ has two nonparallel nonzero vectors, and every nonzero $v\in S$ is nonparallel to at least one $w\in S$.

Lengths are $1$. Given such $v,w$, let $x_0=v\times w\ne0$, which is perpendicular to $v$, and $x_{k+1}=v\times x_k$. All $x_k$ lie in $S$, stay perpendicular to $v$, and have $|x_{k+1}|=|v|\,|x_k|$. A finite set cannot contain vectors of lengths $|v|^k|x_0|$ for all $k$ unless $|v|=1$.

Angles are $0$, $90^\circ$ or $180^\circ$. For unit $v,w\in S$, the vector $v\times w\in S$ has length $|\sin\angle(v,w)|\in\{0,1\}$.

So the nonzero vectors of $S$ are unit vectors along at most three mutually perpendicular lines. If $u,w\in S$ are perpendicular, then $u\times w$ is a unit vector along the third line, and crossing with $u$ turns vectors in the plane perpendicular to $u$ by $90^\circ$, which produces $\pm w$ and $\pm(u\times w)$. Doing the same with $w$ produces $\pm u$. So $S=\{0,\pm e_1,\pm e_2,\pm e_3\}$ for some orthonormal frame, and $n=7$.

Key idea: after one recoloring, the blue set $B$ contains no sum or difference of two of its elements. If some $t$ were blue after the next step, colors would alternate along steps of $t$, and $t/2$ or $3t/2$ would break that rule.

Call the colorings $c_0$ (given), $c_1$, $c_2$. A number $d$ is blue in $c_1$ when $c_0(x+d)\ne c_0(x)$ for all $x>0$.

Rules for $B$, the blue set of $c_1$. Let $d,e\in B$. Then $c_0(x+d)\ne c_0(x)$ and $c_0(x+d+e)\ne c_0(x+d)$, so with two colors $c_0(x+d+e)=c_0(x)$: so $d+e\notin B$ (including $d=e$, so $2d\notin B$). If $d>e$, then $c_0(x+d)$ and $c_0(x+e)$ both differ from $c_0(x)$, so they are equal and $d-e\notin B$.

The second step. If $B$ is empty, $c_1$ is all red and every distance is a same-color distance, so $c_2$ is all red. Suppose instead some $t>0$ is blue in $c_2$. Then $c_1(x+t)\ne c_1(x)$ for all $x$, so $c_1(x+2t)=c_1(x)$: the coloring $c_1$ flips along steps of $t$ and repeats after $2t$.

Here $B$ is not empty (otherwise $c_2$ would be all red). Take $d\in B$. Then $d+2t\in B$, and their difference $2t$ is not in $B$. By the flipping, $3t\in B$, and by the repetition, $t\in B$.

Now look at $t/2$. If $t/2\in B$, then $t/2+t/2=t$ would not be in $B$; but $t\in B$. If $t/2\notin B$, then by flipping $3t/2\in B$, so $3t/2+3t/2=3t\notin B$; but $3t\in B$. Either way we get a contradiction.

So no number is blue in $c_2$: after at most two recolorings everything is red, and it stays red.

Key idea: in terms of the gaps $d_i$, each condition says consecutive gaps have ratio $1$, $-2$ or $-\frac12$, and the gaps add to $0$. Modulo $3$ all gaps agree, which forces $3\mid n$. A short case check rules out $n=6$, and an explicit pattern works for $n=3k\ge9$.

Indices are cyclic. Put $d_i=x_{i+1}-x_i$, nonzero since the $x_i$ are distinct, with $\sum d_i=0$. Shift so $x_i=0$: the triple is $0,\,d_i,\,d_i+d_{i+1}$. It is a progression when one entry is the average of the other two, which gives $d_{i+1}=d_i$, $d_{i+1}=-2d_i$, or $d_{i+1}=-\frac12d_i$.

$3\mid n$. Scale so $d_1$ is a large power of $2$; then every $d_i$ is $\pm$ a power of $2$, an integer. Since $-2\equiv1$ and, when $d_i=-2d_{i+1}$, also $d_{i+1}\equiv d_i\pmod3$, all $d_i$ are congruent to $d_1\not\equiv0\pmod 3$. Then $0=\sum d_i\equiv nd_1$, so $3\mid n$.

$n=6$ fails. Group equal consecutive gaps into blocks. Neighboring blocks have ratio $-2$ or $-\frac12$, so signs alternate and the number of blocks is even; one block is impossible because the sum would not be $0$. Up to scaling, rotation, reflection and sign:

• Two blocks $1,-2$: lengths $4,2$; the walk $0,1,2,3,4,2$ repeats $2$.
• Four blocks $1,-2,1,-2$: lengths $(L_1,1,L_3,1)$ with $L_1+L_3=4$; each case revisits a point (for example $0,1,-1,0$).
• Four blocks $1,-2,4,-2$: lengths $(2,1,1,2)$ or $(2,2,1,1)$; both walks return to $0$ early.
• Six blocks $d_i=(-1)^i2^{h_i}$, where $h$ moves by $\pm1$ each step and returns. Of the four cyclic shapes, only $h=(0,1,2,1,0,1)$ has $\sum d_i=0$, and its walk $0,1,-1,3,1,\dots$ repeats $1$.

So $n=6$ is impossible. (A computer search over all ratio patterns confirms there is no solution for $4\le n\le8$.)

$n=3k$, $k\ge3$, works. Use the gaps $$\underbrace{2,\dots,2}_{2k-3},\ -1,\ 2,\ \underbrace{-4,\dots,-4}_{k-1},\ 2,\ -1 .$$ Consecutive ratios are $1,-\frac12,-2,-2,1,-\frac12,-\frac12,-2$, all allowed (the last ratio wraps around). The sum is $2(2k-3)-1+2-4(k-1)+2-1=0$. Starting at $0$, the points are the even numbers $0,2,\dots,4k-6$, then $4k-7$ and $4k-5$, then $4k-9,4k-13,\dots,-1$ (all $\equiv3\pmod4$ and below $4k-5$), then $1$. These $3k$ numbers are distinct because $4k-7\equiv1\pmod 4$ differs from $1$ when $k\ge3$.

Key idea: for $p\le\frac14$ each characteristic function is nonnegative, which makes $0$ the most likely value. For $p>\frac14$, one odd weight and many weights $2$ make $1$ more likely than $0$.

Let $\varphi(\theta)=1-2p+2p\cos\theta$, the characteristic function of each $X_i$. By Fourier inversion on the integers, $$P(b,a_1,\dots,a_n)=\frac1{2\pi}\int_{-\pi}^{\pi}e^{-ib\theta}\prod_{i}\varphi(a_i\theta)\,d\theta .$$

$p\le\frac14$ works. Then $\varphi\ge1-4p\ge0$, so the product is nonnegative and $$P(b,\dots)\le\frac1{2\pi}\int\prod_i\varphi(a_i\theta)\,d\theta=P(0,\dots).$$

$p>\frac13$ fails. With $n=1$, $a_1=1$: $P(0)=1-2p<p=P(1)$.

$\frac14<p\le\frac13$ fails. Take $a_1=1$, $a_2=\dots=a_{m+1}=2$, $b=1$, and let $T=X_2+\dots+X_{m+1}$, $u=P(T=0)$, $v=P(T=1)$. The sum is $X_1+2T$. It is $0$ only when $X_1=0,T=0$, and $1$ when $X_1=1,T=0$ or $X_1=-1,T=1$. So $$P(0)-P(1)=(1-2p)u-pu-pv=(1-3p)u-pv ,$$ which is negative once $v/u>\frac{1-3p}{p}$. Since $p>\frac14$, the right side is less than $1$. So it is enough to show $v/u\to1$ as $m\to\infty$ through even values.

For even $m$, $\varphi^m\ge0$, and $u-v=\frac1{2\pi}\int(1-\cos\theta)\varphi^m$, $u=\frac1{2\pi}\int\varphi^m$. Fix $\delta>0$. On $|\theta|<\delta$, $1-\cos\theta\le\delta^2/2$. Off it, $|\varphi|\le\rho<1$ for some $\rho$ (because $p>0$ and $-1<1-4p<0$), so that part of $\int(1-\cos\theta)\varphi^m$ is at most $4\pi\rho^m$. Meanwhile, on $|\theta|<1/\sqrt m$ we have $\varphi\ge1-p\theta^2\ge1-p/m$, so $\int\varphi^m\ge\frac{2}{\sqrt m}(1-\frac pm)^m\ge\frac{c}{\sqrt m}$ for a constant $c>0$. Therefore $$\frac{u-v}{u}\le\frac{\delta^2}{2}+\frac{4\pi\rho^m\sqrt m}{c}\longrightarrow\frac{\delta^2}{2}.$$ As $\delta$ is arbitrary, $v/u\to1$.

Key idea: a choice of $y$ that makes $xf(y)=x+y$ cancels two terms. That rules out values above $1$ unless $f\equiv1$. Once $0<f<1$, the equation forces $f$ to decrease, and letting one variable run off to infinity pins down $f$ exactly.

Write $P(x,y)$ for the equation at $(x,y)$.

These work. For $f(x)=\frac1{1+cx}$ with $c\ge0$, $$f(xf(y))=\frac{1+cy}{1+cx+cy},\qquad f(xf(y))+f(yf(x))=\frac{2+cx+cy}{1+cx+cy}=1+f(x+y).$$

Step 1: where $f=1$. Let $Z=\{t>0: f(t)=1\}$. It is closed in $(0,\infty)$ because $f$ is continuous. For $a,b\in Z$, $P(a,b)$ reads $1+1=1+f(a+b)$, so $a+b\in Z$.

Step 2: the cancelling trick. If $f(y)=1+\frac yx$, then $xf(y)=x+y$, and $P(x,y)$ leaves $f(yf(x))=1$. In particular, if $f(a)>1$ for some $a$, take $y=a$ and $x=\frac{a}{f(a)-1}$: then $af(x)\in Z$, so $Z$ is not empty.

Step 3: if $Z$ is not empty, then $f\equiv1$.

• If $Z$ has arbitrarily small elements: for $z\in Z$, all multiples $nz$ are in $Z$, and they come within $z$ of every number $t\ge z$. So $Z$ is dense, and being closed it is all of $(0,\infty)$.
• Otherwise $z_0=\min Z>0$ exists. On $(0,z_0)$, $f\ne1$, so either $f<1$ there or $f>1$ there.
• If $f<1$ on $(0,z_0)$: take $0<x<z_0$ and $y=z_0-x$. Then $xf(y)<x<z_0$ and $yf(x)<y<z_0$, so the left side of $P(x,y)$ is less than $2$, while the right side is $1+f(z_0)=2$. Contradiction.
• If $f>1$ on $(0,z_0)$: fix $y_1\in(0,z_0)$ and choose $n$ with $x=nz_0>\frac{y_1}{f(y_1)-1}$. Then $x\in Z$. The continuous function $y\mapsto f(y)-1-\frac yx$ is positive at $y_1$ and equals $-\frac{z_0}{x}<0$ at $z_0$, so it vanishes at some $y\in(y_1,z_0)$. By Step 2, $f(yf(x))=1$. But $f(x)=1$, so $f(y)=1$ with $y<z_0$. Contradiction.

So from now on suppose $f\not\equiv1$. Then $Z$ is empty, and by Step 2, $f\le1$. Hence $0<f<1$ everywhere.

Step 4: $\limsup_{t\to0^+}f(t)=1$. Call this limsup $B\le1$. If $B=0$, then $f(t)\to0$, and letting $x\to0$ in $P(x,y)$ gives $0+0=1+f(y)$, which is impossible. If $0<B<1$, take $x_n\to0$ with $f(x_n)\to B$. Along a subsequence, $f(x_nf(y))\to\mu$ for some $\mu\le B$, so $P(x_n,y)$ gives in the limit $$f(By)=1+f(y)-\mu\ge f(y)+(1-B).$$ Replacing $y$ by $y/B$ repeatedly, $f(y/B^k)\le f(y)-k(1-B)$, which is negative for large $k$. Contradiction. So $B=1$.

Step 5: $f$ is strictly decreasing. Since $f(xf(y))<1$, $P(x,y)$ gives $f(yf(x))>f(x+y)$ for all $x,y>0$. Now take any $0<v<u$. The function $k(x)=(u-x)f(x)$ on $(0,u)$ is continuous, tends to $0$ as $x\to u$, and has limsup $u\cdot B=u$ as $x\to0$. So $k(x)=v$ for some $x$. With $y=u-x$ we get $yf(x)=v$ and $x+y=u$, so $f(v)>f(u)$. As a result, $f(t)\to1$ as $t\to0^+$.

Step 6: behavior at infinity. Let $L=\lim_{t\to\infty}f(t)<1$. If $L>0$, then $xf(x)\ge Lx\to\infty$, and $P(x,x)$, which says $2f(xf(x))=1+f(2x)$, gives $2L=1+L$ in the limit. That is impossible, so $L=0$. Then $f$ maps $(0,\infty)$ onto $(0,1)$, decreasing, with a continuous inverse. From $P(x,x)$, $f(xf(x))\to\frac12$, so $xf(x)\to\kappa$, where $\kappa$ is the point with $f(\kappa)=\frac12$.

Step 7: the exact form. Let $g(x)=\frac1{f(x)}-1>0$ and $\psi(s)=1-f(s)$. Rewrite $P(x,y)$ and multiply by $y$: $$y\,\psi\big(xf(y)\big)=y\,f\big(yf(x)\big)-y\,f(x+y).$$ Fix $x$ and let $y\to\infty$. By Step 6, $y\,f(x+y)\to\kappa$, and $y f(yf(x))=\frac{t f(t)}{f(x)}$ with $t=yf(x)\to\infty$, so it tends to $\frac{\kappa}{f(x)}$. The right side therefore tends to $\kappa\,g(x)$. On the left, put $s=xf(y)$. Then $y=\frac{x\,yf(y)}{s}$, so the left side is $x\,yf(y)\cdot\frac{\psi(s)}{s}$, and $yf(y)\to\kappa$. Hence $$\frac{\psi(s)}{s}\longrightarrow\frac{g(x)}{x}\quad\text{as } y\to\infty .$$ As $y$ increases to $\infty$, $s=xf(y)$ decreases continuously to $0$. So the limit $\ell=\lim_{s\to0^+}\psi(s)/s$ exists, and $g(x)/x=\ell$ for every $x$. It does not depend on $x$. So $g(x)=\ell x$ with $\ell>0$, and $f(x)=\frac1{1+\ell x}$.

Together with $f\equiv1$ (the case $c=0$), the solutions are exactly $f(x)=\frac1{1+cx}$ with $c\ge0$.