\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 76th William Lowell Putnam Mathematical Competition \\
Saturday, December 5, 2015}
\author{Manjul Bhargava, Kiran Kedlaya, and Lenny Ng}
\noaffiliation
\maketitle
\begin{itemize}
\item[A1]
\textbf{First solution:}
Without loss of generality, assume that $A$ and $B$ lie in the first quadrant with $A = (t_1,1/t_1)$, $B = (t_2,1/t_2)$, and $t_1 0$, the map $(x,y) \mapsto (\lambda x, \lambda^{-1} y)$ preserves both areas and the hyperbola $xy=1$. We may thus rescale the picture so that
$A,B$ are symmetric across the line $y=x$, with $A$ above the line. As $P$ moves from $A$ to $B$, the area of $APB$ increases until $P$ passes through the point $(1,1)$, then decreases. Consequently, $P = (1,1)$ achieves the maximum area, and the desired equality is obvious by symmetry.
Alternatively, since the hyperbola is convex, the maximum is uniquely achieved at the point where the tangent line is parallel to $AB$, and by symmetry that point is $P$.
\item[A2]
\noindent
\textbf{First solution:}
One possible answer is $181$.
By induction, we have $a_n = ((2+\sqrt{3})^n+(2-\sqrt{3})^n)/2 = (\alpha^n+\beta^n)/2$ for all $n$, where $\alpha = 2+\sqrt{3}$ and $\beta = 2-\sqrt{3}$. Now note that if $k$ is an odd positive integer and $a_n \neq 0$, then
$\frac{a_{kn}}{a_n} = \frac{\alpha^{kn}+\beta^{kn}}{\alpha^n+\beta^n}
= \alpha^{(k-1)n}-\alpha^{(k-2)n}\beta^n+\cdots-\alpha^n\beta^{(k-2)n}+\beta^{(k-1)n}$.
This expression is both rational (because $a_n$ and $a_{kn}$ are integers) and of the form $a+b\sqrt{3}$ for some integers $a,b$ by the expressions for $\alpha,\beta$; it follows that it must be an integer, and so $a_{kn}$ is divisible by $a_n$. Applying this to $n=5$ and $k=403$, we find that $a_{2015}$ is divisible by $a_5 = 362$ and thus by $181$.
\noindent
\textbf{Second solution:}
By rewriting the formula for $a_n$ as $a_{n-2} = 4a_{n-1} - a_n$, we may extend the sequence backwards to define $a_n$ for all integers $n$. Since $a_{-1} = 2$, we may see by induction that $a_{-n} = a_n$ for all $n$. For any integer $m$ and any prime $p$ dividing $a_m$,
$p$ also divides $a_{-m}$; on the other hand, $p$ cannot divide $a_{-m+1}$, as otherwise $p$ would also divide $a_{-m+2}, \dots, a_0 = 1$, a contradiction. We can thus find an integer $k$ such that $a_{m+1} \equiv k a_{-m+1} \pmod{p}$; by induction on $n$, we see that
$a_n \equiv k a_{n-2m} \pmod{p}$ for all $n$. In particular, if $k$ is odd, then $p$ also divides $a_{km}$; we thus conclude (again) that $a_{2015}$ is divisible by $a_5 = 362$ and thus by $181$.
\noindent
\textbf{Remark:}
Although it was not needed in the solution, we note in passing that if $a_n \equiv 0 \pmod{p}$, then $a_{2n+k} \equiv -a_{k} \pmod{p}$ for all $k$.
\noindent
\textbf{Remark:} One can find other odd prime factors of $a_{2015}$ in the same manner. For example, $a_{2015}$ is divisible by each of the following quantities. (The prime factorizations were computed using
the \texttt{Magma} computer algebra system.)
\begin{align*}
a_{13} &= 2 \times 6811741 \\
a_{31} &= 2 \times 373 \times 360250962984637 \\
a_{5 \cdot 13} &= 2 \times 181 \times 6811741 \\
&\quad \times 3045046274679316654761356161 \\
a_{5 \cdot 31} &= 1215497709121 \times 28572709494917432101 \\
&\quad \times
13277360555506179816997827126375881581 \\
a_{13 \cdot 31} &= 2 \times 373 \times 193441 \times 6811741 \times 360250962984637 \\
&\quad \times 16866100753000669 \\
&\quad \times 79988387992470656916594531961 \times p_{156}
\end{align*}
where $p_{156}$ is a prime of 156 decimal digits. Dividing $a_{2015}$ by the product of the primes appearing in this list yields a number $N$ of 824 decimal digits which is definitely not prime, because $2^N \not\equiv 2 \pmod{N}$, but whose prime factorization we have been unable to establish. Note that $N$ is larger than a 2048-bit RSA modulus, so the difficulty of factoring it is not surprising.
One thing we can show is that each prime factor of $N$ is %divisible by
congruent to $1$ modulo
$6 \times 2015 = 12090$, thanks to the following lemma.
\begin{lemma*}
Let $n$ be an odd integer. Then any odd prime factor $p$ of $a_n$ which does not divide $a_m$ for any divisor $m$ of $n$ is congruent to $1$ modulo $\lcm(6,n)$. (By either solution of the original problem, $p$ also does not divide $a_m$ for any positive integer $m 0$ when $k \geq 1$, whence the upper left entry of $D^k$ is nonzero when $k \geq 2$, a contradiction.
\noindent
\textbf{Remark:}
A variant of this solution can be obtained by diagonalizing the matrix $M$.
\textbf{Second solution:}
If $a,b,c,d$ are in arithmetic progression, then we may write
\[
a = r-3s, b=r-s, c=r+s, d=r+3s
\]
for some $r,s$. If $s=0$, then clearly all powers of $M$ are in S. Also, if $r=0$, then one easily checks that $M^3$ is in $S$.
We now assume $rs\neq 0$, and show that in that case $M$ cannot be in $S$. First, note that the characteristic polynomial of $M$ is $x^2-2rx-8s^2$, and since $M$ is nonsingular (as $s\neq 0$), this is also the minimal polynomial of $M$ by the Cayley-Hamilton theorem. By repeatedly using the relation $M^2=2rM+8s^2I$, we see that for each positive integer, we have $M^k = t_k M + u_k I$ for unique real constants $t_k, u_k$ (uniqueness follows from the independence of $M$ and $I$). Since $M$ is in $S$, we see that $M^k$ lies in $S$ only if $u_k=0$.
On the other hand, we claim that if $k>1$, then $rt_k>0$ and $u_k>0$ if $k$ is even, and $t_k>0$ and $ru_k>0$ if $k$ is odd (in particular, $u_k$ can never be zero). The claim is true for $k=2$ by the relation $M^2=2rM+8s^2I$. Assuming the claim for $k$, and multiplying both sides of the relation $M^k = t_k M + u_k I$ by $M$, yields
\[
M^{k+1} = t_k (2rM+8s^2I) + u_k M = (2rt_k+u_k) M + 8s^2t_k I,
\]
implying the claim for $k+1$.
\noindent
\textbf{Remark:}
(from \url{artofproblemsolving.com}, user \texttt{hoeij})
Once one has $u_k = 0$, one can also finish using the relation $M \cdot M^k = M^k \cdot M$.
\item[B4]
\textbf{First solution:}
The answer is $17/21$. For fixed $b,c$, there is a triangle of side lengths $a,b,c$ if and only if $|b-c|c$. Then
\begin{align*}
S_1 &= \sum_{b=1}^\infty \sum_{c=b}^\infty \frac{2^{b+c}-2^{c-b+1}}{3^b 5^c} \\
&= \sum_{b=1}^\infty \left( \left( \left(\frac{2}{3}\right)^b-\frac{2}{6^b} \right) \sum_{c=b}^\infty \left(\frac{2}{5} \right)^c \right) \\
&= \sum_{b=1}^\infty \left( \left(\frac{2}{3}\right)^b-\frac{2}{6^b} \right) \frac{5}{3} \left( \frac{2}{5} \right)^b \\
&= \sum_{b=1}^\infty \left( \frac{5}{3} \left(\frac{4}{15}\right)^b - \frac{10}{3} \left(\frac{1}{15}\right)^b \right) \\
&= \frac{85}{231}.
\end{align*}
Similarly,
\begin{align*}
S_2 &= \sum_{c=1}^\infty \sum_{b=c+1}^\infty \frac{2^{b+c}-2^{b-c+1}}{3^b 5^c} \\
&= \sum_{c=1}^\infty \left( \left( \left(\frac{2}{5}\right)^c-\frac{2}{10^c} \right) \sum_{b=c+1}^\infty \left(\frac{2}{3} \right)^b \right) \\
&= \sum_{c=1}^\infty \left( \left(\frac{2}{5}\right)^c-\frac{2}{10^c} \right) 3 \left( \frac{2}{3} \right)^{c+1} \\
&= \sum_{c=1}^\infty \left( 2 \left(\frac{4}{15}\right)^c - 4 \left(\frac{1}{15}\right)^c \right) \\
&= \frac{34}{77}.
\end{align*}
We conclude that $S = S_1+S_2 = \frac{17}{21}$.
\noindent
\textbf{Second solution:}
Recall that the real numbers $a,b,c$ form the side lengths of a triangle if and only if
\[
s-a, s-b, s-c > 0 \qquad s = \frac{a+b+c}{2},
\]
and that if we put $x = 2(s-a), y = 2(s-b), z = 2(s-c)$,
\[
a = \frac{y+z}{2}, b = \frac{z+x}{2}, c = \frac{x+y}{2}.
\]
To generate all \emph{integer} triples $(a,b,c)$ which form the side lengths of a triangle, we must also assume that $x,y,z$ are either all even or all odd. We may therefore write the original sum as
\[
%\sum_{(a,b,c) \in T} \frac{2^a}{3^b 5^c}
%=
\sum_{x,y,z >0 \mbox{\small \,odd}} \frac{2^{(y+z)/2}}{3^{(z+x)/2} 5^{(x+y)/2}}
+ \sum_{x,y,z >0 \mbox{\small \,even}} \frac{2^{(y+z)/2}}{3^{(z+x)/2} 5^{(x+y)/2}}.
\]
To unify the two sums, we substitute in the first case $x = 2u+1, y = 2v+1, z = 2w+1$ and in the second case $x = 2u+2, y = 2v+2, z = 2w+2$ to obtain
\begin{align*}
\sum_{(a,b,c) \in T} \frac{2^a}{3^b 5^c}
&= \sum_{u,v,w=1}^\infty \frac{2^{v+w}}{3^{w+u} 5^{u+v}} \left( 1 + \frac{2^{-1}}{3^{-1} 5^{-1}} \right) \\
&= \frac{17}{2} \sum_{u=1}^\infty \left( \frac{1}{15} \right)^u \sum_{v=1}^\infty
\left( \frac{2}{5} \right)^v \sum_{w=1}^\infty \left( \frac{2}{3} \right)^w \\
&= \frac{17}{2} \frac{1/15}{1-1/15} \frac{2/5}{1-2/5} \frac{2/3}{1-2/3} \\
&= \frac{17}{21}.
\end{align*}
\item[B5]
The answer is 4.
We write the permutations $\pi$ counted by $P_n$ as sequences $\pi(1),\pi(2),\ldots,\pi(n)$. Let $U_n$ be the number of permutations counted by $P_n$ that end with $n-1,n$; let $V_n$ be the number ending in $n,n-1$; let $W_n$ be the number starting with $n-1$ and ending in $n-2,n$; let $T_n$ be the number ending in $n-2,n$ but not starting with $n-1$; and let $S_n$ be the number which has $n-1,n$ consecutively in that order, but not at the beginning or end.
It is clear that every permutation $\pi$ counted by $P_n$ either lies in exactly one of the sets counted by $U_n, V_n, W_n, T_n, S_n$, or is the reverse of such a permutation. Therefore
\[
P_n = 2 (U_n + V_n + W_n+ T_n+ S_n).
\]
By examining how each of the elements in the sets counted by $U_{n+1}, V_{n+1}, W_{n+1}, T_{n+1}, S_{n+1}$ can be obtained from a (unique) element in one of the sets counted by $U_n, V_n, W_n, T_n, S_n$ by suitably inserting the element $n+1$, we obtain the recurrence relations
\begin{align*}
U_{n+1} &= U_n+W_n+T_n, \\
V_{n+1}&=U_n, \\
W_{n+1}&=W_n, \\
T_{n+1}&=V_n, \\
S_{n+1}&=S_n+V_n.
\end{align*}
Also, it is clear that $W_n=1$ for all $n$. Therefore,
\begin{align*}
P_{n+5} &= 2(U_{n+5}+V_{n+5}+W_{n+5}+T_{n+5}+S_{n+5}) \\
&= 2((U_{n+4}+W_{n+4}+T_{n+4})+U_{n+4}\\
& \qquad + W_{n+4}+V_{n+4}+(S_{n+4}+V_{n+4})) \\
&= P_{n+4} + 2(U_{n+4}+W_{n+4}+V_{n+4}) \\
&= P_{n+4} + 2((U_{n+3}+W_{n+3}+T_{n+3})+W_{n+3}+U_{n+3}) \\
&= P_{n+4} + P_{n+3} + 2(U_{n+3}-V_{n+3}+W_{n+3}-S_{n+3}) \\
&= P_{n+4} + P_{n+3} + 2((U_{n+2}+W_{n+2}+T_{n+2})-U_{n+2}\\
&\qquad +W_{n+2}-(S_{n+2}-V_{n+2})) \\
&= P_{n+4} + P_{n+3} + 2(2W_{n+2}+T_{n+2}-S_{n+2}-V_{n+2}) \\
&= P_{n+4} + P_{n+3} + 2(2W_{n+1}+V_{n+1}\\
&\qquad -(S_{n+1}+V_{n+1})-U_{n+1}) \\
&= P_{n+4} + P_{n+3} + 2(2W_n+U_n-(S_n+V_n)-U_n\\
&\qquad -(U_n+W_n+T_n)) \\
&= P_{n+4} + P_{n+3} - P_n + 4,
\end{align*}
as desired.
\noindent
\textbf{Remark:}
There are many possible variants of the above solution obtained by dividing the permutations up according to different features. For example, Karl Mahlburg suggests
writing
\[
P_n = 2P'_n, \qquad P'_n = Q'_n + R'_n
\]
where $P'_n$ counts those permutations counted by $P_n$ for which $1$ occurs before 2,
and $Q'_n$ counts those permutations counted by $P'_n$ for which $\pi(1) = 1$. One then has the recursion
\[
Q'_n = Q'_{n-1} + Q'_{n-3} + 1
\]
corresponding to the cases where $\pi(1), \pi(2) = 1,2$; where $\pi(1), \pi(2), \pi(3) = 1,3,2$; and the unique case $1,3,5,\dots,6,4,2$. Meanwhile, one has
\[
R'_n = R'_{n-1} + Q'_{n-2}
\]
corresponding to the cases containing $3,1,2,4$ (where removing 1 and reversing gives a permutation counted by $R'_{n-1}$); and where $4$ occurs before $3, 1, 2$ (where removing $1,2$ and reversing gives a permutation counted by $Q'_{n-2}$).
\noindent
\textbf{Remark:}
The permutations counted by $P_n$ are known as {\it key permutations}, and have been studied by E.S. Page, Systematic generation of ordered sequences using recurrence relations, {\it The Computer Journal} {\bf 14} (1971), no. 2, 150--153. We have used the same notation for consistency with the literature. The sequence of the $P_n$ also appears as entry A003274 in the On-line Encyclopedia of Integer Sequences (\url{http://oeis.org}).
\item[B6]
(from \url{artofproblemsolving.com})
We will prove that the sum converges to $\pi^2/16$.
Note first that the sum does not converge absolutely, so we are not free to rearrange it arbitrarily. For that matter, the standard alternating sum test does not apply because the absolute values of the terms does not decrease to 0, so even the convergence of the sum must be established by hand.
Setting these issues aside momentarily, note that
the elements of the set counted by $A(k)$ are those odd positive integers $d$ for which $m = k/d$ is also an integer and $d < \sqrt{2dm}$; if we write $d = 2\ee-1$, then the condition on $m$ reduces to $m \geq \ee$. In other words, the original sum equals
\[
S_1 := \sum_{k=1}^\infty \sum_{{\ee \geq 1, m \geq \ee}\atop{k = m(2\ee-1)}} \frac{(-1)^{m-1}}{m(2\ee-1)},
\]
and we would like to rearrange this to
\[
S_2 := \sum_{\ee=1}^\infty \frac{1}{2\ee-1} \sum_{m=\ee}^\infty \frac{(-1)^{m-1}}{m},
\]
in which both sums converge by the alternating sum test. In fact a bit more is true:
we have
\[
\left| \sum_{m=\ee}^\infty \frac{(-1)^{m-1}}{m} \right| < \frac{1}{\ee},
\]
so the outer sum converges absolutely.
In particular, $S_2$ is the limit of the truncated sums
\[
S_{2,n} = \sum_{\ee(2\ee-1) \leq n} \frac{1}{2\ee-1} \sum_{m=\ee}^\infty \frac{(-1)^{m-1}}{m}.
\]
To see that $S_1$ converges to the same value as $S_2$, write
\[
S_{2,n} - \sum_{k=1}^n (-1)^{k-1} \frac{A(k)}{k} =
\sum_{\ee(2\ee-1) \leq n} \frac{1}{2\ee-1} \sum_{m=\lfloor \frac{n}{2\ee-1}+1 \rfloor}^\infty
\frac{(-1)^{m-1}}{m}.
\]
The expression on the right is bounded above in absolute value by the sum $\sum_{\ee(2\ee-1) \leq n} \frac{1}{n}$, in which the number of summands is
%at most $\sqrt{n/2}$ and so the total is bounded by $1/\sqrt{2n}$.
at most $\sqrt{n}$ (since $\sqrt{n}(2\sqrt{n}-1)\geq n$), and so the total is bounded above by $1/\sqrt{n}$.
Hence the difference converges to zero as $n \to \infty$; that is, $S_1$ converges and equals $S_2$.
We may thus focus hereafter on computing $S_2$. We begin by writing
\[
S_2 = \sum_{\ee=1}^\infty \frac{1}{2\ee-1} \sum_{m=\ee}^\infty (-1)^{m-1} \int_0^1 t^{m-1}\,dt.
\]
Our next step will be to interchange the inner sum and the integral, but again this requires some justification.
\begin{lemma}
Let $f_0, f_1, \dots$ be a sequence of continuous functions on $[0,1]$ such that for each $x \in [0,1]$, we have
\[
f_0(x) \geq f_1(x) \geq \cdots \geq 0.
\]
Then
\[
\sum_{n=0}^\infty (-1)^n \int_0^1 f_n(t)\,dt = \int_0^1 \left( \sum_{n=0}^\infty (-1)^n f_n(t) \right)\,dt
\]
provided that both sums converge.
\end{lemma}
\begin{proof}
Put $g_n(t) = f_{2n}(t) - f_{2n+1}(t) \geq 0$; we may then rewrite the desired equality as
\[
\sum_{n=0}^\infty \int_0^1 g_n(t) \,dt = \int_0^1 \left( \sum_{n=0}^\infty g_n(t) \right)\,dt,
\]
which is a case of the Lebesgue monotone convergence theorem.
\end{proof}
By Lemma~1, we have
\begin{align*}
S_2 &= \sum_{\ee=1}^\infty \frac{1}{2\ee-1} \int_0^1 \left( \sum_{m=\ee}^\infty (-1)^{m-1} t^{m-1} \right) \,dt \\
&= \sum_{\ee=1}^\infty \frac{1}{2\ee-1} \int_0^1 \frac{(-t)^{\ee-1}}{1+t} \,dt.
\end{align*}
Since the outer sum is absolutely convergent, we may freely interchange it with the integral:
\begin{align*}
S_2 &= \int_0^1 \left(
\sum_{\ee=1}^\infty \frac{1}{2\ee-1} \frac{(-t)^{\ee-1}}{1+t} \right)\,dt \\
&= \int_0^1 \frac{1}{\sqrt{t}(1+t)} \left( \sum_{\ee=1}^\infty \frac{(-1)^{\ee-1} t^{\ee-1/2}}{2\ee-1} \right) \,dt \\
&= \int_0^1 \frac{1}{\sqrt{t}(1+t)} \arctan(\sqrt{t})\,dt \\
&= \int_0^1 \frac{2}{1+u^2} \arctan(u)\,du \qquad (u = \sqrt{t}) \\
&= \arctan(1)^2 - \arctan(0)^2 = \frac{\pi^2}{16}.
\end{align*}
\end{itemize}
\end{document}