Putnam 2015 Aftermath

(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 was mostly very easy: 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

\displaystyle  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

    \displaystyle  \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

    \displaystyle  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

    \displaystyle  \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

    \displaystyle  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

    \displaystyle  \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

\displaystyle  -\frac{1}{p^2} = \frac{\frac1a-\frac1b}{a-b} \implies p = \sqrt{ab}

Now the area bounded by {AP} is

\displaystyle  \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

\displaystyle  \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}, \dots, {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

\displaystyle  \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

\displaystyle  \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

\displaystyle  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

\displaystyle  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

\displaystyle  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

\displaystyle  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

\displaystyle  \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

\displaystyle  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

\displaystyle  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

\displaystyle  (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

\displaystyle  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

\displaystyle  \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,

\displaystyle  \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

\displaystyle  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

\displaystyle  A_n = A_{n-1} + A_{n-3} + 1 \qquad n \ge 3.

From this one obtains

\displaystyle  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.


One thought on “Putnam 2015 Aftermath

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s