Putnam 2015

Let $A$ and $B$ be points on the same branch of the hyperbola $xy=1$. Suppose that $P$ is a point lying between $A$ and $B$ on this hyperbola, such that the area of the triangle $APB$ is as large as possible. Show that the region bounded by the hyperbola and the chord $AP$ has the same area as the region bounded by the hyperbola and the chord $PB$.

Let $a_0=1$, $a_1=2$, and $a_n=4a_{n-1}-a_{n-2}$ for $n\geq 2$. Find an odd prime factor of $a_{2015}$.

Compute $$\log_2 \left( \prod_{a=1}^{2015} \prod_{b=1}^{2015} (1+e^{2\pi i a b/2015}) \right)$$ Here $i$ is the imaginary unit (that is, $i^2=-1$).

For each real number $x$, let $$f(x) = \sum_{n\in S_x} \frac{1}{2^n},$$ where $S_x$ is the set of positive integers $n$ for which $\lfloor nx \rfloor$ is even. What is the largest real number $L$ such that $f(x) \geq L$ for all $x \in [0,1)$? (As usual, $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$.)

Let $q$ be an odd positive integer, and let $N_q$ denote the number of integers $a$ such that $0 < a < q/4$ and $\gcd(a,q) = 1$. Show that $N_q$ is odd if and only if $q$ is of the form $p^k$ with $k$ a positive integer and $p$ a prime congruent to $5$ or $7$ modulo $8$.

Let $n$ be a positive integer. Suppose that $A$, $B$, and $M$ are $n\times n$ matrices with real entries such that $AM = MB$, and such that $A$ and $B$ have the same characteristic polynomial. Prove that $\det(A-MX) = \det(B-XM)$ for every $n\times n$ matrix $X$ with real entries.

Let $f$ be a three times differentiable function (defined on $\mathbb{R}$ and real-valued) such that $f$ has at least five distinct real zeros. Prove that $f + 6f' + 12f'' + 8f'''$ has at least two distinct real zeros.

Given a list of the positive integers $1,2,3,4,\dots$, take the first three numbers $1,2,3$ and their sum $6$ and cross all four numbers off the list. Repeat with the three smallest remaining numbers $4,5,7$ and their sum $16$. Continue in this way, crossing off the three smallest remaining numbers and their sum, and consider the sequence of sums produced: $6, 16, 27, 36, \dots$. Prove or disprove that there is some number in the sequence whose base 10 representation ends with $2015$.

Let $S$ be the set of all $2 \times 2$ real matrices $$M = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$$ whose entries $a,b,c,d$ (in that order) form an arithmetic progression. Find all matrices $M$ in $S$ for which there is some integer $k>1$ such that $M^k$ is also in $S$.

Let $T$ be the set of all triples $(a,b,c)$ of positive integers for which there exist triangles with side lengths $a,b,c$. Express $$\sum_{(a,b,c) \in T} \frac{2^a}{3^b 5^c}$$ as a rational number in lowest terms.

Let $P_n$ be the number of permutations $\pi$ of $\{1,2,\dots,n\}$ such that $$|i-j| = 1 \text{ implies } |\pi(i) -\pi(j)| \leq 2$$ for all $i,j$ in $\{1,2,\dots,n\}$. Show that for $n \geq 2$, the quantity $$P_{n+5} - P_{n+4} - P_{n+3} + P_n$$ does not depend on $n$, and find its value.

For each positive integer $k$, let $A(k)$ be the number of odd divisors of $k$ in the interval $[1, \sqrt{2k})$. Evaluate $$\sum_{k=1}^\infty (-1)^{k-1} \frac{A(k)}{k}.$$