\documentclass[amssymb,twocolumn,pra,10pt,aps]{revtex4-1}
\usepackage{mathptmx,amsmath,amsthm}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}[lemma]{Corollary}
\newtheorem*{lemma*}{Lemma}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\Trace}{Trace}
\begin{document}
\title{Solutions to the 74th William Lowell Putnam Mathematical Competition \\
Saturday, December 7, 2013}
\author{Kiran Kedlaya and Lenny Ng}
\noaffiliation
\maketitle
\begin{itemize}
\item[A1]
Suppose otherwise. Then each vertex $v$ is a vertex for five faces, all of which have different labels, and so the sum of the labels of the five faces incident to $v$ is at least $0+1+2+3+4 = 10$. Adding this sum over all vertices $v$ gives $3 \times 39 = 117$, since each face's label is counted three times. Since there are $12$ vertices, we conclude that $10 \times 12 \leq 117$, contradiction.
\noindent
\textbf{Remark:}
One can also obtain the desired result by showing that any collection of five faces must contain two faces that share a vertex; it then follows that each label can appear at most $4$ times, and so the sum of all labels is at least $4(0+1+2+3+4) = 40 > 39$, contradiction.
\item[A2]
Suppose to the contrary that $f(n) = f(m)$ with $n 0$ for $0 < y < 1$. For the given value of $x$, we then have
\[
a_0 x^m + a_1 x^{2m} + \cdots + a_n x^{(n+1)m} \geq 0
\]
for $m=0,1,\dots$, with strict inequality for $m>0$.
Taking the sum over all $m$ is absolutely convergent and hence valid; this yields
\[
\frac{a_0}{1-x} + \frac{a_1}{1-x^2} + \cdots + \frac{a_n}{1-x^{n+1}} > 0,
\]
a contradiction.
\item[A4]
Let $w_1',\ldots,w_k'$ be arcs such that: $w_j'$ has the same length as $w_j$; $w_1'$ is the same as $w_1$; and $w_{j+1}'$ is adjacent to $w_j'$ (i.e., the last digit of $w_j'$ comes right before the first digit of $w_{j+1}'$). Since $w_j$ has length $Z(w_j)+N(w_j)$, the sum of the lengths of $w_1,\ldots,w_k$ is $k(Z+N)$, and so the concatenation of $w_1',\ldots,w_k'$ is a string of $k(Z+N)$ consecutive digits around the circle. (This string may wrap around the circle, in which case some of these digits may appear more than once in the string.) Break this string into $k$ arcs $w_1'',\ldots,w_k''$ each of length $Z+N$, each adjacent to the previous one. (Note that if the number of digits around the circle is $m$, then $Z+N \leq m$ since $Z(w_j)+N(w_j) \leq m$ for all $j$, and thus each of $w_1'',\ldots,w_k''$ is indeed an arc.)
We claim that for some $j=1,\ldots,k$, $Z(w_j'')=Z$ and $N(w_j'')=N$ (where the second equation follows from the first since $Z(w_j'')+N(w_j'')=Z+N$). Otherwise, since all of the $Z(w_j'')$ differ by at most $1$, either $Z(w_j'') \leq Z-1$ for all $j$ or $Z(w_j'') \geq Z+1$ for all $j$. In either case,
$|kZ - \sum_j Z(w_j')| = |kZ-\sum_j Z(w_j'')| \geq k$. But since $w_1=w_1'$, we have
$|kZ - \sum_j Z(w_j')| = |\sum_{j=1}^k (Z(w_j)-Z(w_j'))| = |\sum_{j=2}^k (Z(w_j)-Z(w_j'))| \leq \sum_{j=2}^k |Z(w_j)-Z(w_j')| \leq k-1$, contradiction.
\item[A5]
Let $A_1,\ldots,A_m$ be points in $\mathbb{R}^3$, and let $\hat{n}_{ijk}$ denote a unit vector normal to $\Delta A_iA_jA_k$ (unless $A_i,A_j,A_k$ are collinear, there are two possible choices for $\hat{n}_{ijk}$). If $\hat{n}$ is a unit vector in $\mathbb{R}^3$, and $\Pi_{\hat{n}}$ is a plane perpendicular to $\hat{n}$, then the area of the orthogonal projection of $\Delta A_iA_jA_k$ onto $\Pi_{\hat{n}}$ is $\text{Area}(\Delta A_iA_jA_k) |\hat{n}_{ijk} \cdot \hat{n}|$. Thus if $\{a_{ijk}\}$ is area definite for $\mathbb{R}^2$, then for any $\hat{n}$,
\[
\sum a_{ijk} \text{Area}(\Delta A_iA_jA_k) |\hat{n}_{ijk} \cdot \hat{n}| \geq 0.
\]
Note that integrating $|\hat{n}_{ijk} \cdot \hat{n}|$ over $\hat{n} \in S^2$, the unit sphere in $\mathbb{R}^3$, with respect to the natural measure on $S^2$ gives a positive number $c$, which is independent of $\hat{n}_{ijk}$ since the measure on $S^2$ is rotation-independent. Thus integrating the above inequality over $\hat{n}$ gives
$c \sum a_{ijk} \text{Area}(\Delta A_iA_jA_k) \geq 0$. It follows that $\{a_{ijk}\}$ is area definite for $\mathbb{R}^3$, as desired.
\noindent
\textbf{Remark:}
It is not hard to check (e.g., by integration in spherical coordinates) that the constant $c$ occurring above is equal to $2\pi$. It follows that for any convex body $C$ in $\mathbb{R}^3$, the average over $\hat{n}$ of the area of the projection of $C$ onto $\Pi_{\hat{n}}$ equals $1/4$ of the surface area of $C$.
More generally, let $C$ be a convex body in $\mathbb{R}^n$.
For $\hat{n}$ a unit vector, let $\Pi_{\hat{n}}$ denote the hyperplane through the origin perpendicular to $\hat{n}$. Then the average over $\hat{n}$ of the volume of the projection of $C$ onto $\Pi_{\hat{n}}$ equals a constant (depending only on $n$) times the $(n-1)$-dimensional surface area of $C$.
Statements of this form inhabit the field of \emph{inverse problems}, in which one attempts to reconstruct information about a geometric object from low-dimensional samples. This field has important applications in imaging and tomography.
\item[A6]
(by Harm Derksen)
Consider the generating functions
\begin{align*}
f(x,y) &= \sum_{(a,b) \in S} x^a y^b, \\
g(x,y) &= \sum_{(a,b) \in \mathbb{Z}^2} w(a,b) x^a y^b.
\end{align*}
Then $A(S)$ is the constant coefficient of the Laurent polynomial
$h(x,y) = f(x,y) f(x^{-1}, y^{-1}) g(x,y)$. We may compute this coefficient by averaging over unit circles:
\begin{align*}
(2 \pi)^2 A(S) &= \int_0^{2\pi} \int_0^{2\pi} h(e^{is}, e^{it})\,dt\,ds \\
&= \int_0^{2\pi} \int_0^{2\pi} \left| f(e^{is}, e^{it}) \right|^2 g(e^{is}, e^{it}) \,dt\,ds.
\end{align*}
Consequently, it is enough to check that $g(e^{is}, e^{it})$ is a nonnegative real number for all $s,t \in \mathbb{R}$. But
$g(e^{is}, e^{it}) = 16 G(\cos s,\cos t)$ for
\[
G(z,w) = zw + z^2 + w^2 - z^2 w - zw^2 - z^2w^2.
\]
If $z,w \in [-1,1]$ and $zw \geq 0$, then
\[
G(z,w) = zw(1-zw) + z^2(1-w) + w^2(1-z) \geq 0.
\]
If $z,w \in [-1,1]$ and $zw \leq 0$, then
\[
G(z,w) = (z+w)^2 - zw(1+z)(1+w) \geq 0.
\]
Hence $g(e^{is},e^{it}) \geq 0$ as desired.
\item[B1]
Note that
\begin{align*}
c(2k+1)c(2k+3) &= (-1)^k c(k) (-1)^{k+1} c(k+1) \\
&= -c(k)c(k+1) \\
&= -c(2k)c(2k+2).
\end{align*}
It follows that $\sum_{n=2}^{2013} c(n)c(n+2) = \sum_{k=1}^{1006} (c(2k)c(2k+2)+c(2k+1)c(2k+3)) = 0$,
and so the desired sum is $c(1)c(3) = -1$.
\textbf{Remark}: Karl Mahlburg points out the general formula
$c(n) = (-1)^{b_0 b_1 + b_1 b_2 + \dots + b_{k-1} b_k}$
for $n$ having binary representation $b_k \cdots b_0$.
\item[B2]
We claim that the maximum value of $f(0)$ is $3$. This is attained for
$N=2$, $a_1=\frac{4}{3}$, $a_2=\frac{2}{3}$: in this case $f(x) = 1+\frac{4}{3} \cos(2\pi x)+\frac{2}{3} \cos(4\pi x) =
1+\frac{4}{3} \cos(2\pi x)+\frac{2}{3}(2\cos^2(2\pi x)-1) = \frac{1}{3} (2\cos(2\pi x)+1)^2$ is always nonnegative.
Now suppose that $f = 1 + \sum_{n=1}^N a_n \cos(2\pi nx) \in C$. When $n$ is an integer, $\cos(2\pi n/3)$ equals $0$ if $3|n$ and $-1/2$ otherwise. Thus $a_n \cos(2\pi n/3) = -a_n/2$ for all $n$, and
$f(1/3) = 1-\sum_{n=1}^N (a_n/2)$. Since $f(1/3) \geq 0$, $\sum_{n=1}^N a_n \leq 2$, whence $f(0) = 1 + \sum_{n=1}^N a_n \leq 3$.
\item[B3]
Yes, such numbers must exist. To define them, we make the following observations.
\setcounter{lemma}{0}
\begin{lemma}
For any $i \in \{1,\dots,n\}$, if there exists any $S \in P$ containing $i$, then there exist $S,T \in P$ such that $S$ is the disjoint union of $T$ with $\{i\}$.
\end{lemma}
\begin{proof}
Let $S$ be an element of $P$ containing $i$ of minimum cardinality.
By (ii), there must be a subset $T \subset S$ containing $P$ with exactly one fewer element than $S$. These sets have the desired form.
\end{proof}
\begin{lemma}
Suppose $S_1, S_2, T_1, T_2 \in P$ have the property that for some $i \in \{1,\dots,n\}$, $S_1$ is the disjoint union of $T_1$ with $\{i\}$ and $S_2$ is the disjoint union of $T_2$ with $\{i\}$. Then
\[
f(S_1) - f(T_1) = f(S_2) - f(T_2).
\]
\end{lemma}
\begin{proof}
By (i) we have
\begin{align*}
f(T_1 \cup T_2 \cup \{i\}) &= f(S_1) + f(T_2) - f(T_1 \cap T_2) \\
f(T_1 \cup T_2 \cup \{i\}) &= f(T_1) + f(S_2) - f(T_1 \cap T_2),
\end{align*}
from which the claim follows immediately.
\end{proof}
We now define $f_1,\dots,f_n$ as follows. If $i$ does not appear in any element of $P$, we put $f_i = 0$. Otherwise, by Lemma~1, we can find
$S, T \in P$ such that $S$ is the disjoint union of $T$ with $\{i\}$. We then set $f_i = f(S) - f(T)$; by Lemma~2, this does not depend on the choice of $S,T$.
To check that $f(S) = \sum_{i \in S} f_i$ for $S \in P$, note first that $\emptyset \in P$ by repeated application of (ii) and that $f(\emptyset) = 0$ by hypothesis. This provides the base case for an induction on the cardinality of $S$; for any nonempty $S \in P$, we may apply (ii) to find $T \subset S$ such that $S$ is the disjoint union of $T$ and some singleton set $\{j\}$. By construction and the induction hypothesis, we have $f(S) = f(T) + f_j = j + \sum_{i \in T} f_i = \sum_{i \in S} f_i$ as desired.
\item[B4]
\newcommand{\Var}{\mathrm{Var}}
Write $f_0(x) = f(x)-\mu(f)$ and $g_0(x) = g(x)-\mu(g)$, so that $\int_0^1 f_0(x)^2\,dx = \Var(f)$, $\int_0^1 g_0(x)^2\,dx = \Var(g)$, and $\int_0^1 f_0(x)\,dx = \int_0^1 g_0(x)\,dx = 0$. Now since $|g(x)| \leq M(g)$ for all $x$, $0\leq \int_0^1 f_0(x)^2(M(g)^2-g(x)^2)\,dx = \Var(f) M(g)^2-\int_0^1 f_0(x)^2g(x)^2\,dx$, and similarly $0 \leq \Var(g)M(f)^2-\int_0^1 f(x)^2g_0(x)^2\,dx$. Summing gives
\begin{equation}
\Var(f)M(g)^2+\Var(g)M(f)^2
\label{eq:1}
\geq \int_0^1 (f_0(x)^2g(x)^2+f(x)^2g_0(x)^2)\,dx.
\end{equation}
Now
\begin{align*}
&\int_0^1 (f_0(x)^2g(x)^2+f(x)^2g_0(x)^2)\,dx-\Var(fg) \\&= \int_0^1 (f_0(x)^2g(x)^2+f(x)^2g_0(x)^2-(f(x)g(x)-\int_0^1 f(y)g(y)\,dy)^2)\,dx;
\end{align*}
substituting $f_0(x)+\mu(f)$ for $f(x)$ everywhere and $g_0(x)+\mu(g)$ for $g(x)$ everywhere, and using the fact that $\int_0^1 f_0(x)\,dx = \int_0^1 g_0(x)\,dx = 0$, we can expand and simplify the right hand side of this equation to obtain
\begin{align*}
&\int_0^1 (f_0(x)^2g(x)^2+f(x)^2g_0(x)^2)\,dx-\Var(fg) \\
&= \int_0^1 f_0(x)^2g_0(x)^2\,dx \\
&-2\mu(f)\mu(g)\int_0^1 f_0(x)g_0(x)\,dx +(\int_0^1 f_0(x)g_0(x)\,dx)^2 \\
&\geq -2\mu(f)\mu(g)\int_0^1 f_0(x)g_0(x)\,dx.
\end{align*}
Because of \eqref{eq:1}, it thus suffices to show that
\begin{equation}
2\mu(f)\mu(g)\int_0^1 f_0(x)g_0(x)\,dx
\label{eq:3} \leq \Var(f)M(g)^2+\Var(g)M(f)^2.
\end{equation}
Now since $(\mu(g) f_0(x)-\mu(f) g_0(x))^2 \geq 0$ for all $x$, we have
\begin{align*}
2\mu(f)\mu(g) \int_0^1 f_0(x)g_0(x)\,dx
& \leq \int_0^1 (\mu(g)^2 f_0(x)^2 + \mu(f)^2 g_0(x)^2) dx \\
& = \Var(f) \mu(g)^2 + \Var(g) \mu(f)^2 \\
& \leq \Var(f) M(g)^2 + \Var(g) M(f)^2,
\end{align*}
establishing \eqref{eq:3} and completing the proof.
\item[B5]
\setcounter{lemma}{0}
\textbf{First solution:}
We assume $n \geq 1$ unless otherwise specified.
For $T$ a set and $S_1, S_2$ two subsets of $T$, we say that a function $f: T \to T$ \emph{iterates $S_1$ into $S_2$} if for each $x \in S_1$, there is a $j \geq 0$ such that $f^{(j)}(x) \in S_2$.
\begin{lemma}
Fix $k \in X$. Let $f,g: X \to X$ be two functions such that $f$ iterates $X$ into $\{1,\dots,k\}$ and $f(x) = g(x)$ for $x \in \{k+1,\dots,n\}$. Then $g$ also iterates $X$ into $\{1,\dots,k\}$.
\end{lemma}
\begin{proof}
For $x \in X$, by hypothesis there exists a nonnegative integer $j$ such that $f^{(j)}(x) \in \{1,\dots,k\}$. Choose the integer $j$ as small as possible; then $f^{(i)}(x) \in \{k+1,\dots,n\}$ for $0 \leq i \cdots > a_{k-1}$
(or $a_0(x) > \cdots > a_{k-1}(x)$ if this needs to be clarified),
define
\begin{align*}
A(x) &= a_0 + \cdots + a_{k-1} \\
f(x,t) &= A - a_t - t(n+1) \quad (t=0,\dots,k-1);
\end{align*}
note that $f(x,0) > \cdots > f(x,k-1)$. We say that $x$ is \emph{balanced} if $f(x,t) = 0$ for some (necessarily unique) choice of $t$, in which case we refer to $a_t$ as the \emph{balance point} of $x$; otherwise, we say that
$x$ is \emph{unbalanced}.
This definition then has the following properties.
\begin{itemize}
\item
The property of being balanced is invariant under left-right symmetry. This will permit some simplification in the following arguments.
\item
Every position in $P_{n-2}$ is unbalanced, because $a_0 < a_0 + a_1 < a_1 + (n+1)$.
\item
For a position $x \in P_1$ to be balanced,
in order to have $f(x,t) \equiv 0 \pmod{n+1}$ for some $t$,
the unique occupied space must be $n+1-t$. We must then have
$A(x) - t = 1 + \cdots + n - (n+1) = (n/2 -1)(n+1)$,
so $x$ is balanced if and only if $f(x, n/2 - 1) = 0$.
This occurs if and only if the occupied space is $n/2$ or $n/2 + 1$.
\item
From every balanced position $x \in P_{n-k}$ for $k \geq 3$, every move leads to an unbalanced position.
To check this, we need only consider moves at or to the left of the balance point $a_t$ of $x$.
Let $y$ be the result of a move from $x$. If the move is at $a_t$,
then
\[
f(y,t') \equiv f(x,t) - a_{t'}(y) = -a_{t'}(y) \pmod{n+1}
\]
and the latter is not a nonzero residue because $a_{t'} \in \{1,\dots,n\}$.
For a move to the left of $a_t$, the vacant spaces to the right of $a_t$ remain at $a_0,\dots,a_{t-1}$
and $0 < A(x) - A(y) < a_t$; consequently,
\begin{align*}
f(y,t-1) &= f(x,t-1) - (A(x)-A(y)) \\
&\geq (f(x,t) + a_t - a_{t-1} + (n+1)) - (a_t - 1) \\
&= n+2 - a_{t-1} > 0.
\end{align*}
Meanwhile, either $a_t$ remains vacant, or $a_{t}$ and $a_{t+1}$ are filled while some space $b$ in between becomes vacant; in either case, we have $f(y,t)