Putnam 1999

Key idea: $|\,\text{linear}\,|$ creates one bend; choose $f$ to vanish at $-1$ and $g$ to vanish at $0$ with the right slope changes, then fix up with a linear $h$.

The target has slope $0$, then $3$, then $-2$. So the slope jumps by $+3$ at $x=-1$ and by $-5$ at $x=0$.

• $|f|$ with $f(x)=\frac32(x+1)$ has slope $-\frac32$ then $+\frac32$: a jump of $+3$ at $-1$.
• $-|g|$ with $g(x)=\frac52x$ has slope $+\frac52$ then $-\frac52$: a jump of $-5$ at $0$.

Then $h$ must be linear. For $x>0$ we need $\frac32(x+1)-\frac52x+h(x)=-2x+2$, so $h(x)=-x+\frac12$. Check the other pieces:

• $x<-1$: $-\frac32(x+1)+\frac52x-x+\frac12=-1$. ✓
• $-1\le x\le0$: $\frac32(x+1)+\frac52x-x+\frac12=3x+2$. ✓

So $f(x)=\frac{3x+3}{2}$, $g(x)=\frac{5x}{2}$, $h(x)=-x+\frac12$ work.

Key idea: factor $p$ into a square times quadratics $(x-a)^2+b^2$; each factor is a sum of two squares, and such sums are closed under multiplication.

If $p=0$ we are done. Otherwise, since $p\ge0$, its leading coefficient $c$ is positive. Each real root has even multiplicity (else $p$ changes sign there), and the non-real roots come in conjugate pairs $a\pm bi$. So $$p(x)=c\,q(x)^2\prod_j\big((x-a_j)^2+b_j^2\big)$$ for a real polynomial $q$. Each factor $(x-a_j)^2+b_j^2$ is a sum of two squares of real polynomials, and $$(F^2+G^2)(U^2+V^2)=(FU-GV)^2+(FV+GU)^2 .$$ Multiplying the factors together, $\prod_j(\dots)=F^2+G^2$ for real polynomials $F,G$ (an empty product is $1^2+0^2$). Then $$p=\big(\sqrt c\,qF\big)^2+\big(\sqrt c\,qG\big)^2 .$$

Key idea: with the closed form, the cross terms cancel because $\alpha\beta=-1$, and $1+\alpha^2$ is a multiple of $\alpha$.

The coefficients satisfy $a_n=2a_{n-1}+a_{n-2}$ with $a_0=1$, $a_1=2$. Let $\alpha=1+\sqrt2$, $\beta=1-\sqrt2$ (roots of $t^2-2t-1$). Then $$a_n=\frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta},\qquad\alpha-\beta=2\sqrt2,$$ which matches $a_0=1$, $a_1=2$ and the recurrence. Now $$8\big(a_n^2+a_{n+1}^2\big)=\alpha^{2n+2}+\beta^{2n+2}+\alpha^{2n+4}+\beta^{2n+4}-2(\alpha\beta)^{n+1}-2(\alpha\beta)^{n+2}.$$ Since $\alpha\beta=-1$, the last two terms cancel. Also $1+\alpha^2=4+2\sqrt2=2\sqrt2\,\alpha$ and $1+\beta^2=4-2\sqrt2=-2\sqrt2\,\beta$. So $$8\big(a_n^2+a_{n+1}^2\big)=2\sqrt2\big(\alpha^{2n+3}-\beta^{2n+3}\big),\qquad a_n^2+a_{n+1}^2=\frac{\alpha^{2n+3}-\beta^{2n+3}}{2\sqrt2}=a_{2n+2}.$$ So $m=2n+2$ works.

Key idea: in terms of $x_k=k/3^k$ the term is $\frac{x_m^2x_n}{x_m+x_n}$; adding the swapped copy gives $x_mx_n$, so the sum is half of $(\sum x_k)^2$.

Let $x_k=\frac{k}{3^k}$. Dividing numerator and denominator by $3^{2m}3^n$, $$\frac{m^2n}{3^m(n3^m+m3^n)}=\frac{x_m^2x_n}{x_n+x_m}.$$ Call the double sum $S$. All terms are positive, so we may reorder freely; swapping the names $m,n$ gives $S=\sum\frac{x_n^2x_m}{x_m+x_n}$. Adding, $$2S=\sum_{m,n}\frac{x_mx_n(x_m+x_n)}{x_m+x_n}=\Big(\sum_kx_k\Big)^2 .$$ With $\sum_{k\ge1}kz^k=\frac z{(1-z)^2}$ at $z=\frac13$: $\sum x_k=\frac{1/3}{4/9}=\frac34$. So $S=\frac12\cdot\frac9{16}=\frac9{32}$.

Key idea: on a finite-dimensional space all norms are comparable; $\int_{-1}^1|p|$ is one norm, and $|p(0)|$ is bounded by another.

Let $V$ be the space of real polynomials of degree at most $1999$, identified with coefficient vectors $(c_0,\dots,c_{1999})\in\mathbb R^{2000}$ with the Euclidean norm $\|c\|$. Let $$N(p)=\int_{-1}^1|p(x)|\,dx .$$

• $N$ is continuous in the coefficients: $|N(p)-N(q)|\le N(p-q)\le2\sum|c_i-d_i|$.
• $N(p)>0$ for $p\ne0$: a nonzero polynomial has finitely many roots, so $|p|>0$ on most of $[-1,1]$.

The unit sphere $\{\|c\|=1\}$ is compact, so $N$ attains a minimum $\mu>0$ on it. By scaling, $N(p)\ge\mu\|c\|$ for every $p$. Finally $|p(0)|=|c_0|\le\|c\|\le\frac1\mu N(p)$. So $C=\frac1\mu$ works.

Key idea: the ratios $a_n/a_{n-1}$ satisfy a linear recurrence, giving a product formula; then the factors $2^j-1$ supply every odd divisor.

Dividing the recurrence by $a_{n-1}$ (all terms turn out positive), the ratios $r_n=\frac{a_n}{a_{n-1}}$ satisfy $$r_n=6r_{n-1}-8r_{n-2},\qquad r_2=2,\ r_3=12 .$$ The roots of $t^2-6t+8$ are $2$ and $4$, and fitting the initial values gives $r_n=2^{n-1}(2^{n-1}-1)$ (check: $r_2=2\cdot1$, $r_3=4\cdot3$). Hence $$a_n=\prod_{j=1}^{n-1}2^j\,(2^j-1),$$ a positive integer.

Divisibility. For $n=1$, $a_1=1$. For $n\ge2$ write $n=2^st$ with $t$ odd.

• The power of $2$ in $a_n$ is at least $1+2+\dots+(n-1)\ge n-1\ge s$ (since $2^s\le n$).
• If $t>1$, let $d$ be the order of $2$ modulo $t$. Then $d\le t-1\le n-1$, and $t\mid2^d-1$, which is one of the factors.

Since $2^s$ and $t$ are coprime and both divide $a_n$, so does $n$.

Key idea: angle chasing gives triangle $CDE$ with angles $\frac\theta2$, $\theta$ and $\pi-\frac{3\theta}2$; the law of sines then gives $EF$ in closed form.

Put $C=(0,0)$, $A=(1,0)$ and $B=(0,\tan\theta)$, so $BC$ is the $y$-axis.

Angles. Triangle $ACD$ has $AC=AD=1$ and apex angle $\theta$, so $\angle ACD=\frac\pi2-\frac\theta2$ and $|CD|=2\sin\frac\theta2$. Hence $\angle DCE=\frac\pi2-\angle ACD=\frac\theta2$. In triangle $CDE$ the angle at $D$ is $\theta$, so the angle at $E$ is $\pi-\frac{3\theta}{2}$.

Law of sines. $$|CE|=\frac{|CD|\sin\theta}{\sin\frac{3\theta}2}=\frac{2\sin\frac\theta2\sin\theta}{\sin\frac{3\theta}2}.$$ The perpendicular. The line through $E$ perpendicular to $BC$ is horizontal at height $|CE|$, and on $AB$ the point at height $y$ has $x=1-\frac{y}{\tan\theta}$. So $$|EF|=1-\frac{|CE|}{\tan\theta}=1-\frac{2\sin\frac\theta2\cos\theta}{\sin\frac{3\theta}{2}}.$$ As $\theta\to0$, $\frac{2\sin(\theta/2)}{\sin(3\theta/2)}\to\frac{2\cdot\frac12}{\frac32}=\frac23$, so $|EF|\to1-\frac23=\frac13$.

Key idea: a repeated root forces $Q$ to be a constant times $(x-r)^2$, and then $P$ must be a single power $(x-r)^n$.

Since $P$ has at least two distinct roots, $n\ge2$ and $P''\ne0$. Comparing leading coefficients, the leading coefficient of $Q$ is $q=\frac1{n(n-1)}$.

Suppose $r$ is a root of multiplicity $m\ge2$. Then $r$ is a root of $P''$ of multiplicity exactly $m-2$. Since $P=QP''$, $Q$ must vanish at $r$ to order $2$, so $Q=q(x-r)^2$. Shift so that $r=0$ and write $P=\sum c_kx^k$. The equation $P=qx^2P''$ says $$c_k=q\,k(k-1)\,c_k\quad\text{for all }k,\qquad\text{i.e.}\qquad c_k\big(n(n-1)-k(k-1)\big)=0 .$$ For $0\le k\le n$, $k(k-1)=n(n-1)$ only when $k=n$. So $c_k=0$ for $k<n$ and $P=c_nx^n$, which has only one distinct root. Contradiction.

So every root is simple, and $P$ has $n$ distinct roots.

Key idea: the cone’s lattice points split into three shifted copies of the lattice generated by $(1,2)$ and $(2,1)$, so $S$ is a rational function with exactly the denominator $(1-xy^2)(1-x^2y)$.

Unique representation. Let $(m,n)$ be a lattice point with $\frac12\le\frac mn\le2$ (or $(0,0)$). Put $u=2n-m\ge0$ and $v=2m-n\ge0$; then $u-v=3(n-m)$, so $u\equiv v\pmod3$. Let $r\in\{0,1,2\}$ be that common residue and $a=\frac{u-r}3$, $b=\frac{v-r}3$, nonnegative integers. Then $$a(1,2)+b(2,1)+r(1,1)=\Big(\frac{u+2v}3,\frac{2u+v}3\Big)=(m,n),$$ and $(a,b,r)$ is determined by $(m,n)$. Conversely every such combination lies in the cone.

The sum. Hence, for $0\le x,y<1$, $$1+S(x,y)=\frac{1+xy+x^2y^2}{(1-xy^2)(1-x^2y)},$$ where the $1$ accounts for $(0,0)$, which $S$ omits. So $$(1-xy^2)(1-x^2y)S(x,y)=1+xy+x^2y^2-(1-xy^2)(1-x^2y)\longrightarrow3-0=3$$ as $(x,y)\to(1,1)$.

Key idea: two “energy” estimates, $f'^2<2ff''$ and $f''^2<2ff'$, multiply to give $f'^3<8f^3$.

Limits at $-\infty$. $f'$ is positive and increasing, so it has a limit $L\ge0$ at $-\infty$. If $L>0$, then $f'\ge L$ everywhere and $f(x)\le f(0)+Lx\to-\infty$ as $x\to-\infty$, contradicting $f>0$. So $f'\to0$. The same argument applied to $f'$ (positive, with $f''$ positive and increasing) gives $f''\to0$. Also $f$ is increasing and positive.

First estimate. Fix $x$ and $a_0<x$. For $a<a_0$, $$f'(x)^2-f'(a)^2=\int_a^x2f'f''\,dt\le2f''(a_0)\big(f(a_0)-f(a)\big)+2f''(x)\big(f(x)-f(a_0)\big),$$ since $f''$ is increasing. Let $a\to-\infty$ (then $f'(a)\to0$ and $f(a)\ge0$): $$f'(x)^2\le2f''(x)f(x)-2f(a_0)\big(f''(x)-f''(a_0)\big)<2f(x)f''(x).$$ Second estimate. In the same way, using $f'''\le f$ and that $f$ is increasing, $$f''(x)^2-f''(a)^2=\int_a^x2f''f'''\,dt\le\int_a^x2f''(t)f(t)\,dt\le2f(a_0)\big(f'(a_0)-f'(a)\big)+2f(x)\big(f'(x)-f'(a_0)\big).$$ Letting $a\to-\infty$: $f''(x)^2\le2f(x)f'(x)-2f'(a_0)\big(f(x)-f(a_0)\big)<2f(x)f'(x)$.

Combine. Squaring the first and using the second, $$f'^4<4f^2f''^2<8f^3f' ,$$ so $f'^3<8f^3$, i.e. $f'(x)<2f(x)$.

Key idea: the matrix has rank at most two, so the $n\times n$ determinant reduces to a $2\times2$ one built from sums of roots of unity.

Let $\omega=e^{i\theta}$ and $u=(\omega,\omega^2,\dots,\omega^n)^T$. Then $\cos(j\theta+k\theta)=\frac12(\omega^{j+k}+\omega^{-j-k})$, so $$A=XY^T,\qquad X=\tfrac12[\,u\ \ \bar u\,],\quad Y=[\,u\ \ \bar u\,].$$ By the identity $\det(I_n+XY^T)=\det(I_2+Y^TX)$, we need the $2\times2$ matrix $Y^TX=\frac12\begin{pmatrix}u^Tu&u^T\bar u\\\bar u^Tu&\bar u^T\bar u\end{pmatrix}$ (plain transposes, no conjugation):

• $u^Tu=\sum_{j=1}^n\omega^{2j}=0$, because $\omega^2\ne1$ (as $n\ge3$) and $\omega^{2n}=1$;
• likewise $\bar u^T\bar u=0$;
• $u^T\bar u=\bar u^Tu=\sum_j1=n$.

So $\det(I+A)=\det\begin{pmatrix}1&\frac n2\\\frac n2&1\end{pmatrix}=1-\frac{n^2}4$.

Key idea: take the smallest $n$ that meets every element of $S$; dividing it by one prime breaks this, and the element that becomes coprime meets $s$ in exactly that prime.

The product of all elements of $S$ shares a factor with each of them, so there is a smallest positive integer $n$ with $\gcd(s,n)>1$ for all $s\in S$.

By hypothesis some $s\in S$ has $\gcd(s,n)\in\{1,s\}$; it is not $1$, so $s\mid n$. Let $p$ be a prime factor of $s$; then $p\mid n$. By minimality, $n/p$ fails: some $t\in S$ has $\gcd(t,n/p)=1$.

• $\gcd(t,n)>1$, but $t$ shares no prime with $n/p$. So the only prime in $\gcd(t,n)$ is $p$, and $p^2\nmid\gcd(t,n)$ (otherwise $p\mid n/p$ and $p\mid t$). Hence $\gcd(t,n)=p$.
• $p$ divides both $s$ and $t$, and $\gcd(s,t)$ divides $\gcd(n,t)=p$ because $s\mid n$.

So $\gcd(s,t)=p$ is prime. (If $s=t$, this says $s=p$ is itself prime, and $\gcd(s,s)=p$.)