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

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}$ .
Define ${a_0 = 1}$ , ${a_1 = 2}$ and ${a_n = 4a_{n-1} - a_{n-2}}$ . Find an odd prime dividing ${a_{2015}}$ .
Compute
$\displaystyle \log_2 \prod_{a=1}^{2015} \prod_{b=1}^{2015} \left( 1 + e^{\frac{2\pi i a b}{2015}} \right).$
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)}$ .
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}$ .
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

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.
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}$ .
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}$ .
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.
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.
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.

1 thought on “Putnam 2015 Aftermath”

Susan December 8, 20159:45 PM Reply

I solved 9 questions…

LikeLike

Putnam 2015 Aftermath

1. Problems

1.1. Day A

1.2. Night B

2. Solution to Problem A1

3. Solution to Problem A2

4. Solution to Problem A3

5. Solution to Problem A4

6. Solution to Problem A5

7. Solution to Problem B1

8. Solution to Problem B3

9. Solution to Problem B4

10. Solution to Problem B5

Published by Evan Chen (陳誼廷)

1 thought on “Putnam 2015 Aftermath”

Leave a Reply Cancel reply

1. Problems

1.1. Day A

1.2. Night B

2. Solution to Problem A1

3. Solution to Problem A2

4. Solution to Problem A3

5. Solution to Problem A4

6. Solution to Problem A5

7. Solution to Problem B1

8. Solution to Problem B3

9. Solution to Problem B4

10. Solution to Problem B5

Share:

Like this:

Related

Published by Evan Chen (陳誼廷)

1 thought on “Putnam 2015 Aftermath”

Leave a Reply Cancel reply