\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{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\Trace}{Trace}
\newcommand{\ee}{\ell}
\begin{document}
\title{Solutions to the 77th William Lowell Putnam Mathematical Competition \\
Saturday, December 3, 2016}
\author{Kiran Kedlaya and Lenny Ng}
\noaffiliation
\maketitle
\begin{itemize}
\item[A1]
The answer is $j=8$. First suppose that $j$ satisfies the given condition. For $p(x) = x^j$, we have $p^{(j)}(x) = j!$ and thus $j!$ is divisible by $2016$. Since $2016$ is divisible by $2^5$ and $7!$ is not, it follows that $j \geq 8$. Conversely, we claim that $j=8$ works. Indeed, let $p(x) = \sum_{m=0}^n a_m x^m$ be a polynomial with integer coefficients; then if $k$ is any integer,
\begin{align*}
p^{(8)}(k) &= \sum_{m=8}^n m(m-1)\cdots (m-7) a_m k^{m-8} \\
&= \sum_{m=8}^n {m\choose 8} 8! a_m k^{m-8}
\end{align*}
is divisible by $8! = 20 \cdot 2016$, and so $p^{(8)}(k)$ is divisible by $2016$.
\noindent
\textbf{Remark:}
By the same reasoning, if one replaces $2016$ in the problem by a general integer $N$,
then the minimum value of $j$ is the smallest one for which $N$ divides $j!$.
This can be deduced from P\'olya's observation that the set of integer-valued polynomials is the free $\ZZ$-module generated by the binomial polynomials $\binom{x}{n}$ for $n=0,1,\dots$. That statement can be extended to polynomials evaluated on a subset of a Dedekind domain using Bhargava's method of \emph{$P$-orderings}; we do not know if this generalization can be adapted to the analogue of this problem, where one considers polynomials whose $j$-th derivatives take integral values on a prescribed subset.
\item[A2]
The answer is $\frac{3+\sqrt{5}}{2}$. Note that for $m > n+1$, both binomial coefficients are nonzero and their ratio is
\begin{align*}
{m\choose n-1}/{m-1\choose n} &= \frac{m!n!(m-n-1)!}{(m-1)!(n-1)!(m-n+1)!} \\
&= \frac{mn}{(m-n+1)(m-n)}.
\end{align*}
Thus the condition ${m\choose{n-1}} > {{m-1}\choose n}$ is equivalent to $(m-n+1)(m-n)-mn < 0$. The left hand side of this last inequality is a quadratic function of $m$ with roots
\begin{align*}
\alpha(n) &= \frac{3n-1+\sqrt{5n^2-2n+1}}{2}, \\
\beta(n) &= \frac{3n-1-\sqrt{5n^2-2n+1}}{2},
\end{align*}
both of which are real since $5n^2-2n+1 = 4n^2+(n-1)^2 > 0$; it follows that $m$ satisfies the given inequality if and only if $\beta(n) < m < \alpha(n)$. (Note in particular that since $\alpha(n)-\beta(n) = \sqrt{5n^2-2n+1} > 1$, there is always some integer $m$ between $\beta(n)$ and $\alpha(n)$.)
We conclude that $M(n)$ is the greatest integer strictly less than $\alpha(n)$, and thus that
$\alpha(n)-1 \leq M(n) < \alpha(n)$. Now
\[
\lim_{n\to\infty} \frac{\alpha(n)}{n} = \lim_{n\to\infty} \frac{3-\frac{1}{n}+\sqrt{5-\frac{2}{n}+\frac{1}{n^2}}}{2}
= \frac{3+\sqrt{5}}{2}
\]
and similarly $\lim_{n\to\infty} \frac{\alpha(n)-1}{n} = \frac{3+\sqrt{5}}{2}$, and so by the sandwich theorem, $\lim_{n\to\infty} \frac{M(n)}{n} = \frac{3+\sqrt{5}}{2}$.
\item[A3]
The given functional equation, along with the same equation but with $x$ replaced by $\frac{x-1}{x}$ and $\frac{1}{1-x}$ respectively, yields:
\begin{align*}
f(x) + f\left(1-\frac{1}{x}\right) &= \tan^{-1}(x) \\
f\left(\frac{x-1}{x}\right) + f\left(\frac{1}{1-x}\right) &= \tan^{-1}\left(\frac{x-1}{x}\right) \\
f\left(\frac{1}{1-x}\right) + f(x) &= \tan^{-1}\left(\frac{1}{1-x}\right).
\end{align*}
Adding the first and third equations and subtracting the second gives:
\[
2f(x) = \tan^{-1}(x) + \tan^{-1}\left(\frac{1}{1-x}\right) - \tan^{-1}\left(\frac{x-1}{x}\right).
\]
Now $\tan^{-1}(t) + \tan^{-1}(1/t)$ is equal to $\pi/2$ if $t>0$ and $-\pi/2$ if $t<0$; it follows that for $x \in (0,1)$,
\begin{align*}
2(f(x)+f(1-x)) &= \left(\tan^{-1}(x)+\tan^{-1}(1/x)\right)\\
&\,\, + \left(\tan^{-1}(1-x)+\tan^{-1}\left(\frac{1}{1-x}\right)\right) \\
&\,\,-
\left(\tan^{-1}\left(\frac{x-1}{x}\right) + \tan^{-1}\left(\frac{x}{x-1}\right) \right) \\
&= \frac{\pi}{2} + \frac{\pi}{2} + \frac{\pi}{2} \\
&= \frac{3\pi}{2}.
\end{align*}
Thus
\[
4\int_0^1 f(x)\,dx = 2\int_0^1 (f(x)+f(1-x))dx = \frac{3\pi}{2}
\]
and finally $\int_0^1 f(x)\,dx = \frac{3\pi}{8}$.
\noindent
\textbf{Remark:}
Once one has the formula for $f(x)$, one can also (with some effort) directly evaluate the integral of each summand over $[0,1]$ to obtain the same result. A much cleaner variant of this approach (suggested on AoPS, user \texttt{henrikjb}) is to write
\[
\tan^{-1}(x) = \int_0^y \frac{1}{1+y^2}\,dy
\]
and do a change of variable on the resulting double integral.
\item[A4]
The minimum number of tiles is $mn$. To see that this many are required, label the squares $(i,j)$ with $1\leq i\leq 2m-1$ and $1\leq j\leq 2n-1$, and for each square with $i,j$ both odd, color the square red; then no tile can cover more than one red square, and there are $mn$ red squares.
It remains to show that we can cover any $(2m-1) \times (2n-1)$ rectangle with $mn$ tiles when $m,n \geq 4$. First note that we can tile any $2 \times (2k-1)$ rectangle with $k\geq 3$ by $k$ tiles: one of the first type, then $k-2$ of the second type, and finally one of the first type. Thus if we can cover a $7\times 7$ square with $16$ tiles, then we can do the general $(2m-1) \times (2n-1)$ rectangle, by decomposing this rectangle into a $7\times 7$ square in the lower left corner, along with $m-4$ $(2\times 7)$ rectangles to the right of the square, and $n-4$ $((2m-1)\times 2)$ rectangles above, and tiling each of these rectangles separately, for a total of $16+4(m-4)+m(n-4) = mn$ tiles.
To cover the $7 \times 7$ square, note that the tiling must consist of 15 tiles of the first type and 1 of the second type, and that any $2 \times 3$ rectangle can be covered using 2 tiles of the first type. We may thus construct a suitable covering by covering all but the center square with eight $2 \times 3$ rectangles, in such a way that we can attach the center square to one of these rectangles to get a shape that can be covered by two tiles. An example of such a covering, with the remaining $2 \times 3$ rectangles left intact for visual clarity, is depicted below. (Many other solutions are possible.)
\[
\setlength{\unitlength}{4144sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\begin{picture}(3174,3174)(1339,-7723)
\thinlines
{\put(1351,-7711){\framebox(3150,3150){}}
}%
{\put(1351,-5911){\line( 1, 0){945}}
\put(2296,-5911){\line( 0, 1){1350}}
}%
{\put(2296,-5911){\line( 1, 0){405}}
\put(2701,-5911){\line( 0,-1){1800}}
}%
{\put(1351,-6811){\line( 1, 0){1350}}
}%
{\put(2701,-6361){\line( 1, 0){1800}}
}%
{\put(3601,-6361){\line( 0,-1){1350}}
}%
{\put(3151,-6361){\line( 0, 1){1800}}
}%
{\put(3151,-5461){\line( 1, 0){1350}}
}%
{\multiput(2296,-5011)(128.57143,0.00000){4}{\line( 1, 0){ 64.286}}
\multiput(2746,-5011)(0.00000,-128.57143){4}{\line( 0,-1){ 64.286}}
\multiput(2746,-5461)(115.71429,0.00000){4}{\line( 1, 0){ 57.857}}
}%
\end{picture}%
\]
\item[A5]
\noindent
\textbf{First solution:}
For $s \in G$ and $r$ a positive integer, define a \emph{representation of $s$ of length $r$}
to be a sequence of values $m_1, n_1, \ldots, m_r, n_r \in \{-1, 1\}$ for which
\[
s = g^{m_1} h^{n_1} \cdots g^{m_r} h^{n_r}.
\]
We first check that every $s \in G$ admits at least one representation of some length; this is equivalent to saying that the set $S$ of $s \in G$ which admit representations of some length
is equal to $G$ itself.
Since $S$ is closed under the group operation and $G$ is finite, $S$ is also closed under formation of inverses and contains the identity element; that is, $S$ is a subgroup of $G$.
In particular, $S$ contains not only $gh$ but also its inverse $h^{-1} g^{-1}$; since $S$ also contains $g^{-1} h$, we deduce that $S$ contains $g^{-2}$.
Since $g$ is of odd order in $G$, $g^{-2}$ is also a generator of the cyclic subgroup containing $g$; it follows that $g \in S$ and hence $h \in S$. Since we assumed that $g,h$ generate $G$,
we now conclude that $S = G$, as claimed.
To complete the proof, we must now check that for each $s \in G$, the smallest possible length of a representation of $s$ cannot exceed $|G|$. Suppose the contrary, and let
\[
s = g^{m_1} h^{n_1} \cdots g^{m_r} h^{n_r}
\]
be a representation of the smallest possible length. Set
\[
s_i = g^{m_1} h^{n_1} \cdots g^{m_i} h^{n_i} \qquad (i=0,\dots,r-1),
\]
interpreting $s_0$ as $e$; since $r>|G|$ by hypothesis, by the pigeonhole principle there must exist indices $0 \leq i < j \leq r-1$ such that $s_i = s_j$. Then
\[
s = g^{m_1} h^{n_1} \cdots g^{m_i} h^{n_i} g^{m_{j+1}} h^{n_{j+1}} \cdots g^{m_r} h^{n_r}
\]
is another representation of $s$ of length strictly less than $r$, a contradiction.
\noindent
\textbf{Remark:}
If one considers $s_1,\dots,s_r$ instead of $s_0,\dots,s_{r-1}$, then the case $s=e$ must be handled separately: otherwise, one might end up with a representation of length 0 which is disallowed by the problem statement.
\noindent
\textbf{Reinterpretation:}
Note that the elements $gh, gh^{-1}, g^{-1} h, g^{-1} h^{-1}$ generate $gh(g^{-1}h)^{-1} = g^2$ and hence all of $G$ (again using the hypothesis that $g$ has odd order, as above). Form the Cayley digraph on the set $G$, i.e., the directed graph with an edge from $s_1$ to $s_2$ whenever $s_2 = s_1 *$ for $* \in \{gh, gh^{-1}, g^{-1} h, g^{-1} h^{-1}\}$. Since $G$ is finite, this digraph is strongly connected: there exists at least one path from any vertex to any other vertex (traveling all edges in the correct direction). The shortest such path cannot repeat any vertices (except the starting and ending vertices in case they coincide), and so has length at most $|G|$.
\noindent
\textbf{Second solution:}
For $r$ a positive integer, let $S_r$ be the set of $s \in G$ which admit a representation of length at most $r$ (terminology as in the first solution); obviously $S_r \subseteq S_{r+1}$.
We will show that $S_r \neq S_{r+1}$ unless $S_r = G$; this will imply by induction on $r$ that $\#S_r \geq \min\{r, |G|\}$ and hence that $S_r = G$ for some $r \leq |G|$.
Suppose that $S_r = S_{r+1}$.
Then the map $s \mapsto sgh$ defines an injective map $S_r \to S_{r+1} = S_r$,
so $S_r$ is closed under right multiplication by $gh$. By the same token, $S_r$ is closed under right multiplication by each of $gh^{-1}, g^{-1}h, g^{-1}h^{-1}$.
Since $gh, gh^{-1}, g^{-1}h, g^{-1}h^{-1}$ generate $G$ as in the first solution, it follows that $S_r = G$ as claimed.since $r+1 \leq |G|$, we are done in this case also.
\noindent
\textbf{Remark:} The condition on the order of $g$ is needed to rule out the case where $G$ admits a (necessarily normal) subgroup $H$ of index 2 not containing either $g$ or $h$; in this case, all products of the indicated form belong to $H$.
On the other hand, if one assumes that both $g$ and $h$ have odd order, then one can say a bit more: there exists some positive integer $r$ with $1 \leq r \leq |G|$ such that every element of $G$ has a representation of length exactly $r$. (Namely, the set of such elements for a given $r$ strictly increases in size until it is stable under right multiplication by both
$gh(g^{-1}h)^{-1} = g^2$ and $gh(gh^{-1})^{-1} = gh^2g^{-1}$, but under the present hypotheses these generate $G$.)
\item[A6]
We prove that the smallest such value of $C$ is $5/6$.
\noindent
\textbf{First solution:}
(based on a suggestion of Daniel Kane)
We first reduce to the case where $P$ is nonnegative in $[0,1]$ and $P(0) = 0$.
To achieve this reduction, suppose that a given value $C$ obeys the inequality for such $P$.
For $P$ general,
divide the interval $[0,1]$ into subintervals $I_1,\dots,I_k$ at the roots of $P$.
Write $\ell(I_i)$ for the length of the interval $I_i$; since each interval is bounded by a root of $P$, we may make a linear change of variable to see that
\[
\int_{I_i} |P(x)|\,dx \leq C \ell(I_i) \max_{x \in I_i} |P(x)| \quad (i=1,\dots,k).
\]
Summing over $i$ yields the desired inequality.
Suppose now that $P$ takes nonnegative values on $[0,1]$, $P(0) = 0$, and $\max_{x \in [0,1]} P(x) = 1$. Write $P(x) = ax^3 + bx^2 + cx$ for some $a,b,c \in \RR$; then
\begin{align*}
\int_0^1 P(x)\,dx &= \frac{1}{4} a + \frac{1}{3} b + \frac{1}{2} c \\
&= \frac{2}{3} \left( \frac{1}{8} a + \frac{1}{4} b + \frac{1}{2} c \right)
+ \frac{1}{6} (a+b+c) \\
&= \frac{2}{3} P\left( \frac{1}{2} \right) + \frac{1}{6} P(1) \\
&\leq \frac{2}{3} + \frac{1}{6} = \frac{5}{6}.
\end{align*}
Consequently, the originally claimed inequality holds with $C = 5/6$. To prove that this value is best possible, it suffices to exhibit a polynomial $P$ as above with $\int_0^1 P(x)\,dx = 5/6$; we will verify that
\[
P(x) = 4x^3 - 8x^2 + 5x
\]
has this property. It is apparent that $\int_0^1 P(x)\, dx =5/6$.
Since $P'(x) = (2x-1)(6x-5)$ and
\[
P(0) = 0, \,P\left( \frac{1}{2} \right) = 1, \,
P\left( \frac{5}{6} \right) = \frac{25}{27}, P(1) = 1,
\]
it follows that $P$ increases from 0 at $x=0$ to 1 at $x=1/2$, then decreases to a positive value at $x=5/6$, then increases to 1 at $x=1$. Hence $P$ has the desired form.
\noindent
\textbf{Remark:}
Here is some conceptual motivation for the preceding solution.
Let $V$ be the set of polynomials of degree at most 3 vanishing at 0, viewed as a three-dimensional vector space over $\RR$.
Let $S$ be the subset of $V$ consisting of those polynomials $P(x)$ for which
$0 \leq P(x) \leq 1$ for all $x \in [0,1]$; this set is convex and compact. We may then compute the minimal $C$ as the maximum value of $\int_0^1 P(x)\,dx$ over all $P \in S$, provided that the maximum is achieved for some polynomial of degree exactly 3. (Note that any extremal polynomial must satisfy
$\max_{x \in [0,1]} P(x) = 1$, as otherwise we could multiply it by some constant $c>1$ so as to increase $\int_0^1 P(x)\,dx$.)
Let $f: V \to \RR$ be the function taking $P(x)$ to $\int_0^1 P(x)\,dx$. This function is linear, so we can characterize its extrema on $S$ easily: there exist exactly two level surfaces for $f$ which are supporting planes for $S$, and the intersections of these two planes
with $S$ are the minima and the maxima. It is obvious that the unique minimum is achieved by the zero polynomial, so this accounts for one of the planes.
It thus suffices to exhibit a single polynomial $P(x) \in S$ such that the level plane of $f$ through $P$ is a supporting plane for $S$.
The calculation made in the solution amounts to verifying that
\[
P(x) = 4x^3 - 8x^2 + 5x
\]
has this property, by interpolating between the constraints $P(1/2) \leq 1$ and $P(1) \leq 1$.
This still leaves the matter of correctly guessing the optimal polynomial. If one supposes that it should be extremized both at $x=1$ and at an interval value of the disc, it is forced to have the form $P(x) = 1 + (x-1)(cx-1)^2$ for some $c>0$; the interpolation property then pins down $c$ uniquely.
\noindent
\textbf{Second solution:}
(by James Merryfield, via AoPS)
As in the first solution, we may assume that $P$ is nonnegative on $[0,1]$ and $P(0)= 0$.
Since $P$ has degree at most 3, Simpson's rule for approximating $\int_0^1 P(x)\,dx$ is an exact formula:
\[
\int_0^1 P(x)\,dx = \frac{1}{6}( P(0) + 4 P\left( \frac{1}{2} \right) + P(1)).
\]
This immediately yields the claimed inequality for $C = 5/6$. Again as in the first solution,
we obtain an example showing that this value is best possible.
\item[B1]
Note that the function $e^x - x$ is strictly increasing for $x>0$ (because its derivative is $e^x - 1$, which is positive because $e^x$ is strictly increasing), and its value at 0 is 1.
By induction on $n$, we see that $x_n > 0$ for all $n$.
By exponentiating the equation defining $x_{n+1}$, we obtain the expression
\[
x_n = e^{x_n} - e^{x_{n+1}}.
\]
We use this equation repeatedly to acquire increasingly precise information about the sequence $\{x_n\}$.
\begin{itemize}
\item
Since $x_n > 0$, we have $e^{x_n} > e^{x_{n+1}}$, so $x_n > x_{n+1}$.
\item
Since the sequence $\{x_n\}$ is decreasing and bounded below by 0, it converges to some limit $L$.
\item
Taking limits in the equation yields $L = e^L - e^L$, whence $L = 0$.
\item
Since $L = 0$, the sequence $\{e^{x_n}\}$ converges to 1.
\end{itemize}
We now have a telescoping sum:
\begin{align*}
x_0 + \cdots + x_n &= (e^{x_0} - e^{x_1}) + \cdots + (e^{x_n} - e^{x_{n+1}}) \\
&=e^{x_0} - e^{x_{n+1}} = e - e^{x_{n+1}}.
\end{align*}
By taking limits, we see that the sum $x_0 + x_1 + \cdots$ converges to the value
$e-1$.
\item[B2]
We prove that the limit exists for $\alpha = \frac{3}{4}$, $\beta =\frac{4}{3}$.
For any given positive integer $n$, the integers which are closer to $n^2$ than to any other perfect square are the ones in the interval $[n^2 - n - 1, n^2 + n]$. The number of squarish numbers in this interval is $1 + \lfloor \sqrt{n-1} \rfloor + \lfloor \sqrt{n} \rfloor$.
Roughly speaking, this means that
\[
S(N) \sim \int_0^{\sqrt{N}} 2 \sqrt{x} \,dx = \frac{4}{3} N^{3/4}.
\]
To make this precise, we use the bounds $x-1 \leq \lfloor x \rfloor \leq x$,
and the upper and lower Riemann sum estimates for the integral of $\sqrt{x}$,
to derive upper and lower bounds on $S(N)$:
\begin{align*}
S(N) &\geq \sum_{n=1}^{\lfloor \sqrt{N} \rfloor - 1}
(2 \sqrt{n-1}-1) \\
&\geq \int_0^{\lfloor \sqrt{N} \rfloor - 2} 2\sqrt{x} \,dx - \sqrt{N} \\
&\geq \frac{4}{3} (\sqrt{N} - 3)^{3/2} - \sqrt{N}
\end{align*}
\begin{align*}
S(N) &\leq \sum_{n=1}^{\lceil \sqrt{N} \rceil} (2 \sqrt{n} + 1) \\
&\leq \int_0^{\lceil \sqrt{N}\rceil + 1} 2 \sqrt{x}\,dx + \sqrt{N} + 1\\
&\leq \frac{4}{3} (\sqrt{N} + 2)^{3/2} + \sqrt{N} + 1.
\end{align*}
\noindent
\textbf{Remark:}
John Rickert points out that when $N = n^4$, one can turn the previous estimates into exact calculations to obtain the formula
\[
S(N) = \frac{4}{3}\left( n^3 + \frac{n}{2} \right) = \frac{4}{3} N^{3/4} + \frac{2}{3} N^{1/4}.
\]
For general $N$, one can then use the estimates
\begin{align*}
\frac{4}{3} (N-1)^{3/4} + \frac{2}{3} (N-1)^{1/4}
&\leq
S(\lfloor N^{1/4} \rfloor^4) \\
&\leq S(N) \\
&\leq S(\lceil N^{1/4} \rceil^4) \\
&\leq \frac{4}{3} (N+1)^{3/4} + \frac{2}{3} (N+1)^{1/4}
\end{align*}
to obtain the desired limit.
\item[B3]
Since $S$ is finite, we can choose three points $A,B,C$ in $S$ so as to maximize the area of the triangle $ABC$. Let $A', B', C'$ be the points in the plane such that $A,B,C$ are the midpoints of the segments $B'C', C'A', A'B'$; the triangle $A'B'C'$ is similar to $ABC$ with sides twice as long, so its area is 4 times that of $ABC$ and hence no greater than 4.
We claim that this triangle has the desired effect; that is, every point $P$ of $S$ is contained within the triangle $A'B'C'$.
(To be precise, the problem statement requires a triangle of area exactly 4, which need not be the case for $A'B'C'$, but this is trivially resolved by scaling up by a homothety.)
To see this, note that since the area of the triangle $PBC$ is no more than that of $ABC$, $P$ must lie in the half-plane bounded by $B'C'$ containing $B$ and $C$. Similarly, $P$ must lie in the half-plane bounded by $C'A'$ containing
$C$ and $A$, and the half-plane bounded by $A'B'$ containing $A$ and $B$. These three half-planes intersect precisely in the region bounded by the triangle $A'B'C'$, proving the claim.
\item[B4]
The expected value equals
\[
\frac{(2n)!}{4^n n!}.
\]
\noindent
\textbf{First solution:}
Write the determinant of $A-A^t$ as the sum over permutations $\sigma$ of $\{1,\dots,2n\}$ of the product
\[
\sgn(\sigma)
\prod_{i=1}^{2n}
(A-A^t)_{i \sigma(i)}
=
\sgn(\sigma) \prod_{i=1}^{2n} (A_{i \sigma(i)} - A_{\sigma(i) i});
\]
then the expected value of the determinant is the sum over $\sigma$ of the expected value of this product, which we denote by $E_\sigma$.
Note that if we partition $\{1,\dots,2n\}$ into orbits for the action of $\sigma$, then partition the factors of the product accordingly, then no entry of $A$ appears in more than one of these factors; consequently, these factors are independent random variables. This means that we can compute $E_\sigma$ as the product of the expected values of the individual factors.
It is obvious that any orbit of size 1 gives rise to the zero product, and hence the expected value of the corresponding factor is zero. For an orbit of size $m \geq 3$, the corresponding factor contains $2m$ distinct matrix entries, so again we may compute the expected value of the factor as the product of the expected values of the individual terms $A_{i \sigma(i)} - A_{\sigma(i) i}$. However, the distribution of this term is symmetric about 0, so its expected value is 0.
We conclude that $E_\sigma = 0$ unless $\sigma$ acts with $n$ orbits of size 2. To compute $E_\sigma$ in this case, assume without loss of generality that the orbits of $\sigma$ are
$\{1,2\}, \dots, \{2n-1,2n\}$; note that $\sgn(\sigma) = (-1)^n$. Then $E_\sigma$ is the expected value of
$\prod_{i=1}^n -(A_{(2i-1)2i} - A_{2i(2i-1)})^2$, which is $(-1)^n$ times the $n$-th power
of the expected value of $(A_{12} - A_{21})^2$. Since $A_{12} - A_{21}$ takes the values $-1, 0, 1$ with probabilities $\frac{1}{4}, \frac{1}{2}, \frac{1}{4}$, its square takes the values
$0,1$ with probabilities $\frac{1}{2}, \frac{1}{2}$; we conclude that
\[
E_\sigma = 2^{-n}.
\]
The permutations $\sigma$ of this form correspond to unordered partitions of $\{1,\dots,2n\}$ into $n$ sets of size 2, so there are
\[
\frac{(2n)!}{n!(2!)^n}
\]
such permutations. Putting this all together yields the claimed result.
\noindent
\textbf{Second solution:}
(by Manjul Bhargava)
Note that the matrix $A-A^t$ is skew-symmetric:
\[
(A-A^t)^t = A^t-A = -(A-A^t).
\]
The determinant of a $2n \times 2n$ skew-symmetric matrix $M$ is the square of the {\it Pfaffian} of $M$, which is a polynomial of degree $n$ in the entries of $M$ defined as follows. Define a {\it perfect matching} of $\{1,\ldots,2n\}$ to be a permutation of $\{1,\ldots,2n\}$ that is the product of $n$ disjoint transpositions. Then the Pfaffian of $M$ is given by
\begin{equation}\label{pfaffeq}
\sum_{\alpha} \sgn(\alpha) M_{i_1,j_1}\cdots M_{i_n,j_n}
\end{equation}
where the sum is over perfect matchings $\alpha=(i_1,j_1)\cdots(i_n,j_n)$,
and $\sgn(\alpha)$ denotes the sign of the permutation
$\left(\begin{smallmatrix}
1&2&3&4&\cdots & (2n-1)&2n \\
i_1&j_1&i_2&j_2& \cdots & i_n & j_n
\end{smallmatrix} \right)$.
The determinant of $M$ is then the square of \eqref{pfaffeq}, i.e.,
\begin{equation}\label{deteq} \det(M)=\sum_{\alpha,\beta} \sgn(\alpha)\sgn(\beta) M_{i_1,j_1}\cdots M_{i_n,j_n}M_{i'_1,j'_1}\cdots M_{i'_n,j'_n}
\end{equation}
where the sum is now over ordered pairs $$(\alpha=(i_1,j_1)\cdots(i_n,j_n),\beta=(i'_1,j'_1)\cdots(i'_n,j'_n))$$ of perfect matchings.
Taking $M = A - A^t$, so that $M_{ij} = A_{ij} - A_{ji}$,
we wish to find the expected value of \eqref{deteq}; again, this is the sum of the expected values of each summand in \eqref{deteq}. Note that each $M_{ij}$ with $i < j$ is an independent random variable taking the values $-1,0,1$ with probabilities $\frac14,\frac12,\frac14$, respectively.
Consider first a summand in \eqref{deteq} with $\alpha\neq \beta$. Then some factor $M_{ij}$ occurs with exponent 1; since the distribution of $M_{ij}$ is symmetric about 0, any such summand has expected value 0.
Consider next a summand in \eqref{deteq} with $\alpha= \beta$. This summand is a product of distinct factors of the form $M_{ij}^2$; from the distributions of the $M_{ij}$, we see that the expected value of each of these terms is $1/2^n$.
Since the total number of perfect matchings $\alpha$ is $(2n)!/(2^nn!)$, the expected value of $(\ref{deteq})$ is therefore $(2n)!/(2^nn!)\cdot 1/2^n=(2n)!/(4^nn!)$, as desired.
\item[B5]
It is obvious that for any $c>0$, the function $f(x) = x^c$ has the desired property; we will prove that conversely, any function with the desired property has this form for some $c$.
Define the function $g: (0, \infty) \to (0, \infty)$ given by
$g(x) = \log f(e^x)$; this function has the property that if $x,y \in (0, \infty)$
and $2x \leq y \leq 3x$, then $2g(x) \leq g(y) \leq 3g(x)$.
It will suffice to show that there exists $c>0$ such that $g(x) = cx$ for all $x >0$.
Similarly, define the function $h: \RR \to \RR$ given by
$h(x) = \log g(e^x)$; this function has the property that if $x,y \in \RR$
and $x + \log 2 \leq y \leq x + \log 3$, then $h(x) + \log 2 \leq h(y) \leq h(x) + \log 3$.
It will suffice to show that there exists $c>0$ such that $h(x) = x + c$ for all $x \in \RR$
(as then $h(x) = e^c x$ for all $x>0$).
By interchanging the roles of $x$ and $y$, we may restate the condition on $h$ as follows:
if $x - \log 3 \leq y \leq x - \log 2$, then $h(x) - \log 3 \leq h(y) \leq h(x) - \log 2$.
This gives us the cases $a+b=0,1$ of the following statement, which we will establish in full by induction on $a+b$, we deduce the following: for any nonnegative integers $a,b$, for all $x,y \in \RR$ such that
\[
x + a \log 2 - b \log 3 \leq y \leq x + a \log 3 - b \log 2,
\]
we have
\[
h(x) + a \log 2 - b \log 3 \leq h(y) \leq h(x) + a \log 3 - b \log 2.
\]
To this end, suppose that $a+b>0$ and that the claim is known for all smaller values of $a+b$. In particular, either $a>0$ or $b>0$; the two cases are similar, so we treat only the first one. Define the function
\[
j(t) = \frac{(a+b-1)t - b(\log 2 + \log 3)}{a+b},
\]
so that
\begin{gather*}
j(a \log 2 - b \log 3) = a \log 2 - b \log 3, \\
j(a \log 3 - b \log 2) = (a-1) \log 3 - b \log 2, \\
\log 2 \leq t \leq \log 3 \qquad (t \in [a \log 2 - b \log 3, a \log 3 - b \log 2]).
\end{gather*}
For $t \in [a \log 2 - b \log 3, a \log 3 - b \log 2]$ and $y = x+t$,
we then have
\begin{gather*}
(a-1) \log 2 - b \log 3 \leq h(x+j(t)) - h(x) \leq (a-1) \log 3 - b \log 2 \\
\log 2 \leq h(y)-h(x+j(t)) \leq \log 3
\end{gather*}
and thus the desired inequalities.
Now fix two values $x,y \in \RR$ with $x \leq y$. Since $\log 2$ and $\log 3$ are linearly independent over $\QQ$, the fractional parts of the nonnegative integer multiples of $\log 3/\log 2$ are dense in $[0,1)$. (This result is due to Kronecker; a stronger result of Weyl shows that the fractional parts are uniformly distributed in $[0,1)$.)
In particular, for any $\epsilon > 0$ and any $N > 0$, we can find integers $a,b > N$ such that
\[
y-x < a \log 3 - b \log 2 < y-x + \epsilon.
\]
By writing
\begin{align*}
a \log 2 - b \log 3& = \frac{\log 2}{\log 3}(a \log 3 - b \log 2) \\
&\,\,- b \frac{(\log 3)^2 - (\log 2)^2}{\log 3},
\end{align*}
we see that this quantity tends to $-\infty$ as $N \to \infty$; in particular, for $N$ sufficiently large we have that $a \log 2 - b \log 3 < y-x$. We thus have
$h(y) \leq h(x) + a \log 2 - b \log 3 < y-x + \epsilon$; since $\epsilon>0$ was chosen arbitrarily, we deduce that $h(y)-h(x) \leq y-x$. A similar argument shows that $h(y)-h(x) \geq y-x$; we deduce that $h(y) - h(x) = y-x$, or equivalently $h(y)-y = h(x) - x$. In other words, the function $x \mapsto h(x) - x$ is constant, as desired.
\item[B6]
Let $S$ denote the desired sum. We will prove that $S=1$.
\noindent
\textbf{First solution:}
Write
\[
\sum_{n=0}^\infty \frac{1}{k2^n+1} = \frac{1}{k+1} + \sum_{n=1}^\infty \frac{1}{k2^n+1};
\]
then we may write $S = S_1+S_2$ where
\begin{align*}
S_1 &= \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k(k+1)} \\
S_2 &= \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k} \sum_{n=1}^\infty \frac{1}{k2^n+1}.
\end{align*}
The rearrangement is valid because both $S_1$ and $S_2$ converge absolutely in $k$, by comparison to $\sum 1/k^2$.
To compute $S_1$, note that
\begin{align*}
\sum_{k=1}^N \frac{(-1)^{k-1}}{k(k+1)} &= \sum_{k=1}^N (-1)^{k-1}\left(\frac{1}{k}-\frac{1}{k+1} \right) \\
&= -1+\frac{(-1)^N}{N+1}+2\sum_{k=1}^N \frac{(-1)^{k-1}}{k}
\end{align*}
converges to $2\ln 2-1$ as $N\to\infty$, and so $S_1 = 2\ln 2-1$.
To compute $S_2$, write $\frac{1}{k2^n+1} = \frac{1}{k2^n}\cdot \frac{1}{1+1/(k2^n)}$ as the geometric series $\sum_{m=0}^\infty \frac{(-1)^m}{k^{m+1} 2^{mn+n}}$, whence
\[
S_2 = \sum_{k=1}^\infty \sum_{n=1}^\infty \sum_{m=0}^\infty \frac{(-1)^{k+m-1}}{k^{m+2} 2^{mn+n}}.
\]
(This step requires $n \geq 1$, as otherwise the geometric series would not converge for $k=0$.)
Now note that this triple sum converges absolutely: we have
\begin{align*}
\sum_{m=0}^\infty \frac{1}{k^{m+2} 2^{mn+n}} &=
\frac{1}{k^2 2^n} \cdot \frac{1}{1-\frac{1}{k 2^n}} \\
&= \frac{1}{k(k2^n-1)} \leq \frac{1}{k^2 2^{n-1}}
\end{align*}
and so
\begin{align*}
\sum_{k=1}^\infty \sum_{n=1}^\infty \sum_{m=0}^\infty \frac{1}{k^{m+2} 2^{mn+n}} &\leq
\sum_{k=1}^\infty \sum_{n=1}^\infty \frac{1}{k^2 2^{n-1}}\\
&= \sum_{k=1}^\infty \frac{2}{k^2} < \infty.
\end{align*}
Thus we can rearrange the sum to get
\[
S_2 = \sum_{m=0}^\infty (-1)^m \left( \sum_{n=1}^\infty \frac{1}{2^{mn+n}}\right) \left(\sum_{k=1}^\infty
\frac{(-1)^{k-1}}{k^{m+2}} \right).
\]
The sum in $n$ is the geometric series
\[
\frac{1}{2^{m+1}(1-\frac{1}{2^{m+1}})} = \frac{1}{2^{m+1}-1}.
\]
If we write the sum in $k$ as $S_3$, then note that
\[
\sum_{k=1}^\infty \frac{1}{k^{m+2}} = S_3 + 2 \sum_{k=1}^\infty \frac{1}{(2k)^{m+2}}
= S_3 + \frac{1}{2^{m+1}} \sum_{k=1}^\infty \frac{1}{k^{m+2}}
\]
(where we can rearrange terms in the first equality because all of the series converge absolutely), and so
\[
S_3 = \left(1-\frac{1}{2^{m+1}}\right) \sum_{k=1}^\infty \frac{1}{k^{m+2}}.
\]
It follows that
\begin{align*}
S_2 &= \sum_{m=0}^\infty \frac{(-1)^m}{2^{m+1}} \sum_{k=1}^\infty \frac{1}{k^{m+2}} \\
&= \sum_{k=1}^\infty \frac{1}{2k^2} \sum_{m=0}^\infty \left(-\frac{1}{2k}\right)^m \\
&= \sum_{k=1}^\infty \frac{1}{k(2k+1)} \\
&= 2 \sum_{k=1}^\infty \left( \frac{1}{2k} - \frac{1}{2k+1} \right) = 2(1-\ln 2).
\end{align*}
Finally, we have $S = S_1 + S_2 = 1$.
\noindent
\textbf{Second solution:}
(by Tewodros Amdeberhan)
Since $\int_0^1 x^t\,dx = \frac{1}{1+t}$ for any $t \geq 1$, we also have
\[
S = \sum_{k=1}^\infty \sum_{n=0}^\infty \frac{(-1)^{k-1}}{k} \int_0^1 x^{k2^n}\,dx.
\]
Again by absolute convergence, we are free to permute the integral and the sums:
\begin{align*}
S &= \int_0^1 dx\, \sum_{n=0}^\infty \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k} x^{k2^n} \\
&= -\int_0^1 dx\, \sum_{n=0}^\infty \log (1 + x^{2^n}).
\end{align*}
Due to the uniqueness of binary expansions of nonnegative integers, we have the identity
of formal power series
\[
\frac{1}{1 - x} = \prod_{n=0}^\infty (1 + x^{2^n});
\]
the product converges absolutely for $0 \leq x < 1$. We thus have
\begin{align*}
S &= -\int_0^1 \log (1-x)\,dx \\
&= \left((1-x) \log (1-x) - (1-x)\right)_0^1 \\
&= 1.
\end{align*}
\noindent
\textbf{Third solution:}
(by Serin Hong)
Again using absolute convergence, we may write
\[
S = \sum_{m=2}^\infty \frac{1}{m} \sum_{k} \frac{(-1)^{k-1}}{k}
\]
where $k$ runs over all positive integers for which $m = k2^n+1$ for some $n$.
If we write $e$ for the 2-adic valuation of $m-1$ and $j = (m-1)2^{-e}$ for the odd part of $m-1$, then the values of $k$ are $j 2^i$ for $i=0,\dots,e$. The inner sum can thus be evaluated as
\[
\frac{1}{j} - \sum_{i=1}^e \frac{1}{2^i j}
= \frac{1}{2^e j} = \frac{1}{m-1}.
\]
We thus have
\[
S = \sum_{m=2}^\infty \frac{1}{m(m-1)} \\
= \sum_{m=2}^\infty \left( \frac{1}{m-1} - \frac{1}{m} \right) \\
= 1.
\]
\noindent
\textbf{Fourth solution:}
(by Liang Xiao)
Let $S_0$ and $S_1$ be the sums $\sum_k \frac{1}{k} \sum_{n=0}^\infty \frac{1}{k2^n+1}$
with $k$ running over all odd and all even positive integers, respectively, so that
\[
S = S_0 - S_1.
\]
In $S_1$, we may write $k = 2\ell$ to obtain
\begin{align*}
S_1 &= \sum_{\ell=1}^\infty \frac{1}{2\ell} \sum_{n=0}^\infty \frac{1}{\ell 2^{n+1} + 1} \\
&= \frac{1}{2} (S_0 + S_1) - \sum_{\ell=1}^\infty \frac{1}{2\ell(\ell+1)} \\
&= \frac{1}{2} (S_0 + S_1) - \frac{1}{2}
\end{align*}
because the last sum telescopes; this immediately yields $S = 1$.
\end{itemize}
\end{document}