(EDIT: These solutions earned me a slot in N1, top 16.)

I solved eight problems on the Putnam last Saturday. Here were the solutions I found during the exam, plus my repaired solution to B3 (the solution to B3 I submitted originally had a mistake).

Some comments about the test. I thought that the A test had easy problems: problems A1, A3, A4 were all routine, and problem A5 is a little long-winded but nothing magical. Problem A2 was tricky, and took me well over half the A session. I don’t know anything about A6, but it seems to be very hard.

The B session, on the other hand, was completely bizarre. In my opinion, the difficulty of the problems I did attempt was $$B4 \ll B1 \ll B5 < B3 < B2.$$

1. Problems

1.1. Day A

1. Points $A$ and $B$ are on the same branch of the hyperbola $xy=1$. Point $P$ is selected between them maximizing the area of $\triangle ABP$. Show that the area of region bounded by the hyperbola and $AP$ equals the area of region bounded by the hyperbola and $BP$.

2. Define $a_0 = 1$, $a_1 = 2$ and $a_n = 4a_{n-1} - a_{n-2}$. Find an odd prime dividing $a_{2015}$.

3. Compute

   $$\log_2 \prod_{a=1}^{2015} \prod_{b=1}^{2015} \left( 1 + e^{\frac{2\pi i a b}{2015}} \right).$$

4. Let $f(x) = \sum_{n \in S_x} 2^{-n}$ where $S_x = \{ n \in \mathbb Z^+ \mid \left\lfloor nx \right\rfloor \text { even} \}$. Compute $\inf_{x \in [0,1)} f(x)$.

5. Let $q \ge 1$ be an odd integer and define

   $$N_q = \# \left\{ 0 < a < q/4 \mid \gcd(a,q) = 1 \right\}.$$ Prove $N_q$ is odd if and only if $q = p^k$ for some prime $p \equiv 5,7 \pmod8$.

6. Let $A$, $B$, $M$, $X$ be $n \times n$ real matrices. Prove that if $AM = MB$ and $A$, $B$ have the same characteristic polynomial then $\det(A-MX) = \det(B-XM)$.

1.2. Night B

1. Let $f : \mathbb R \rightarrow \mathbb R$ be thrice differentiable. Prove that if $f$ has at least five distinct roots then $f + 6f' + 12f" + 8f'''$ has at least two distinct roots.

2. Starting with the list of positive integers $1, 2, 3, \dots$, we repeatedly remove the first three elements as well as their sum, giving a sequence of sums $1+2+3=6$, $4+5+7=16$, $8+9+10=27$, $11+12+13=36$, $14+15+17=46$, and so on. Decide whether some sum in the sequence ends with $2015$ in base $10$.

3. Define $S$ to be the set of real matrices $\left(\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right)$ such that $a$, $b$, $c$, $d$ form an arithmetic progression in that order. Find all $M \in S$ such that for some integer $k > 1$, $M^k \in S$.

4. Let $ T = \left{a,b,c) \in \mathbb Z_+^3 \mid a,b,c \text{ are sides of a triangle} \right} $. Prove that

   $$\sum_{(a,b,c) \in T} \frac{2^a}{3^b5^c}$$ is rational and determine its value.

5. Let $P_n$ be the number of permutations $\pi : \{1, \dots, n\} \rightarrow \{1, \dots, n\}$ such that $|\pi(i)-\pi(j)| \le 2$ where $|i-j| \le 1$. For any $n \ge 2$ show that

   $$P_{n+5} - P_{n+4} - P_{n+3} + P_n$$ does not depend on $n$ and determine its value.

6. Let $a(k)$ be the number of odd divisors of $k$ in the interval $[1, \sqrt{2k})$. Compute

   $$\sum_{k \ge 1} \frac{(-1)^{k-1} a(k)}{k}.$$

2. Solution to Problem A1

Standard A1 fare. WLOG $A$ is to the left of $B$ on the positive branch. First we claim the tangent to $P$ must be parallel to line $AB$; otherwise let it intersect the parabola again at $P'$, and any point between $P$ and $P'$ will increase the area of $\triangle ABP$. In that case, we must have $$-\frac{1}{p^2} = \frac{\frac1a-\frac1b}{a-b} \implies p = \sqrt{ab}$$ Now the area bounded by $AP$ is

$$\frac{\frac1a+\frac1p}{2} \cdot (p-a) - \int_a^p \frac 1x dx = \frac{1}{2}\left( \frac pa - \frac ap \right) - \log \left( \frac pa \right).$$

The area of $BP$ is computed similarly and gives $$\frac{1}{2}\left( \frac bp - \frac pb \right) - \log \left( \frac bp \right)$$ and so these are equal.

3. Solution to Problem A2

By induction we have $a_n = \frac12\left( (2+\sqrt3)^n+(2-\sqrt3)^n \right)$. Thus $a_{m} \mid a_{(2k+1)m}$ for any $k$, $m$, because their quotient is both rational and an algebraic integer. Thus $a_5 = 362 = 2 \cdot \boxed{181}$.

During the test, I only found this solution by computing $a_1$, …, $a_{11}$ explicitly and factoring the first $10$ numbers, upon which I realized $a_3 \mid a_9$.

4. Solution to Problem A3

First, we use the fact that for any odd integer $m$, we have $$\prod_{1 \le b \le m} (1 + \zeta^b) = 2$$ where $\zeta$ is an $m$-th root of unity. (Just plug $-1$ into $X^m-1$.) Thus

$$\begin{aligned} \log_2 \prod_{a=1}^{2015} \prod_{b=1}^{2015} \left( 1 + e^{\frac{2\pi i a b}{2015}} \right) &= \log_2 \prod_{a=1}^{2015} 2^{\gcd(a,2015)} \\ &= \sum_{a=1}^{2015} \gcd(a,2015) \\ &= \sum_{d \mid 2015} \frac{2015}{d} \phi(d) \\ &= (5+\phi(5))(13+\phi(13))(31+\phi(31)) \\ &= 9 \cdot 25 \cdot 61 \\ &= \boxed{13725}. \end{aligned}$$

5. Solution to Problem A4

We first prove that $f(x) \ge \frac47$ for every $x \in [0,1)$. It suffices to consider $x \ge \frac{1}{2}$ since otherwise $f(x) \ge \frac12+\frac14$. We note that for any $k$, if $k \notin S_x$ and $k+1 \notin S_x$ then we require that $\left\lfloor kx \right\rfloor = \left\lfloor (k+1)x \right\rfloor = 2m+1$ for some $m$; since $1 \le 2x < 2$ this implies $\left\lfloor (k+2)x \right\rfloor = 2m+2$.

Thus among any three consecutive numbers, at least one is in $S_x$. Plainly $1 \in S_x$ and hence $f(x) \ge 2^{-1} + 2^{-4} + 2^{-7} + \dots = \frac47$.

Finally note that $$f\left( \frac23-\varepsilon \right) \rightarrow \frac47 \quad\text{as}\quad x \rightarrow \frac23$$ so the answer is $L = \boxed{\frac47}$.

6. Solution to Problem A5

Let $q = p_1^{e_1} p_2^{e_2} \dots p_n^{e_n}$. By Principle of Inclusion-Exclusion (or Moebius inversion?) we have

$$N_q = \sum_{S \subset \{1, \dots, n\}} (-1)^{|S|} \left\lfloor \frac{q}{4\prod_{s \in S} p_s} \right\rfloor .$$

The $(-1)^{|S|}$ vanishes when taking modulo $2$. Now, $\left\lfloor \frac{\bullet}{4} \right\rfloor \pmod 2$ depends only on the input modulo $8$, equalling $0$ for $1,3 \pmod 8$ and $1$ for $5,7\pmod8$. As $p^2 \equiv 1 \pmod 8$ the exponents in the floor also can be taken mod $2$. Therefore, we can simplify this to

$$N_q \equiv \sum_{S \subset \{1, \dots, n\}} \left\lfloor \frac{q\prod_{s \in S} p_s}{8} \right\rfloor \pmod 2.$$

Let $A(S) = \left\lfloor \frac{q\prod_{s \in S} p_s}{8} \right\rfloor \pmod 2$. The solution now proceeds in three cases.

If any prime is $1$ or $3$ mod $8$, say $p_1$, then $A(T) = A(T \cup \{1\})$ for $T \subset \{2, \dots, n\}$ and thus $N_q$ is even.

If all primes are $5$ or $7$ mod $8$ and $n \ge 2$, then $A(T) = A(T \cup \{1,2\})$ and $A(T \cup \{1\}) = A(T \cup \{2\})$ for $T \subset \{3, \dots, n\}$ and thus $N_q$ is even.

But if $n = 1$ and $p_1 \equiv 5,7 \pmod 8$ then $A(\varnothing) + A(\{1\})$ is always odd. This completes the proof.

7. Solution to Problem B1

Let $X(f) = f + 2f'$. The problem asks to show $f$ having five distinct real roots implies $X(X(X(f)))$ has at least two. But by Rolle’s Theorem on $$g(x) = e^{\frac{1}{2} x} f(x) \implies 2g'(x) = e^{\frac{1}{2} x}(f(x) + 2f'(x))$$ we see that $f$ having $k$ roots gives $X(f)$ having $k-1$ roots, so done. (I’m told the trick of considering this function $g$ is not new, though I came up with it during the exam so I can’t verify this.)

Lots of people said something about trying to use the Intermediate Value Theorem to show that $X(f)$ has a root between any two roots of $f$. This would require $f$ to be continuously differentiable, so it breaks down at the last application to $X(X(X(f)))$. I deliberately appealed to Rolle’s Theorem because I didn’t trust myself to deal with these real-analytic issues during the exam.

8. Solution to Problem B3

The answer is $$\begin{pmatrix} t&t\\t&t \end{pmatrix} \quad\text{and}\quad \begin{pmatrix} -3t&-t\\t&3t \end{pmatrix}$$ for $t \in \mathbb R$. These work by taking $k=3$.

Now to see these are the only ones, consider an arithmetic matrix $$M = \begin{pmatrix} a & a+e \\ a+2e & a+3e \end{pmatrix}.$$ which is not zero everywhere. Its characteristic polynomial is $t^2 - (2a+3e)t - 2e^2$, with discriminant $(2a+3e)^2 + 8e^2$, so it has two distinct real roots; moreover, since $-2e^2 \le 0$ either one of the roots is zero or they are of opposite signs.

Now we can diagonalize $M$ by writing

$$M = \begin{pmatrix} s & -q \\ -r & p \end{pmatrix} \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \begin{pmatrix} p & q \\ r & s \end{pmatrix} = \begin{pmatrix} ps\lambda_1 - qr\lambda_2 & qs(\lambda_1-\lambda_2) \\ pr(\lambda_2-\lambda_1) & ps\lambda_2 - qr\lambda_1 \end{pmatrix}$$

where $ps-qr=1$. By using the fact the diagonal entries have sum equalling the off-diagonal entries, we obtain that

$$(ps-qr)(\lambda_1+\lambda_2) = (qs-pr)(\lambda_1-\lambda_2) \implies qs-pr = \frac{\lambda_1+\lambda_2}{\lambda_1-\lambda_2}.$$

Now if $M^k \in S$ too then the same calculation gives $$qs-pr = \frac{\lambda_1^k+\lambda_2^k}{\lambda_1^k-\lambda_2^k}.$$ Let $x = \lambda_1/\lambda_2 < 0$ (since $-2e^2 < 0$). We appropriately get

$$\frac{x+1}{x-1} = \frac{x^k+1}{x^k-1} \implies \frac{2}{x-1} = \frac{2}{x^k-1} \implies x = x^k \implies x = -1 \text{ or } x = 0$$

and $k$ odd. If $x=0$ we get $e=0$ and if $x=-1$ we get $2a+3e=0$, which gives the curve of solutions that we claimed. (Unfortunately, during the test I neglected to address $x=-1$, which probably means I will get null marks.)

9. Solution to Problem B4

By the Ravi substitution,

$$\begin{aligned} \sum_{(a,b,c) \in T} \frac{2^a}{3^b5^c} &= \sum_{x,y,z \ge 1 \text{ odd}} \frac{2^\frac{y+z}{2}}{3^{\frac{z+x}{2}} 5^{\frac{x+y}{2}}} + \sum_{x,y,z \ge 2 \text{ even}} \frac{2^\frac{y+z}{2}}{3^{\frac{z+x}{2}} 5^{\frac{x+y}{2}}} \\ &= \sum_{u,v,w \ge 1} \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,v,w \ge 1} \left(\frac{1}{15}\right)^u \left(\frac25\right)^v \left(\frac23\right)^w \\ &= \frac{17}{2} \frac{\frac{1}{15}}{1-\frac{1}{15}} \frac{\frac25}{1-\frac25}\frac{\frac23}{1-\frac23} \\ &= \boxed{\frac{17}{21}}. \end{aligned}$$

No idea why this was B4; it was by far the easiest problem on the test for me. I knew how to do it in less than a second on seeing it and the rest was just arithmetic. (We use the Ravi substitution all the time on olympiad inequalities, so it’s practically a reflex for me.)

10. Solution to Problem B5

My solution was long and disgusting, so I won’t write out the full details. The idea is to let $A_n$ be the number of permutations in $P_{n+1}$ with the additional property that $\pi(1) = 1$. By casework on the index $k$ with $\pi(k) = 1$ (which must be surrounded by $2$ or $3$ if $k \neq 1, n$) one obtains $$P_n = 2(A_0 + A_1 + \dots + A_{n-3} + A_{n-1}) \qquad n \ge 2.$$ Also by more casework one obtains the recursion $$A_n = A_{n-1} + A_{n-3} + 1 \qquad n \ge 3.$$ From this one obtains $$P_n - P_{n-1} = 2(A_{n-1}-A_{n-2}+A_{n-3}) = 2(A_{n-3}+A_{n-4}+1).$$ So we know $P_{n+5}-P_{n+4}$ and can compute $P_{n+3}-P_n = (P_{n+3}-P_{n+2}) + (P_{n+2}-P_{n+1}) + (P_{n+1}-P_n)$ so a long algebraic computation gives that these differ by $\boxed 4$.

Also, I swear I’ve seen the exact condition $|\pi(i)-\pi(j)|\le 2$ many years ago, back when I was doing high school olympiads. But it was so long ago I don’t remember the source.